Для простого связанного списка, в котором случайный доступ к элементам списка не является обязательным требованием, существуют ли существенные преимущества (производительность или иное) для использования std::list вместо std::vector? Если требуется обратное перемещение, было бы более эффективно использовать std::slist и reverse() список перед повторением его элементов?Относительная производительность std :: vector vs. std :: list vs. std :: slist?
Как обычно, наилучшим ответом на вопросы производительности является profile обе реализации для вашего случая использования и посмотрите, что быстрее.
В общем, если у вас есть вставки в структурой данных (другой, чем в конце), то vector может быть медленнее, в противном случае в большинстве случаев vector, как ожидается, лучше, чем list, если только для data locality issues, это означает, что если два элементы, которые смежны в наборе данных, смежны в памяти, тогда следующий элемент уже будет в кеше процессора и не должен будет печатать страницы в памяти в кеш.
Также помните, что служебные данные пространства для vector являются постоянными (3 указателя), в то время как накладные расходы для list оплачиваются за каждый элемент, это также уменьшает количество полных элементов (данных плюс накладных расходов), которые могут находиться в кеше в любой момент времени.
Имейте в виду, что даже вставки быстрее в векторе, чем в связанном списке, если нужно искать местоположение для вставки.Например, беря кучу случайных целых чисел и вставляя их в отсортированном порядке в вектор или связанный список - вектор всегда будет быстрее, независимо от количества элементов, из-за промахов кеша при поиске точки вставки в связанный список. – Collin 2012-09-29 22:45:24
Довольно часто единственное место, где связанный список работает быстрее, - это когда вы выполняете много сращиваний, поскольку это не связано с большим количеством промахов в кеше, и каждый сплайсинг - операция с постоянным временем (которая может перемещать большое количество предметов из одного связанного списка в другой). – Collin 2012-09-29 22:47:53
«Также имейте в виду, что пространственные накладные расходы для вектора постоянны» Только если вы очень осторожны. Для случайного использования он имеет линейные пространственные накладные расходы, такие же, как «список». См .: амортизированный линейный push_back. – 2017-03-13 21:46:24
Просто нет. Список имеет преимущества перед Vector, но последовательный доступ не является одним из них - если это все, что вы делаете, то вектор лучше.
Однако, вектор стоит дороже добавлять дополнительные элементы, чем список, особенно если вы вставляете посередине.
Поймите, как реализованы эти коллекции: вектор представляет собой последовательный массив данных, список - это элемент, содержащий данные и указатели на следующие элементы. Как только вы это поймете, вы поймете, почему списки хороши для вставок и плохо для случайного доступа.
(так, обратная итерация вектора точно такой же, как и для прямой итерации - итератор просто вычитает размер элементов данных каждый раз, список все равно должен перейти к следующему пункту через указатель)
Если вам нужен обратный ход, то сланс вряд ли станет для вас структурой данных.
Обычный (дважды) связанный список дает вам постоянное время вставки и удаления в любом месте списка; вектор дает только вставку и удаление по умолчанию в конце списка. Для вектора время вставки и удаления является линейным где угодно, кроме конца. Это не вся история; существуют также постоянные факторы. Вектор представляет собой более простую структуру данных, которая имеет преимущества и недостатки в зависимости от контекста.
Лучший способ понять это - понять, как они реализованы. Связанный список имеет следующий и предыдущий указатель для каждого элемента. Вектор имеет массив элементов, адресуемых индексом. Из этого вы можете видеть, что оба могут совершать эффективные переходы вперед и назад, в то время как только вектор может обеспечить эффективный произвольный доступ. Вы также можете видеть, что накладные расходы на память связанного списка на каждый элемент, а для вектора он постоянный. И вы также можете узнать, почему время вставки отличается между двумя структурами.
Смотрите этот вопрос подробности о расходах:
What are the complexity Guarantees of the standard containers
Если у вас есть SLIST и теперь вы хотите, чтобы пересечь его в обратном порядке, почему бы не изменить тип перечислять везде?
Структура данных по умолчанию, о которой нужно думать в C++, это Вектор.
Рассмотрим следующие моменты ...
1] Traversal:
Список узлы разбросаны повсюду в памяти и, следовательно, список обхода приводит к промахов кэша. Но обход векторов является гладким.
2] Вставка и удаление:
Среднее 50% элементов должны быть сдвинуты, когда вы делаете что в вектор, но тайники очень хороши в этом! Но, со списками, вам нужно traverse до точки вставки/удаления ... так что снова ... кэш промахи! И удивительно, что векторы также выигрывают этот случай!
3] Хранение:
При использовании списков, есть 2 указателей на элементы (вперед & назад), поэтому список гораздо больше, чем в векторе! Векторам требуется немного больше памяти, чем нужно фактическим элементам.
У Yout должно быть причина не использовать вектор.
Некоторые строгие тесты на тему: http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html
Как уже отмечалось другими, смежными хранения памяти означает станд: : вектор лучше для большинства вещей. Практически нет оснований для использования std :: list, за исключением небольших объемов данных (где все они могут входить в кеш) и/или где часто происходят стирание и повторное вхождение. Гарантии сложности не относятся к реальной производительности из-за разницы между кешем и основными скоростями памяти (200x), и как непрерывный доступ к памяти влияет на использование кеша. См Чандлер Carruth (Google) говорить о проблеме здесь: https://www.youtube.com/watch?v=fHNmRkzxHWs
И Oriented Design Data Майк Актона говорить здесь: https://www.youtube.com/watch?v=rX0ItVEVjHc
(Late комментарий, только для записи): Ссылка на лекцию Бьерн Страуструп: «Почему вы должны избегать Linked Lists», где он утверждает, что векторы всегда лучше списков. Причина, по которой он дает, заключается в том, что в среднем поиск точки вставки доминирует над усилием, а смещение элементов (в векторах) является незначительным * в сравнении *. Также: промахи кэша, но это уже упоминается в ответе ниже. Видео: http://www.youtube.com/watch?v=YQs6IC-vgmo – 2014-01-16 13:04:23
Несмотря на то, что список почти всегда медленнее, чем вектор (за исключением случаев, когда выполняются высокие уровни сращивания), есть один раз, когда вам абсолютно нужен список: стабильный итераторы. Если вам нужно сохранить копии итераторов, которые всегда будут указывать на один и тот же элемент (если не удалять), это не может гарантировать вектор гарантии (например, вызов push_back может аннулировать все итераторы). Использование пулов памяти может привести к тому, что скорость списка будет намного ближе к скорости вектора. – coderforlife 2014-07-01 22:00:35