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

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

Конечно, вот несколько советов:

int *x, *y;

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

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

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

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

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

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

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