вектор против списка в STL

Question

Я заметил в Effective STL, что

вектор - это тип последовательности, которая должен использоваться по умолчанию.

Что это значит? Кажется, что игнорировать эффективность vector может все что угодно.

Может ли кто-нибудь предложить мне сценарий, в котором vector не является возможным вариантом, но необходимо использовать list?

Answer 1

вектор:

• Непрерывная память.
• Предварительно выделяет пространство для будущих элементов, поэтому требуется дополнительное пространство сверх того, что необходимо для самих элементов.
• Каждый элемент требует только места для самого типа элемента (без дополнительных указателей).
• Может перераспределять память для всего вектора в любое время, когда вы добавляете элемент.
• Вставки в конце - это постоянное амортизированное время, но вставки в другом месте - это дорого O (n).
• Стирание в конце вектора является постоянным временем, а для остальных это O (n).
• Вы можете получить произвольный доступ к его элементам.
• Итераторы становятся недействительными, если вы добавляете или удаляете элементы в или из вектора.
• Вы можете легко получить базовый массив, если вам нужен массив элементов.

список:

• Несмежная память.
• Нет предварительно выделенной памяти. Объем памяти для самого списка постоянен.
• Каждый элемент требует дополнительного пространства для узла, который содержит элемент, включая указатели на следующий и предыдущий элементы в списке.
• Никогда не нужно перераспределять память для всего списка только потому, что вы добавляете элемент.
• Вставки и удаления дешевы независимо от того, где они находятся в списке.
• Дешево объединять списки со сплайсингом.
• Вы не можете получить произвольный доступ к элементам, поэтому получение определенного элемента в списке может быть дорогостоящим.
• Итераторы остаются действительными даже при добавлении или удалении элементов из списка.
• Если вам нужен массив элементов, вам нужно будет создать новый и добавить их все к нему, поскольку базового массива нет.

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

Answer 2

Ситуации, когда требуется многократно вставлять множество элементов в любое место, кроме конца последовательности.

Проверьте гарантии сложности для каждого типа контейнера:

Каковы гарантии сложности стандартных контейнеров?

Answer 3

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

Answer 4

В большинстве ответов здесь не хватает одной важной детали: зачем?

Что вы хотите сохранить в контейнере?

Если это набор int с, то std::list проиграет в каждом сценарии, независимо от того, сможете ли вы перераспределить, вы удалите только спереди и т. Д. Списки перемещаются медленнее, каждая вставка стоит вам взаимодействие с распределителем. Было бы крайне сложно подготовить пример, где list<int> бьет vector<int>. И даже тогда, deque<int> может быть лучше или близким, не просто используя списки, которые будут иметь большую нагрузку на память.

Однако, если вы имеете дело с большими, уродливыми каплями данных - и немногими из них - вы не хотите перераспределять ресурсы при вставке, а копирование из-за перераспределения будет катастрофой - тогда, возможно, вам лучше с list<UglyBlob> чем vector<UglyBlob>.

Тем не менее, если вы переключитесь на vector<UglyBlob*> или даже vector<shared_ptr<UglyBlob> >, снова - список будет отставать.

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

Answer 5

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

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

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

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

Answer 6

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

Вот как я понимаю

Списки : Каждый элемент содержит адрес следующего или предыдущего элемента, поэтому с помощью этой функции вы можете рандомизировать элементы, даже если они не отсортированы, порядок не изменится: это эффективно, если ваша память фрагментирована. Но у него есть и другое очень большое преимущество: вы можете легко вставлять / удалять элементы, потому что единственное, что вам нужно сделать, это изменить некоторые указатели. Минус: Чтобы прочитать случайный элемент, вам нужно переходить от одного элемента к другому, пока не найдете правильный адрес.

Vectors : При использовании векторов память намного более организована, как обычные массивы: каждый n-й элемент сохраняется сразу после (n-1) -го элемента и до (n + 1) -го элемента. Почему это лучше, чем список? Потому что это позволяет быстрый произвольный доступ. Вот как это делается: если вы знаете размер элемента в векторе, и если они непрерывны в памяти, вы можете легко предсказать, где находится n-й элемент; вам не нужно просматривать весь элемент списка, чтобы прочитать тот, который вы хотите, с вектором, вы непосредственно читаете его, со списком, который вы не можете. С другой стороны, изменить векторный массив или изменить значение гораздо медленнее.

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

Я не знаю, как оптимизируются списки, но вы должны знать, что если вы хотите быстрого доступа к чтению, вы должны использовать векторы, потому что, насколько хорошо STL скрепляет списки, он не будет таким быстрым в доступе для чтения чем вектор.

Answer 7

В основном вектор - это массив с автоматическим управлением памятью. Данные непрерывны в памяти. Попытка вставить данные посередине - дорогостоящая операция.

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

Чтобы ответить более конкретно на ваш вопрос, я процитирую эту страницу

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

Answer 8

В любое время вы не можете сделать итераторы недействительными.

Answer 9

Когда у вас много вставок или удалений в середине последовательности. например менеджер памяти.

Answer 10

Если вы хотите перемещать объекты между контейнерами, вы можете использовать list::splice.

Например, алгоритм разбиения графа может иметь постоянное количество объектов, рекурсивно разделенных между увеличивающимся числом контейнеров. Объекты должны быть инициализированы один раз и всегда оставаться в тех же местах в памяти. Гораздо быстрее переставить их путем перекомпоновки, чем перераспределением.

Редактировать: когда библиотеки готовятся к реализации C ++ 0x, общий случай объединения подпоследовательности в список становится линейным усложнением с длиной последовательности. Это связано с тем, что splice (сейчас) необходимо выполнить итерацию последовательности для подсчета количества элементов в ней. (Поскольку список должен записывать его размер.) Простой подсчет и повторное связывание списка по-прежнему быстрее, чем любая альтернатива, а объединение всего списка или одного элемента - это особые случаи с постоянной сложностью. Но если у вас есть длинные последовательности для соединения, вам, возможно, придется покопаться в поисках лучшего, старомодного, несовместимого контейнера.