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