как вставить значение в отсортированный вектор?
ВСЕ,
Этот вопрос является продолжением этот.
Я думаю, что STL пропускает эту функциональность, но это только мое ИМХО.
Теперь к вопросу.
Рассмотрим следующий код:
class Foo
{
public:
Foo();
...........
private:
int paramA, paramB;
std::string name;
};
int main()
{
std::vector<Foo> foo;
Sorter sorter;
sorter.paramSorter = 0;
std::sort( foo.begin(), foo.end(), sorter );
}
struct Sorter
{
bool operator()(const Foo &foo1, const Foo &foo2)
{
switch( paramSorter )
{
case 0:
return foo1.name < foo2.name;
case 1:
return foo1.paramA < foo2.paramB;
case 2:
return foo1. paramA > foo2.paramB;
}
}
private:
int paramSorter;
}
В любой момент времени вектор может быть пересортирован.
У класса также есть методы получения, которые используются в структуре сортировщика.
Какой самый эффективный способ вставить новый элемент в вектор?
Ситуация у меня такая:
У меня есть сетка (электронная таблица), которая использует отсортированный вектор класса. В любой момент времени вектор может быть повторно отсортирован, и сетка будет отображать отсортированные данные соответственно.
Теперь мне нужно будет вставить новый элемент в вектор / сетку.
Я могу вставить, затем повторно отсортировать и затем снова отобразить всю сетку, но это очень неэффективно, особенно для большой сетки.
Любая помощь будет оценена.
Решение
Простой ответ на вопрос:
template< typename T >
typename std::vector<T>::iterator
insert_sorted( std::vector<T> & vec, T const& item )
{
return vec.insert
(
std::upper_bound( vec.begin(), vec.end(), item ),
item
);
}
Версия с предикатом.
template< typename T, typename Pred >
typename std::vector<T>::iterator
insert_sorted( std::vector<T> & vec, T const& item, Pred pred )
{
return vec.insert
(
std::upper_bound( vec.begin(), vec.end(), item, pred ),
item
);
}
Где Pred — строго упорядоченный предикат типа T.
Чтобы это работало, входной вектор уже должен быть отсортирован по этому предикату.
Сложность сделать это O(log N) для upper_bound поиск (найти, где вставить), но до O(N) для самой вставки.
Для лучшей сложности вы можете использовать std::set<T> если не будет дубликатов или std::multiset<T> если могут быть дубликаты. Они автоматически сохранят для вас отсортированный порядок, и вы также можете указать свой предикат.
Есть много других вещей, которые вы могли бы сделать, которые являются более сложными, например, управлять vector и set / multiset / sorted vector недавно добавленных предметов, затем объедините их, когда их будет достаточно. Любой вид перебора вашей коллекции должен проходить через обе коллекции.
Использование второго вектора имеет преимущество в сохранении компактности ваших данных. Здесь ваши «недавно добавленные» предметы vector будет относительно небольшим, поэтому время вставки будет O(M) где M размер этого вектора и может быть более осуществимым, чем O(N) вставлять в большой вектор каждый раз. Слияние будет O(N+M) что лучше чем O(NM) он будет вставлять по одному, так что в общей сложности это будет O(N+M) + O(M²) вставить M элементы затем объединяются.
Вы, вероятно, также сохраните вектор вставки на своем уровне, так что по мере роста вы не будете делать никаких перераспределений, просто перемещая элементы.
Другие решения
Если вам нужно постоянно сортировать вектор, сначала вы можете подумать std::set или же std::multiset не упростит ваш код
Если вам действительно нужен отсортированный вектор и вы хотите быстро вставить в него элемент, но не хотите, чтобы критерий сортировки выполнялся постоянно, тогда вы можете сначала использовать std::lower_bound() чтобы найти позицию в отсортированном диапазоне, где элемент должен быть вставлен в логарифмическом времени, затем используйте insert() функция-член vector вставить элемент в этой позиции.
Если производительность является проблемой, рассмотрите сравнительный анализ std::list против std::vector, Для мелких предметов, std::vector Известно, что быстрее из-за более высокой частоты обращений к кэшу, но insert() Сама операция в списках выполняется быстрее (нет необходимости перемещать элементы).
Просто заметка, вы можете использовать upper_bound а также в зависимости от ваших потребностей. upper_bound обеспечит появление новых записей, эквивалентных другим, на конец их последовательности, lower_bound будет гарантировать, что новые записи, эквивалентные другим, появятся на начало их последовательности. Может быть полезно для определенных реализаций (может быть, классы, которые могут разделять «позицию», но не все их детали!)
И то и другое убедит вас, что вектор остается отсортированным по < результат элементов, хотя вставка в lower_bound будет означать перемещение большего количества элементов.
Пример:
insert 7 @ lower_bound of { 5, 7, 7, 9 } => { 5, *7*, 7, 7, 9 }
insert 7 @ upper_bound of { 5, 7, 7, 9 } => { 5, 7, 7, *7*, 9 }
Вместо вставки и сортировки. Вы должны найти и вставить
Держите вектор отсортированным. (сортировать один раз). Когда вы должны вставить
-
найдите первый элемент, который сравнивается с тем, который больше, чем тот, который вы собираетесь вставить.
-
Сделайте вставку прямо перед этой позицией.
Таким образом, вектор остается отсортированным.
Вот пример того, как это происходит.
start {} empty vector
insert 1 -> find first greater returns end() = 1 -> insert at 1 -> {1}
insert 5 -> find first greater returns end() = 2 -> insert at 2 -> {1,5}
insert 3 -> find first greater returns 2 -> insert at 2 -> {1,3,5}
insert 4 -> find first greater returns 3 -> insert at 3 -> {1,3,4,5}
Когда вы хотите переключаться между порядками сортировки, вы можете использовать несколько индексных структур данных, каждую из которых вы храните в отсортированном порядке (возможно, какое-то сбалансированное дерево, такое как std :: map, которое отображает ключи сортировки на векторные индексы, или std :: для хранения указателей на ваши объекты — но с различными функциями сравнения).
Вот библиотека, которая делает это: http://www.boost.org/doc/libs/1_53_0/libs/multi_index/doc/index.html
Для каждого изменения (вставка новых элементов или обновление ключей) необходимо обновить всю структуру данных индекса или пометить их как недействительные.
Это работает, если не существует «слишком много» порядков сортировки и не «слишком много» обновлений вашей структуры данных. В противном случае — неудача, вам придется пересортировать каждый раз, когда вы хотите изменить порядок.
Другими словами: чем больше индексов вам нужно (для ускорения операций поиска), тем больше времени вам потребуется для операций обновления. И каждый индекс нуждается в памяти, конечно.
Чтобы сохранить небольшое количество индексов, вы можете использовать механизм запросов, который объединяет индексы нескольких полей для поддержки более сложных порядков сортировки по нескольким полям. Как оптимизатор SQL-запросов. Но это может быть излишним …
Пример: если у вас есть два поля, a и b, вы можете поддерживать 4 порядка сортировки:
- б
- сначала а потом б
- сначала б потом
с 2 индексами (3. и 4.).
Чем больше полей, тем больше возможных комбинаций порядка сортировки. Но вы все равно можете использовать индекс, который сортирует «почти так, как вы этого хотите», и во время запроса сортировать оставшиеся поля, которые вы не могли поймать с этим индексом, по мере необходимости. Для отсортированного вывода целых данных это не очень помогает. Но если вы хотите найти только некоторые элементы, первое «сужение» может сильно помочь.
Предполагая, что вы действительно хотите использовать вектор, а критерии сортировки или ключи не меняются (поэтому порядок уже вставленных элементов всегда остается неизменным):
Вставьте элемент в конце, затем перемещайте его вперед по одному шагу за раз, пока предыдущий элемент не станет больше.
Это не может быть сделано быстрее (в отношении асимптотической сложности или «больших обозначений О»), потому что вы должны перемещать все более крупные элементы. И это причина, почему STL не обеспечивает этого — потому что это неэффективно для векторов, и вы не должны использовать их, если вам это нужно.
Изменить: Еще одно предположение: сравнение элементов не намного дороже, чем их перемещение. Смотрите комментарии.
Редактировать 2: Поскольку мое первое предположение не выполняется (вы хотите изменить критерий сортировки), отбросьте этот ответ и посмотрите мой другой: https://stackoverflow.com/a/15843955/1413374