Относительная производительность std::vector против std:: list vs. std:: slist?

Ответ 1

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

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

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

Ответ 2

Структура данных по умолчанию, о которой нужно думать в С++, - это Вектор.

Рассмотрим следующие моменты...

1] Обход:
Узлы списка разбросаны повсюду в памяти, и поэтому обход списка приводит к промахам в кеше. Но обход векторов гладкий.

2] Вставка и удаление:
Средние 50% элементов должны быть сдвинуты, когда вы делаете это с Vector, но кеши очень хороши в этом! Но, со списками, вам нужно перейти к точке вставки/удаления..., так что снова... промахи кэша! И удивительно, что векторы также выигрывают этот случай!

3] Хранение:
Когда вы используете списки, есть два указателя на элементы (вперед и назад), поэтому список намного больше, чем вектор! Векторам требуется немного больше памяти, чем нужно фактическим элементам.

У Yout должна быть причина не использовать вектор.

Ответ 3

Просто нет. Список имеет преимущества перед Vector, но последовательный доступ не является одним из них - если это все, что вы делаете, то лучше вектор.

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

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

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

Ответ 4

Если вам требуется обратное перемещение, то сланс вряд ли станет для вас структурой данных.

Обычный (дважды) связанный список дает вам постоянное время вставки и удаления в любом месте списка; вектор дает только вставку и удаление по умолчанию в конце списка. Для вектора время вставки и удаления является линейным где угодно, кроме конца. Это не вся история; существуют также постоянные факторы. Вектор представляет собой более простую структуру данных, которая имеет преимущества и недостатки в зависимости от контекста.

Лучший способ понять это - понять, как они реализованы. Связанный список имеет следующий и предыдущий указатель для каждого элемента. Вектор имеет массив элементов, адресуемых индексом. Из этого вы можете видеть, что оба могут совершать эффективные переходы вперед и назад, в то время как только вектор может обеспечить эффективный произвольный доступ. Вы также можете видеть, что накладные расходы на память связанного списка на каждый элемент, а для вектора он постоянный. И вы также можете видеть, почему время вставки отличается между двумя структурами.

Ответ 5

Некоторые строгие критерии по теме: http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

Как было отмечено другими, для большинства вещей лучше всего использовать непрерывное запоминающее устройство std::vector. Практически нет оснований для использования std:: list, за исключением небольших объемов данных (где все они могут входить в кеш) и/или где часто происходят стирание и повторное вхождение. Гарантии сложности не относятся к реальной производительности из-за разницы между кешем и основными скоростями памяти (200x) и как непрерывный доступ к памяти влияет на использование кеша. См. Chandler Carruth (google) о проблеме здесь: https://www.youtube.com/watch?v=fHNmRkzxHWs

И Mike Acton Data Oriented Design говорят здесь: https://www.youtube.com/watch?v=rX0ItVEVjHc

Ответ 6

См. этот вопрос для получения подробной информации о стоимости:
Какова сложность Гарантии стандартных контейнеров

Если у вас есть слайдер, и теперь вы хотите пройти его в обратном порядке, почему бы не изменить тип, который будет отображаться повсюду?