Когда вы предпочитаете использовать std :: list <T>вместо std :: vector <T>?

Question

Я никогда не использовал std::list<T> сам.Мне было интересно, когда люди используют его, когда у нас уже есть std::vector<T>, который похож на массивы с непрерывной памятью.std::vector кажется идеальным выбором, когда нам нужен последовательный контейнер!

Так что мой вопрос

• Когда именно вы предпочитаете std::list над std::vector?а почему именно?
• Когда вы предпочитаете std::vector над std::list?и почему?

Если есть соображения производительности, то, пожалуйста, перечислите их также с подробным объяснением / информацией.

Если возможно, укажите несколько ссылок, чтобы поддержать ваш ответ.

Answer 1

Итак, мой вопрос: когда именно вы предпочитаете std::list более std::vector?

Когда мне нужен последовательный контейнер в чувствительной к производительностиплощадь и профилирование показывает std::list быстрее.

Пока что со мной такого никогда не было.

(у меня может возникнуть желание сначала попробовать std::list, когда мне придется хранить очень большие объекты с большим количеством вставок / удалений посередине. Однако на практике я никогда не сталкивался с таким использованием-case.)

Answer 2

Списки лучше вставлять или удалять в любом месте посередине, векторы лучше вставлять в конце.

Векторы также удобнее для доступа к элементам.

Это артефакткак они реализованы.

Итак, если коллекция изменяется очень мало (по сравнению с доступом) или изменения в конце концентрируются, я бы использовал вектор.

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

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

С другой стороны, приложение телефонной книги для особенно популярной и непостоянной рок-звезды, я бы искалк списку.На самом деле, я бы смотрел на соединение с базой данных, но это был лучший пример, который я мог привести в кратчайшие сроки: -)

Что касается ссылок, последний черновой вариант C ++ 0x частично (23.3.4, списки):

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

Раздел 23.3.5 (для векторов):

Вектор - это контейнер последовательности, который поддерживаетитераторы с произвольным доступом.Кроме того, он поддерживает (амортизируется) операции вставки и удаления с постоянным временем в конце;вставка и стирание в середине занимают линейное время.

Answer 3

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

Answer 4

Единственный (несколько) раз, когда я предпочел std::list, связан с функцией-членом list::splice.Если вы перемещаетесь между поддиапазонами в списке или между списками, эта операция может быть значительно быстрее, чем при использовании std::vector.

Answer 5

Мне не нужно повторять основы, но я усвоил трудный путь, что если производительность вставки важна и у вас есть «большие» объекты, то вам следует действительно рассмотреть стандартное представление ::список, даже , если вы вставляете только в конце.(Ну, список или, возможно, вектор умного указателя / ptr_vector.)

У нас были некоторые случаи использования, когда нам приходилось создавать коллекции априорно неизвестного размера структур из нескольких маленьких std :: string и использоватьstd :: vector полностью убил производительность вставки и добавили неснижаемые накладные расходы памяти.

Проблема со std :: vector в сценарии с неизвестным количеством вставок :

• Так как вектор всегда будет перераспределяться, вы платите 50% наихудшего случая на издержки пространства для типичных реализаций (одиночный вектор строки, где объект имеет, например, 24 байта (MSVC), учитывая скудный)100 000 элементов могут занимать пространство 2 МБ и умножаться на более крупные объекты с большим количеством строк или других элементов biggish.)
• Каждый раз, когда вектор должен перераспределяться, он должен копировать все объекты вокруг,и это не дешево, если у вас есть что-нибудь сложное.Очевидно, что семантика перемещения поможет, но если сами объекты большие, повторная копия все еще может быть актуальной.Не имеет значения, является ли среднее амортизированное время вставки (в конце) теоретически постоянным, если вы копируете все ваши объекты многократно во время построения вектора.Вы можете заметить этот удар по производительности.
• Объекты становятся очень большими: структура из двух пустых std :: string уже имеет неподвижных 48 байт в MSVC.

Это не bash std :: vector, я все еще использую его по умолчанию - но знаю, чего ожидать от ваших структур данных!

Answer 6

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

Answer 7

Кто-то скажет, что вы, вероятно, не должны никогда больше никогда не использовать связанный список в вашем коде . ;)

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

(См. Пост в блоге, приведенный выше, для более подробного обсуждения этой конкретной проблемы, с оценками и т. Д.)

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

Но учтите, что даже когда вы делаете , выполняете множество операций такого рода, вам может быть лучше "разместить" свой список в непрерывном буфере std :: vector.

Я обсуждаю это более подробно в этом посте с некоторыми диаграммами и примерами кода: http://upcoder.com/12/vector-hosted-lists/

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

Answer 8

std::list - мое предпочтение почти исключительно для одного свойства, которое vector не разделяет, и это означает, что мои указатели на list всегда будут действительны. Из-за этого я могу использовать это, чтобы содержать все экземпляры любого актива, в котором я нуждаюсь, в одной области, а также одалживать ссылки на другие объекты для использования. Наилучшим примером, который я мог бы придумать, был бы загрузчик изображений, который хранит только одну копию пикселей в памяти, при этом одалживая указатели нескольким объектам, чтобы они все могли рисовать из него.

Все, что есть у vector, это O (1) время доступа. Хотя это звучит как огромный актив, на практике мне очень редко когда-либо приходилось обращаться к элементам в структуре данных, не переходя от «первого» к «последнему»

Answer 9

Используйте список, когда его семантика недействительности и характеристики производительности соответствуют вашим требованиям.

Список может вставлять / стирать / сращивать в любом месте O (1), и это не делает недействительными никакие итераторы. Вектор - это O (n) для вставки / стирания, за исключением конца, и даже тогда только для вставки, если размер <емкость; вектор не может сраститься. Производительность еще тоньше, чем, например, в другом ответе указано место кэширования. </p>

Answer 10

Вы используете std :: list, когда вам нужно часто изменять последовательность в других местах, кроме передней или задней. Издержки таких операций велики в std :: vector при сравнении std :: list.