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

Question

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

Answer 1

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

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

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

Answer 2

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

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

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

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

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

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

---

Справка:
Я узнал об этом в беседе с лордом Бьярном Страуструпом: https://youtu.be/0iWb_qi2-uI?t=2680

Answer 3

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

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

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

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

Answer 4

Некоторые строгие тесты по теме: http://baptiste -wicht.com / сообщений / 2012/12 / CPP-тест-вектор-список-deque.html

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

А Майк-Актон, специализирующийся на данных, говорит здесь: https://www.youtube.com/watch?v=rX0ItVEVjHc

Answer 5

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

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

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

Answer 6

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

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