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

Ответ 1

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

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

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

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

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

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

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

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

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

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

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

Ответ 2

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

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

До сих пор это никогда не случалось со мной.

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

Ответ 3

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

Ответ 4

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

Ответ 5

Мне не нужно повторять основы, но то, что я усвоил, - это то, что если производительность вставки актуальна и у вас есть "большие" объекты, тогда вам действительно стоит рассмотреть std:: list, re только вставка в конце. (Ну, список или, возможно, вектор умного указателя /ptr _vector.)

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

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

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

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

Ответ 6

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

Ответ 7

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

Ответ 8

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

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

Ответ 9

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

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

Ответ 10

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

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

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

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

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

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

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

Ответ 11

Вам следует использовать список, когда вы делаете много удалений/вставок.

Вектор может использоваться, если общий размер элементов не меняется много, а если вы выполняете некоторую замену.