What is the asymptotic complexity of operations with the std::vector class in C++?

Asymptotic complexity for basic operations with std::vector:

Operation	Average Time	Worst-case Time
Element access ([], at)	O(1)	O(1)
Insertion/deletion at the end	O(1)	O(N)
Insertion/deletion at the beginning/middle	O(N)	O(N)
Getting size (size)	O(1)	O(1)
Resizing (resize)	O(N)	O(N)

Explanations:

• O(1) (constant time): The operation takes a fixed number of steps regardless of the vector size.
• O(N) (linear time): The operation's time is directly proportional to the number of elements in the vector (N).

Additionally:

• Insertion/deletion at the end may require O(N) in the worst case due to memory reallocation when the current capacity is insufficient. During reallocation, a new, larger buffer is created, and all existing elements are copied into it. Thanks to the memory allocation strategy (usually doubling the capacity), the average time for insertion/deletion at the end remains O(1).
• Insertion/deletion in the middle requires shifting all subsequent elements, which takes O(N) time.

Example of reallocation during push_back:

// Suppose the vector has a capacity of 4 and is full
std::vector<int> vec = {1, 2, 3, 4}; // Capacity = 4, Size = 4

// Adding a new element requires reallocation
vec.push_back(5); // Capacity might become 8, and all elements are copied

// The push_back operation in this case took O(N) time,
// where N is the number of elements before reallocation.