Introduction
Vectors are sequence containers which is a part of the C++ Standard Template Library. They share similarities with arrays, such as using continuous memory storage and allowing efficient element access through pointers. However, unlike arrays, vectors can change in size dynamically, and their storage is managed automatically by the container.
Using a vector in programming is indeed convenient, but having a solid understanding of how it works and is implemented under the hood can be highly beneficial.
How does vector work?
When considering how vector is implemented it's essential to understand two critical properties: capacity and size. Initially, when you declare a vector, no memory is allocated. As you add elements to it, both its size and capacity change dynamically to accommodate the growing data.
When adding an element to a vector, two scenarios arise:
Capacity is Sufficient: If the vector's capacity is greater than or equal to its size, you can simply add the new element to the available space. This operation has a time complexity of O(1) because it involves a basic assignment.
Capacity is Insufficient: When the vector's capacity is not enough to accommodate the new element, a resizing operation is necessary. Typically, this involves allocating a new contiguous block of memory with double the initial capacity and copying all the old elements to this new memory. This copying process has a time complexity of O(n) since all elements need to be moved one by one. However, when considering the overall performance, including the less frequent resizing operations, the amortized time complexity for insertions remains O(1). This is because the resizing operations become less frequent as the vector grows, effectively spreading the cost of copying elements over multiple insertions and maintaining an average constant-time insertion performance.
In summary, while resizing a vector may incur an O(n) time cost, the amortized time complexity for insertions remains O(1), making vectors a versatile and efficient data structure for dynamic collections.
To gain a deeper understanding of how resizing works in vectors, let's examine the following code and accompanying diagrams:
vector<int> v;
// Operation 1
v.push_back(16);
cout << "size: " << v.size() << ", capacity: " << v.capacity() << endl;
// Operation 2
v.push_back(14);
cout << "size: " << v.size() << ", capacity: " << v.capacity() << endl;
// Operation 3
v.push_back(25);
cout << "size: " << v.size() << ", capacity: " << v.capacity() << endl;
// Operation 4
v.push_back(18);
cout << "size: " << v.size() << ", capacity: " << v.capacity() << endl;
// Operation 5
v.push_back(10);
cout << "size: " << v.size() << ", capacity: " << v.capacity() << endl;
// Operation 6
v.pop_back();
cout << "size: " << v.size() << ", capacity: " << v.capacity() << endl;
Initially, both the vector size and capacity are zero.
Operation 1 - We add a new element, the capacity becomes 2 and the size increases to 1.
Operation 2 - We add one more element, the size will increase by 1, but the capacity will remain the same.
Operation 3 - One more element is added, the size becomes 3, and the capacity is doubled to 4.
Operation 4 - Adding another element, the capacity will be the same since the new element being added can be accommodated but the size now becomes 4.
Operation 5 - The capacity has to be increased now, it is doubled to 8.
Operation 6 - This case is interesting. We are deleting one element from the end of the vector. We would expect the capacity to reduce by half but no it does not happen. The capacity of the vector does not change on element removal.
Conclusion
The above representation simplifies the description of each operation and its impact on the capacity and size of the vector (dynamic array). It highlights how capacity typically increases when needed to accommodate new elements but doesn't necessarily decrease when elements are removed to optimize performance.
Please upvote this post if it helped you and follow me for more such blogs :)