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

Question

Для простого связанного списка, в котором произвольный доступ к элементам списка не является обязательным, есть ли существенные преимущества (производительность или иное) в использовании std :: list вместо std: : вектор ? Если требуется обратный переход, будет ли эффективнее использовать std :: slist и reverse () список до перебора его элементов?

Answer 1

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

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

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

Answer 2

Структура данных по умолчанию для C ++ - Вектор .

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

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

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

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

У Yout должна быть причина не использовать вектор. <ч> Справка:
Я узнал об этом в беседе с лордом Бьярном Страуструпом: https://youtu.be/0iWb_qi2-uI ? Т = 2680 <р>

Answer 3

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

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

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

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

Answer 4

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

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

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

Answer 5

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

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

И о Майк-Актоне, ориентированном на данные, поговорим здесь: https://www.youtube.com/watch?v=rX0ItVEVjHc

Answer 6

Подробнее о расходах см. в этом вопросе:
Каковы гарантии сложности стандартных контейнеров

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