Size of a vector counts the number of built elements; capacity counts how many elements fit in the currently allocated block of memory. This is where people confuse two numbers and thus make their iterator code vulnerable to any changes in vector internals.
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec;
for (int i = 0; i < 5; ++i) {
vec.push_back(i);
std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << "\n";
}
return 0;
}When compiled and executed on a computer running the GCC compiler, this program will generate the following output:
The vector retains all values and changes the address - just the way pointers don't like it.
Size: 1, Capacity: 1 Size: 2, Capacity: 2 Size: 3, Capacity: 4 Size: 4, Capacity: 4 Size: 5, Capacity: 8The size of a vector is the number of elements in the vector, and the capacity is the number of elements that the vector can accommodate in its currently allocated block of memory. The resizing function not only increases the capacity but also builds the necessary elements. On the other hand, the reservation function can increase the capacity of a vector without building the elements.
The above output shows the difference between size and capacity. Size means the number of elements that are currently active in the vector, while capacity means the total number of elements that the vector can accommodate in its currently allocated block of memory. When size exceeds the capacity, the vector needs to allocate a new, bigger block of memory on the heap, move the existing elements to the new memory block, and deallocate the old memory block. Such process is known as reallocation.
Observe that the capacity doesn't increase by one element each time the vector runs out of space. Rather, it doubles. Were the vector to grow by one element each time, every append operation would cause reallocation. It would have to allocate the memory block on the heap, copy all the elements in the new memory block. By growing in a geometric progression, the vector guarantees that reallocation happens rarely, which allows it to maintain a low average cost of adding an element.
Reallocation and capacity control mechanics
During reallocation the vector performs the following operations sequentially: requests a new memory block from the system allocator, its size being defined by the growth factor of the vector (it equals two for GCC and Clang, one and a half for MSVC); moves or copies the existing elements to the new memory block; calls the destructors of the elements in the old memory block; deallocates the old memory block.
When there's growth that exceeds capacity, the vector requests new storage and moves/copies the existing elements to it. The pointers/references/iterators into the old memory block become invalid. You can reserve an estimated final size in order to avoid further reallocations, but reserving the excessive size will keep memory that the vector won't use. The capacity-reduction function is a non-binding request, not a guaranteed reduction of capacity.
In order to optimize the process, C++ vectors utilize move semantics. If the element type stored in the vector has the move constructor that is marked as non-throwing, the vector will move the elements to the new memory block instead of copying them. It is much faster since it transfers the ownership of the resources rather than copying them. However, if the move constructor is marked as throwing, the vector will do copying, because it guarantees exception safety: if an exception happens while copying, the operation can be aborted and the original elements will remain untouched in the old memory block.
While the vector automatically increases its capacity, it doesn't decrease the capacity after deletion of some elements. When you clear a vector or pop elements from it, the size changes, but the capacity stays the same. It's assumed that if you needed such capacity once, you may need it in the future, which saves the costs of future allocations. To release the unused memory, use the capacity-reduction member function, as follows:
#include <iostream>
#include <vector>
int main() {
std::vector<int> numbers;
numbers.reserve(100); // Allocate space for 100 elements
numbers.push_back(10);
numbers.push_back(20);
std::cout << "Before shrink - Size: " << numbers.size()
<< ", Capacity: " << numbers.capacity() << "\n";
numbers.shrink_to_fit();
std::cout << "After shrink - Size: " << numbers.size()
<< ", Capacity: " << numbers.capacity() << "\n";
return 0;
}When the capacity-reduction function is called, the vector allocates the new memory block with the size equal to the current one, moves the elements there and deallocates the excessive memory block. Be aware that the capacity-reduction function is a non-binding request. The C++ Standard leaves it up to the compiler implementation whether to honor this request or not. Most modern compilers free the memory but you can't rely on this guarantee in the environment with severe resource constraints.
Exercise: Vector Size, Capacity, and ReallocationStarter code, hints and solutionOpenClose
Practice: Vector Size, Capacity, and Reallocation
Work through the mission, reveal hints only when needed, and compare your result with the model solution.
Your challenge
Push 30 as a third element before shrink_to_fit. Predict size before and after and distinguish that guarantee from implementation-dependent capacity changes.
Mission checklist
- Run the starter as a baseline, then predict the change requested in Your challenge.
- Make that change in your editor; use the lesson-specific hints if you need help.
- Compile and run your answer, then compare with the worked solution and explain the result.
Starter program
This is the working baseline, not the completed answer. Compile as C++20, then make the change described above.
#include <iostream>
#include <vector>
int main() {
std::vector<int> numbers;
numbers.reserve(100); // Reserve capacity for at least 100 elements
numbers.push_back(10);
numbers.push_back(20);
std::cout << "Before shrink - Size: " << numbers.size()
<< ", Capacity: " << numbers.capacity() << "\n";
numbers.shrink_to_fit();
std::cout << "After shrink - Size: " << numbers.size()
<< ", Capacity: " << numbers.capacity() << "\n";
return 0;
}Hints
reserve(100) requests capacity for at least 100 elements but does not create 100 elements. Only the two push_back calls increase size here.
shrink_to_fit is a request, not a guarantee that capacity will become exactly size. Predict the element count confidently, but inspect the capacity reported by your implementation.
Worked solution
A third push adds 30, so size is 3 before and after shrink_to_fit. reserve changes capacity rather than size. The exact capacity and whether shrink_to_fit honors the request are implementation-dependent; the displayed run is an example, not a capacity guarantee.
#include <iostream>
#include <vector>
int main() {
std::vector<int> numbers;
numbers.reserve(100); // Reserve capacity for at least 100 elements
numbers.push_back(10);
numbers.push_back(20);
numbers.push_back(30);
std::cout << "Before shrink - Size: " << numbers.size()
<< ", Capacity: " << numbers.capacity() << "\n";
numbers.shrink_to_fit();
std::cout << "After shrink - Size: " << numbers.size()
<< ", Capacity: " << numbers.capacity() << "\n";
return 0;
}
Example output
This is one tested C++20 run. Sizes, capacity, formatting, floating-point details, or extra container lifetime messages may differ by implementation; use the explanation to identify the guaranteed result.
Before shrink - Size: 3, Capacity: 100
After shrink - Size: 3, Capacity: 3
0 comments
No comments yet. Be the first.