Какая асимптотическая сложность у обращения по индексу в std::vector?

O(1) — константное время. Это одна из ключевых характеристик std::vector.

Причина: Элементы std::vector хранятся в непрерывном блоке памяти, подобно обычному массиву C. Это позволяет вычислить адрес любого элемента за константное время с помощью простой арифметики указателей.

Как это работает под капотом:

// Примерная логика оператора []
reference vector::operator[](size_type index) {
    // start_ptr — указатель на начало выделенного блока памяти
    return start_ptr[index]; // Эквивалентно *(start_ptr + index)
}

Адрес i-го элемента вычисляется как: адрес_начала + i * sizeof(тип_элемента). Это одна операция сложения и умножения, не зависящая от размера вектора.

Пример и сравнение:

#include <vector>
#include <list>
#include <iostream>

int main() {
    std::vector<int> vec = {10, 20, 30, 40, 50};
    std::list<int> lst = {10, 20, 30, 40, 50};

    // O(1) для vector
    int val1 = vec[2]; // Мгновенный доступ к 3-му элементу
    val1 = vec.at(2);  // O(1), но с проверкой границ (throws std::out_of_range)

    // O(n) для list (линейный поиск от начала или конца)
    // У std::list НЕТ оператора []. Придётся итерироваться:
    auto it = lst.begin();
    std::advance(it, 2); // Это операция O(n) для list!
    int val2 = *it;

    // Практическое следствие:
    const size_t N = 1000000;
    std::vector<int> bigVec(N);
    // Следующий цикл выполняется за O(N) — сумма N операций O(1)
    for (size_t i = 0; i < N; ++i) {
        bigVec[i] = static_cast<int>(i); // Быстро для любого i
    }
}

Важные следствия:

• Произвольный доступ (Random Access): std::vector поддерживает итераторы произвольного доступа, что позволяет использовать алгоритмы, требующие такой возможности (например, std::sort, std::binary_search).
• Локализация данных (Cache Friendliness): Из-за непрерывности хранения данные вектора идеально ложатся в кэш-память процессора, что на практике делает итерацию по нему чрезвычайно быстрой.
• Отличие от std::deque: std::deque также предоставляет доступ по индексу за O(1), но вычисление адреса внутри сложнее (дека обычно реализована как массив указателей на блоки), что может быть чуть менее эффективно, чем у вектора.