Как вы вставляете значение в отсортированный вектор?

ALL,

Этот вопрос является продолжением этого. Я думаю, что 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;
}

В любой момент времени вектор может быть пересортирован. Класс также имеет методы геттера, которые используются в структуре сортировщика.

Каким будет наиболее эффективный способ вставки нового элемента в вектор?

Ситуация у меня есть:

У меня есть сетка (электронная таблица), которая использует отсортированный вектор класса. В любой момент времени вектор может быть повторно отсортирован, и сетка отобразит отсортированные данные соответствующим образом.

Теперь мне нужно будет вставить новый элемент в вектор/сетку. Я могу вставить, а затем повторно отсортировать, а затем повторно отобразить всю сетку, но это очень неэффективно, особенно для большой сетки.

Любая помощь будет оценена.

Ответ 1

Простой ответ на вопрос:

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 
        );
}

Версия с предикатом.

typedef< 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, затем слить.

Вероятно, вы сохраните вектор вставки также в своем качестве, так как вы будете расти, что вы не будете делать перераспределения, просто перемещая элементы.

Ответ 2

Если вам нужно постоянно сортировать вектор, сначала вы можете подумать, не будет ли использование std::set или std::multiset упростить ваш код.

Если вам действительно нужен отсортированный вектор и вы хотите быстро вставить в него элемент, но не хотите, чтобы весь критерий сортировки выполнялся все время, вы можете сначала использовать std::lower_bound(), чтобы найти позицию в отсортированном диапазоне, где элемент должен быть вставлен в логарифмическое время, затем используйте insert() член функции vector, чтобы вставить элемент в эту позицию.

Если производительность является проблемой, рассмотрите сравнительный анализ std::list vs std::vector. Для небольших предметов std::vector, как известно, быстрее из-за более высокой скорости попадания кеша, но сама операция insert() вычисляется быстрее в списках (нет необходимости перемещать элементы вокруг).

Ответ 3

Просто заметьте, вы также можете использовать 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 }

Ответ 4

Вместо вставки и сортировки. Вы должны сделать поиск, а затем вставить

Сохраните вектор. (сортировка один раз). Когда вам нужно вставить

найдите первый элемент, который сравнивается с тем, который вы вставляете.
Сделайте вставку непосредственно перед этой позицией.

Таким образом, вектор остается отсортированным.

Вот пример того, как это происходит.

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}

Ответ 5

Если вы хотите переключаться между порядками сортировки, вы можете использовать несколько индексных структур данных, каждый из которых хранится в упорядоченном порядке (вероятно, какое-то сбалансированное дерево, например std:: map, которое отображает сортировку ключей в векторные индексы, или std:: set для хранения указателей на объекты youre, но с различными функциями сравнения).

Вот библиотека, которая делает это: http://www.boost.org/doc/libs/1_53_0/libs/multi_index/doc/index.html

Для каждого изменения (вставка новых элементов или обновление ключей) вы должны обновить всю индексную структуру данных или пометить их как недействительные.

Это работает, если не существует "слишком много" заказов сортировки, а не "слишком много" обновлений вашей структуры данных. В противном случае - неудача, вам нужно повторно сортировать каждый раз, когда вы хотите изменить порядок.

Другими словами: чем больше индексов вам необходимо (чтобы ускорить операции поиска), тем больше времени вам нужно для операций обновления. И каждый индекс нуждается в памяти, конечно.

Чтобы счетчик индексов был мал, вы можете использовать некоторый механизм запросов, который объединяет индексы нескольких полей для поддержки более сложных порядков сортировки по нескольким полям. Как оптимизатор запросов SQL. Но это может быть излишним...

Пример. Если у вас есть два поля: a и b, вы можете поддерживать 4 порядка сортировки:

а
б
сначала a, затем b
сначала b, затем

с двумя индексами (3. и 4.). С большим количеством полей возможные комбинации заказов сортировки становятся большими, быстрыми. Но вы все равно можете использовать индекс, который сортирует "почти так, как вы этого хотите", и во время запроса сортируйте оставшиеся поля, которые вам не удалось поймать с этим индексом, по мере необходимости. Для отсортированного вывода всех данных это мало помогает. Но если вы хотите только найти некоторые элементы, первое "сужение" может значительно помочь.

Ответ 6

Чтобы добавить к CashCow ответ: Если вы вставляете в отсортированный вектор, а вектор действительно большой, то рассмотрите вопрос о том, чтобы медиана была выделена. Вы все равно должны использовать std:: set, поскольку вставка все еще занимает время O (n). std:: upper_bound теперь должен искать меньше элементов.

template< typename T >
typename std::vector<T>::iterator 
insert_sorted( std::vector<T> & vec, T const& item )
{
    int medianIndex = vec.size()/2;
    if(item < vec.at(medianIndex)/2 )
    {
       return vec.insert( 
        std::upper_bound( vec.begin(), vec.end() - medianIndex+1, item ),
       item);
    }else{
       return vec.insert( 
        std::upper_bound( vec.begin() + medianIndex -1, vec.end(), item ),
       item);
    }
}

Ответ 7

Предполагая, что вы действительно хотите использовать вектор, а критерий сортировки или ключи не меняются (поэтому порядок уже вставленных элементов всегда остается неизменным): Вставьте элемент в конец, затем переместите его на первый шаг за раз, пока предыдущий элемент не станет больше.

Это невозможно сделать быстрее (относительно асимптотической сложности или "большой записи O" ), потому что вы должны перемещать все более крупные элементы. И причина, по которой STL не предоставляет этого, потому что он неэффективен по векторам, и вы не должны использовать их, если вам это нужно.

Изменить: другое предположение: сравнение элементов не намного дороже, чем их перемещение. См. Комментарии.

Изменить 2: Поскольку мое первое предположение не выполняется (вы хотите изменить критерий сортировки), отмените этот ответ и посмотрите на мой другой: fooobar.com/info/201399/...