Каква е асимптотичната сложност на операциите с класа std::vector в C++?

Асимптотична сложност за основните операции с std::vector:

Операция	Средно време	Най-лошо време
Достъп до елемент ([], at)	O(1)	O(1)
Вмъкване/изтриване в края	O(1)	O(N)
Вмъкване/изтриване в началото/средата	O(N)	O(N)
Получаване на размер (size)	O(1)	O(1)
Промяна на размера (resize)	O(N)	O(N)

Обяснения:

• O(1) (константно време): Операцията се изпълнява за фиксирано количество стъпки, независимо от размера на вектора.
• O(N) (линейно време): Времето за изпълнение на операцията е пропорционално на броя на елементите в вектора (N).

Допълнително:

• Вмъкването/изтриването в края може да изисква O(N) в най-лошия случай поради преразпределение на паметта (realloc), когато текущият капацитет не е достатъчен. При realloc се създава нов буфер с по-голям размер и всички съществуващи елементи се копират в него. Благодарение на стратегията за разпределение на паметта (обикновено удвояване на капацитета), средното време за вмъкване/изтриване в края е O(1).
• Вмъкването/изтриването в средата изисква преместване на всички следващи елементи, което отнема O(N) време.

Пример за преразпределение при push_back:

// Да предположим, че векторът има капацитет 4 и е пълен
std::vector<int> vec = {1, 2, 3, 4}; // Капацитет = 4, Размер = 4

// Добавяне на нов елемент изисква преразпределение
vec.push_back(5); // Възможно е капацитетът да стане 8 и всички елементи да бъдат копирани

// Операцията push_back в този случай отне O(N) време,
// където N е броят на елементите преди преразпределението.