Почему доступ к элементам vector-а O(1)?

Question

[Quark]

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

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

Почему тогда поулчение любого элемента вектора всё-равно остаётся O(1)? Ведь для получения элемента нам нужно сначала пройти все предыдущие, а это уже O(n)

Comments

[Алексей 〒.]

std::vector is a sequence container that encapsulates dynamic size arrays

Это обернутый массив

Answer 1

[Евгений Шатунов]

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

Такое поведение имеет список, односвязный или двусвязный.

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

Именно поэтому доступ к любому элементу вектора имеет сложность O(1). Это просто смещение на индекс элемента относительно начала блока памяти с помощью адресной арифметики.

Answer 2

[Irval]

Дело в том, что std::vector - достаточно хитрая структура, использующая непрерывные блоки памяти для реализации "динамического" массива. Сам объект хранит в себе 2 различных размера - capacity (вместимость) и непосредственно size. Последний численно равен количеству добавленных Вами элементов, а вот с capacity дела обстоят чуточку сложнее.
Как Вы, думаю знаете, амортизационная асимптотика вставки элемента в вектор равна O(1). Это достигается благодаря "разрастанию" capacity вдвое каждый раз, когда размер массива переваливает за его вместимость. Структура ищет в памяти блок, размер которого равен 2 * capacity и объявляет его занятым, после чего перемещает всю информацию туда. Поскольку массив хранится на непрерывном участке памяти, то к нему вполне применима адресная арифметика, то есть расстояние от первого элемента вектора до i-ого равно sizeof(datatype) * i. Именно благодаря этому доступ к произвольному элементу осуществляется за константное время.

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

Answer 3

[Dmitrii]

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

Comments

[Quark]

я говорил о std::vector

Но если он основан на динамическом массиве, то как тогда выполняется вставка элементов?

Массив, хранящийся в оперативной памяти, я представляю себе так:
[какие-то даннные]-[наш массив]-[какие-то данные]

Благодаря этому доступ к элементам постоянный.

std::vector я представляю себе так:
[какие-то даннные]-[наш вектор]-[какие-то данные]-[ещё данные с вектора]-[какие-то данные]-[и ещё данные с того же вектора]

В таком случае чтобы найти данные по определённому индексу нужно сначала понять где они хранятся физически

[Евгений Шатунов]

Quark,

Но если он основан на динамическом массиве, то как тогда выполняется вставка элементов?

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

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

[Dmitrii]

Quark, Евгений прекрасно ответил на вопрос. Если у вас много вставок, то используйте std::list, вместо vector или пользуйтесь кастомным алокатором

[Quark]

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

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

[RabraBabr]

Quark, Вектор может часто делать реаллокацию памяти. При том по умолчанию делает это копированием. Кончилась капасити и реаллокация.

Удалили вы первый элемент из вектора все поехало. Можно свапнуть с последним элементом (если он не упорядочен). Вставить в серединку оппять все элементы до конца двигать. и т.д и т.п При том по умолчанию все это в динамической памяти.

Стек быстрее работает, можно использовать std::array. Но стека мало очень.