Как вектор STL дает произвольный доступ

Question

Вчера вечером я использовал std :: vector для своей работы, и у меня возник вопрос: как vector дает произвольный доступ?

Я пытался заглянуть в код, но безуспешно. Кто-нибудь может дать несколько указателей?

Спасибо, Arun

Answer 1

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

Answer 2

Конечно, вот несколько указателей:

int *x, *y;

А если серьезно, vector внутренне просто реализован как массив. Он предоставляет перегруженный оператор индексирования ([]), чтобы вы могли обращаться к нему как к массиву.

Answer 3

как минимум в два раза

На самом деле, многие реализации используют коэффициент 1,5 Важно то, что это фактор, поэтому вы получаете экспоненциальный рост вектора.

Answer 4

Vector обычно использует реализацию динамического массива [*] ... всегда, когда данные хранятся в непрерывном блоке памяти, так что арифметику указателей можно использовать для доступа O (1) к любому (уже существующему) элементу .

Трюк с эффективными динамическими массивами (при условии, что вы этого еще не знаете) - всегда увеличивать размер зарезервированного хранилища как минимум на постоянный коэффициент (см. Комментарий Джерри Коффина). Результатом этого является то, что, поскольку мы добавляем неопределенное количество новых элементов, принимая коэффициент как 2 для простоты, первый элемент копируется в n-е добавление, а (2 * n) добавление и (4 * n) -ое добавление и ...

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

[*] Я не знаю другого механизма, который бы достигал требуемой производительности. Кто-нибудь?