Какой контейнер stl следует использовать при выполнении нескольких вставок?

Question

Я не знаю своих точных цифр, но я буду стараться изо всех сил. У меня есть 10000 элементов, которые были заполнены в самом начале. Затем я просматриваю каждый элемент и каждые 20 элементов мне нужно вставить новый элемент. Вставка произойдет в текущей позиции и, возможно, на один элемент назад.

Мне точно не нужно запоминать позицию, но мне также не нужен произвольный доступ. Я хотел бы быстрые вставки. Имеет ли deque и vector высокую цену для вставки? Должен ли я использовать список?

Мой другой вариант - иметь второй список дэков, и по мере прохождения каждого элемента вставлять его в другой список дэков, если мне не нужно делать вставку, о которой я говорю. Это должно быть быстрым, поскольку его приложение интенсивно работает. Но я использую много указателей (каждый элемент является указателем), что меня огорчает, но я не могу обойти это, поэтому я должен предположить, что кэш L1 всегда будет отсутствовать?

Answer 1

Я бы начал с std::vector, в этом случае , но используйте секунду std::vector для ваших массовых мутаций, reserve() соответственно, затем swap() векторы.

Обновление

Это будет выглядеть так:

std:vector<t_object*> source; // << source already holds 10000 elements

std:vector<t_object*> tmp;

// to minimize reallocations and frees to 1 and 1, if possible.
// if you do not swap or have to grow more, reserving can really work against you.
tmp.reserve(aMeaningfulReserveValue);

while (performingMassMutation) {
  // "i scan through each element and lets every 20 elements"
  for (twentyElements)
    tmp.push_back(source[readPos++]);

  // "every 20 elements i'll need to insert an new element"
  tmp.push_back(newElement);
}

// approximately 500 iterations later…

source.swap(tmp);

Бореалид поднял хорошую мысль, а именно: мера - выполнение сильно варьируется в зависимости от реализаций вашей библиотеки std, размеров данных, сложности копирования и т. Д.

Для необработанных указателей коллекции такого размера с конфигурацией my массовая мутация vector и push_back выше были в 7 раз быстрее, чем вставка std::list. push_back был быстрее, чем вставка диапазона vector.

Как указывает Эмиль ниже, std::vector::swap() не нужно перемещать или перераспределять элементы - он может просто менять внутренние компоненты (при условии, что распределители одного типа).

Answer 2

Во-первых, ответом на все вопросы о производительности является «сравнительный анализ».Всегда.Теперь ...

Если вам не нужны дополнительные объемы памяти и вам не нужен произвольный доступ, но вы делаете заботитесь о вставках в постоянном времени, listвероятно, подходит именно вам.

std::vector будет иметь вставки с постоянным временем в конце , когда он имеет достаточную емкость.Когда емкость превышена, требуется копия с линейным временем.deque лучше, потому что он связывает дискретные выделения, избегая полной копии и позволяя вам делать вставки в постоянном времени также спереди.Случайные вставки (каждые 20 элементов) всегда будут иметь линейное время.

Что касается локальности кэша, vector настолько хорош, насколько вы можете получить (непрерывная память), но вы сказали, что заботились о вставках, а не поисках;по моему опыту, когда это так, вас не волнует, насколько горячим становится кеш при сканировании для выгрузки, поэтому плохое поведение list не имеет большого значения.

Answer 3

Количество копий, выполненных для std::vector/deque ::insert и т. Д., Пропорционально количеству элементов между положением вставки и концом контейнера (количество элементов, которые необходимо сместить, чтобы освободить место).Наихудший случай для std::vector - O(N) - при вставке в переднюю часть контейнера.Если вы вставляете M элементов, то наихудшим случаем будет O(M*N), что не очень хорошо.

Может также произойти перераспределение, если емкость контейнеров будет превышена.Вы можете предотвратить перераспределение, убедившись, что достаточно места было ::reserve впереди.

Другое предложение - лучше скопировать во второй контейнер std::vector/deque, так как его всегда можно организовать для достижения сложности O(N), но за счет временного хранения двух контейнеров.

Использование std::list позволит вам получить вставки O(1) на месте, но за счет дополнительных накладных расходов на память (хранение указателей на список и т. Д.) И уменьшенной локальности памяти (узлы списка не выделяются непрерывно).Вы можете улучшить локальность памяти, используя распределитель памяти пула (Boost pool может быть?).

В целом вам придется провести тест, чтобы по-настоящему разобраться, какой из них «самый быстрый»подход.

Надеюсь, это поможет.

Answer 4

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

Answer 5

Списки полезны, когда вы часто хотите вставить элементы в середину коллекции или часто удаляете их. Однако списки медленно читаются.

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

Запросы - это в основном двусвязные списки, которые можно использовать как векторы.

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

Answer 6

Если вам нужны быстрые вставки посередине, но вам не нужен произвольный доступ, vector и deque определенно не для вас: для них каждый раз, когда вы вставляете что-то, все элементы между этим одним и концом должны быть перемещены.Из встроенных контейнеров list почти наверняка является лучшим выбором.Однако лучшей структурой данных для вашего сценария, вероятно, будет VList , поскольку он обеспечивает лучшую локальность кэша, однако это не обеспечивается стандартной библиотекой C ++.Страница Википедии ссылается на реализацию C ++, однако из быстрого просмотра интерфейса она, похоже, не полностью совместима с STL;Я не знаю, является ли это проблемой для вас.

Конечно, в конце концов, единственный способ убедиться, что является оптимальным решением, это измерить производительность.