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

Question

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

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

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

Answer 1

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

---

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

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

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

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

A vector - это разновидность последовательности, которая поддерживает итераторы произвольного доступа,Кроме того, он поддерживает (амортизируется) операции вставки и удаления с постоянным временем в конце;вставить и стереть в середине взять линейное время.Управление хранилищем обрабатывается автоматически, хотя могут быть даны подсказки для повышения эффективности. Элементы 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) и запросов (23.2.1), быстрый произвольный доступ к элементам списка не поддерживается, но многие алгоритмы в любом случае нуждаются только в последовательном доступе.

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

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

Answer 2

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

Вектор:

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

Список:

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

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

Answer 3

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

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

Answer 4

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

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