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

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

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

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

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

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

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

Quark,

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

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

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

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

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

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

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

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

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