Я провел 3 разных эксперимента с использованием списков и векторов C ++.
Те, у кого были векторы, оказались более эффективными, даже когда в центре было много вставок.
Отсюда вопрос: в каком случае списки имеют больше смысла, чем векторы?
Если векторы кажутся более эффективными в большинстве случаев, и учитывая, насколько похожи их члены, то какие преимущества остаются для списков?
Создайте N целых чисел и поместите их в контейнер, чтобы контейнер оставался отсортированным. Вставка была выполнена наивно, читая элементы один за другим и вставляя новый прямо перед первым большим.
Со списком время проходит через крышу, когда размерность увеличивается по сравнению с векторами.Вставьте N целых чисел в конце контейнера.
Для списков и векторов время увеличилось на тот же порядок, хотя с векторами оно было в 3 раза быстрее.Вставьте N целых чисел в контейнер.
Запустить таймер.
Сортируйте контейнер, используя list.sort для списков и std :: sort для векторов. Стоп таймер.
Опять же, время увеличивается на тот же порядок, но с векторами оно в среднем в 5 раз быстрее.
Я мог бы продолжить выполнять тесты и найти пару примеров, где списки оказались бы лучше.
Но совместный опыт чтения вами этого сообщения, ребята, может дать более продуктивные ответы.
Возможно, вы сталкивались с ситуациями, когда списки были удобнее в использовании или работали лучше?
источник
list
, Вероятно , делает лучше , если вы удаляете много элементов. Я не верю,vector
что когда-нибудь будет возвращена память в систему, пока не будет удален весь вектор. Также имейте в виду, что ваш тест № 1 не проверяет только время вставки. Это тест, сочетающий поиск и вставку. Это поиск места для вставки, гдеlist
медленно. Фактическая вставка будет быстрее, чем вектор.Ответы:
Короткий ответ заключается в том, что случаев, кажется, мало, и далеко между. Хотя, вероятно, есть несколько.
Например, вам нужно хранить небольшое количество крупных объектов, особенно таких больших, что нецелесообразно выделять место даже для нескольких дополнительных объектов. По сути, нет никакого способа остановить вектор или deque от выделения пространства для дополнительных объектов - это то, как они определены (т. Е. Они должны выделить дополнительное пространство, чтобы удовлетворить свои требования к сложности). Если вы не можете выделить это дополнительное пространство, это
std::list
может быть единственным стандартным контейнером, который соответствует вашим потребностям.Другой вариант: когда / если вы будете хранить итератор в «интересной» точке списка в течение длительного периода времени, а когда вы делаете вставки и / или удаления, вы (почти) всегда делаете это с места, до которого у вас уже есть итератор, поэтому вы не проходите по списку, чтобы добраться до точки, где вы собираетесь выполнить вставку или удаление. Очевидно, что то же самое применимо, если вы работаете с более чем одним местом, но по-прежнему планируете хранить итератор для каждого места, с которым вы, вероятно, будете работать, так что вы больше всего манипулируете точками, к которым вы можете добраться напрямую, и очень редко просматриваете список, чтобы получить в эти места.
Для примера первого рассмотрим веб-браузер. Он может хранить связанный список
Tab
объектов, причем каждый объект вкладки отображается на открытой вкладке в браузере. Каждая вкладка может содержать несколько десятков мегабайт данных (и более, особенно если речь идет о чем-то вроде видео). Типичное количество открытых вкладок может быть меньше дюжины, а 100, вероятно, близко к верхнему пределу.В качестве примера второго рассмотрим текстовый процессор, который хранит текст в виде связанного списка глав, каждая из которых может содержать связанный список (скажем) абзацев. Когда пользователь редактирует, он обычно собирается найти конкретное место, где он собирается редактировать, а затем выполняет достаточное количество работы в этом месте (или в любом случае внутри этого абзаца). Да, они будут переходить от одного абзаца к другому время от времени, но в большинстве случаев это будет абзац рядом с тем местом, где они уже работали.
Время от времени (такие как глобальный поиск и замена) вы заканчиваете тем, что просматриваете все элементы во всех списках, но это довольно редко, и даже когда вы делаете, вы, вероятно, будете выполнять достаточно работы по поиску в элементе в список, что время для прохождения списка почти несущественно.
Обратите внимание, что в типичном случае это, вероятно, также соответствует первому критерию - глава содержит довольно небольшое количество абзацев, каждый из которых может быть достаточно большим (по крайней мере, относительно размера указателей в узел и тому подобное). Кроме того, у вас есть относительно небольшое количество глав, каждая из которых может быть несколько килобайт или около того.
Тем не менее, я должен признать, что оба эти примера, вероятно, немного надуманы, и хотя связанный список может работать отлично для обоих, он, вероятно, не обеспечит огромное преимущество в обоих случаях. В обоих случаях, например, выделение дополнительного пространства в векторе для некоторых (пустых) веб-страниц / вкладок или некоторых пустых глав вряд ли будет реальной проблемой.
источник
std::vector
указателей будет более эффективным, чем все эти связанные объекты узлов списка.std::vector<std::unique_ptr<T>>
может быть хорошей альтернативой.По словам самого Бьярна Страуструпа, векторы всегда должны быть коллекцией по умолчанию для последовательностей данных. Вы можете выбрать список, если вы хотите оптимизировать вставку и удаление элементов, но обычно этого делать не следует. Стоимость списка - медленный обход и использование памяти.
Об этом он говорит в этой презентации .
Примерно в 0:44 он говорит о векторах и списках в целом.
Примерно в 1:08 ему задают вопрос по этому вопросу.
источник
Единственное место, где я обычно использую списки, это где мне нужно удалять элементы, а не делать недействительными итераторы.
std::vector
делает недействительными все итераторы при вставке и удалении.std::list
гарантирует, что итераторы к существующим элементам все еще действительны после вставки или удаления.источник
В дополнение к другим уже предоставленным ответам списки имеют определенные функции, которых нет в векторах (потому что они будут безумно дорогими). Операции объединения и слияния являются наиболее значительными. Если у вас часто есть несколько списков, которые необходимо добавить или объединить вместе, список, вероятно, является хорошим выбором.
Но если вам не нужно выполнять эти операции, то, вероятно, нет.
источник
Отсутствие присущей кеш / дружественности страниц связанных списков приводит к тому, что многие разработчики на C ++ почти полностью отклоняют их, и с хорошим обоснованием в этой форме по умолчанию.
Связанные списки все еще могут быть замечательными
Тем не менее, связанные списки могут быть замечательными, если они поддерживаются фиксированным распределителем, который возвращает им пространственную локализацию, которой им по сути не хватает.
Они отличаются тем, что мы можем разделить список на два списка, например, просто сохраняя новый указатель и манипулируя указателем или двумя. Мы можем перемещать узлы из одного списка в другой за постоянное время простым манипулированием указателем, а пустой список может просто иметь стоимость памяти одного
head
указателя.Простой Grid Accelerator
В качестве практического примера рассмотрим 2D визуальное моделирование. У него есть экран прокрутки с картой, которая охватывает 400x400 (160 000 ячеек сетки), используемой для ускорения таких вещей, как обнаружение столкновений между миллионами частиц, движущихся вокруг в каждом кадре (здесь мы избегаем четырех деревьев, поскольку они на самом деле имеют тенденцию работать хуже с этим уровнем динамические данные). Целая группа частиц постоянно движется вокруг каждого кадра, что означает, что они постоянно перемещаются из одной ячейки сетки в другую.
В этом случае, если каждая частица является односвязным узлом списка, каждая ячейка сетки может начинаться как
head
указатель, на который указываетnullptr
. Когда рождается новая частица, мы просто помещаем ее в ячейку сетки, в которой она находится, устанавливаяhead
указатель этой ячейки, чтобы он указывал на этот узел частицы. Когда частица перемещается из одной ячейки сетки в другую, мы просто манипулируем указателями.Это может быть гораздо более эффективным, чем хранить 160 000
vectors
для каждой ячейки сетки и все время сдвигаться назад и стираться с середины на покадровой основе.станд :: список
Это для свернутых вручную, навязчивых, односвязных списков, поддерживаемых фиксированным распределителем.
std::list
представляет собой двусвязный список, и он может быть не таким компактным, если он пустой, как один указатель (зависит от реализации поставщика), плюс это немного затрудняет реализацию пользовательских распределителей вstd::allocator
форме.Я должен признать, что я никогда не использую
list
что-либо. Но связанные списки могут быть замечательными! Тем не менее, они не удивительны по причинам, по которым люди часто испытывают искушение использовать их, и не столь удивительны, если они не подкреплены очень эффективным фиксированным распределителем, который устраняет множество, по крайней мере, принудительных сбоев страниц и связанных с ними ошибок кэша.источник
std::forward_list
.Вы должны учитывать размер элементов в контейнере.
int
Вектор элементов очень быстрый, так как большая часть данных помещается в кэш процессора (и SIMD-инструкции, вероятно, могут использоваться для копирования данных).Если размер элемента больше, результат теста 1 и 3 может значительно измениться.
Из очень полного сравнения производительности :
(как примечание
std::deque
- очень недооцененная структура данных).С точки зрения удобства,
std::list
обеспечивается гарантия того, что итераторы никогда не станут недействительными при вставке и удалении других элементов. Это часто ключевой аспект.источник
На мой взгляд, наиболее важной причиной использования списков является недействительность итераторов : если вы добавляете / удаляете элементы к вектору, все указатели, ссылки, итераторы, которые вы держали для определенных элементов этого вектора, могут быть недействительными и приводить к незначительным ошибкам. или ошибки сегментации.
Это не относится к спискам.
Точные правила для всех стандартных контейнеров приведены в этом сообщении StackOverflow .
источник
Короче говоря, нет веских причин для использования
std::list<>
:Если вам нужен несортированный контейнер,
std::vector<>
правила.(Удалите элементы, заменив их последним элементом вектора.)
Если вам нужен отсортированный контейнер,
std::vector<shared_ptr<>>
правила.Если вам нужен разреженный индекс,
std::unordered_map<>
правила.Вот и все.
Я обнаружил, что есть только одна ситуация, когда я склонен использовать связанный список: когда у меня есть уже существующие объекты, которые нужно каким-то образом подключить для реализации некоторой дополнительной логики приложения. Тем не менее, в этом случае я никогда не использую
std::list<>
, скорее я прибегаю к (умному) следующему указателю внутри объекта, тем более что в большинстве случаев используется дерево, а не линейный список. В некоторых случаях результирующая структура представляет собой связанный список, в других это дерево или ориентированный ациклический граф. Основной целью этих указателей всегда является построение логической структуры, а не управление объектами. У нас естьstd::vector<>
для этого.источник
Вы должны показать, как вы делали вставки в первом тесте. Ваши вторые и третьи тесты, вектор легко победит.
Значительное использование списков - это когда вы должны поддерживать удаление элементов во время итерации. Когда вектор изменяется, все итераторы (потенциально) являются недействительными. В случае списка только итератор удаленного элемента недопустим. Все остальные итераторы остаются действительными.
Типичный порядок использования для контейнеров: vector, deque, затем list. Выбор контейнера обычно основывается на push_back, выбирает вектор, pop_front, выбирает deque, вставляет список выбора.
источник
Один фактор, о котором я могу подумать, заключается в том, что по мере роста вектора свободная память будет фрагментироваться, поскольку вектор освобождает свою память и снова и снова выделяет больший блок. Это не будет проблемой со списками.
Это в дополнение к тому факту, что большое количество
push_back
s без резерва также будет вызывать копию при каждом изменении размера, что делает его неэффективным. Вставка в середине аналогично вызывает перемещение всех элементов вправо, и еще хуже.Хотя я не знаю, является ли это серьезной проблемой, но это была причина, которую мне дали в моей работе (разработка мобильных игр), чтобы избежать векторов.
источник