Является ли вектор особым случаем связанных списков?

Говоря о STL, у меня есть несколько одноклассников, которые говорят мне, что "векторы связаны списками".

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

Они также не понимают, почему я всегда спорю, что вектор смежный, как и любой другой массив, и, похоже, не понимает, что такое случайный доступ. Являются ли векторные строчно смежные точно так же, как обычные массивы, или просто наиболее смежными? (например, он будет выделять несколько смежных сегментов, если весь массив не подходит).

Ответ 1

Мне жаль говорить, что ваши одноклассники совершенно неправы. Если ваши одноклассники могут честно сказать, что "векторы связаны списками", то вам нужно с уважением сказать им, что им нужно подобрать хорошую книгу на С++ (или любую достойную компьютерную науку книги) и прочитал его. Или, возможно, даже статьи в Википедии для векторы и списки, (Также см. Статьи для динамические массивы и связанные списки.)

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

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

Класс std::vector в С++ требуется, чтобы быть смежным по стандарту С++:

23.2.4/1 Шаблон класса vector

A vector - это разновидность последовательности, которая поддерживает итераторы произвольного доступа. Кроме того, он поддерживает (амортизируется) постоянное время вставки и стирания операций в конце; вставлять и стирать в середине, принимать линейное время. Управление хранилищем обрабатывается автоматически, хотя можно дать рекомендации для повышения эффективности. Элементы a vector хранятся смежно, что означает, что если v является vector<T, Allocator>, где T - это какой-то тип, отличный от bool, то он подчиняется идентификатору &v[n] == &v[0] + n для всех 0 <= n < v.size().

Сравните это с std::list:

23.2.2/1 Шаблон класса list

A list - это разновидность последовательности, которая поддерживает двунаправленные итераторы и позволяет выполнять операции по вставке и стиранию времени в любом месте последовательности, причем управление хранилищем обрабатывается автоматически. В отличие от векторов (23.2.4) и deques (23.2.1) быстрый случайный доступ к элементам списка не поддерживается, но многим алгоритмам нужен только последовательный доступ.

Очевидно, что стандарт С++ предусматривает, что вектор и список представляют собой два разных контейнера, которые делают разные вещи.

Вы не можете "разбить" вектор (по крайней мере, не намеренно), просто называя erase() допустимым итератором. Это сделало бы std::vector скорее бесполезным, так как точка его существования - управлять памятью для вас!

Ответ 2

vector будет хранить все хранилище в одном месте. A vector даже не удаленно, как связанный список. Infact, если мне пришлось выбрать две структуры данных, которые были бы самыми непохожими друг на друга, это было бы vector и list. "Приблизительно" - как работает deque.

Vector:

Гарантированное непрерывное хранение для всех элементов - копирует или перемещает элементы.
O (1) время доступа.
O (n) для вставки или удаления.
Итераторы недействительны при вставке или удалении любого элемента.

Список:

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

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

Ответ 3

По определению vector являются непрерывными блоками памяти, такими как C-массивы. См.: http://en.wikipedia.org/wiki/Vector_(C%2B%2B)

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

Ответ 4

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

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