А с вектором дела обстоят иначе. Каждый элемент хранит указатель на следующий после него.
Такое поведение имеет список,
односвязный или
двусвязный.
Вектор же реализован как
непрерывный блок памяти, внутри которого последовательно размещены его элементы. Благодаря этому элементы вектора доступны не только через итераторы, но и через адресную арифметику.
Именно поэтому доступ к любому элементу вектора имеет сложность O(1). Это просто смещение на индекс элемента относительно начала блока памяти с помощью адресной арифметики.
