capacity
and size
It is important to understand the difference between capacity
and size
. The size
of a container is the number of elements it already holds; its capacity
is how many elements it can hold before more space must be allocated.
The following code illustrates the interaction between size
and capacity
:
vector<int> ivec;
// size should be zero; capacity is implementation defined
cout << "ivec: size: " << ivec.size()
<< " capacity: " << ivec.capacity() << endl;
// give ivec 24 elements
for (vector<int>::size_type ix = 0; ix != 24; ++ix)
ivec.push_back(ix);
// size should be 24; capacity will be >= 24 and is implementation defined
cout << "ivec: size: " << ivec.size()
<< " capacity: " << ivec.capacity() << endl;
When run on our system, this code produces the following output:
ivec: size: 0 capacity: 0
ivec: size: 24 capacity: 32
We know that the size
of an empty vector
is zero, and evidently our library also sets the capacity
of an empty vector
to zero. When we add elements to the vector
, we know that the size
is the same as the number of elements we’ve added. The capacity
must be at least as large as size
but can be larger. The details of how much excess capacity is allocated vary by implementations of the library. Under this implementation, adding 24 elements one at a time results in a capacity
of 32.
Visually we can think of the current state of ivec
as
We can now reserve
some additional space:
ivec.reserve(50); // sets capacity to at least 50; might be more
// size should be 24; capacity will be >= 50 and is implementation defined
cout << "ivec: size: " << ivec.size()
<< " capacity: " << ivec.capacity() << endl;
Here, the output indicates that the call to reserve
allocated exactly as much space as we requested:
ivec: size: 24 capacity: 50
We might next use up that reserved capacity as follows:
// add elements to use up the excess capacity
while (ivec.size() != ivec.capacity())
ivec.push_back(0);
// capacity should be unchanged and size and capacity are now equal
cout << "ivec: size: " << ivec.size()
<< " capacity: " << ivec.capacity() << endl;
The output indicates that at this point we’ve used up the reserved capacity, and size
and capacity
are equal:
ivec: size: 50 capacity: 50
Because we used only reserved capacity, there is no need for the vector
to do any allocation. In fact, as long as no operation exceeds the vector
’s capacity, the vector
must not reallocate its elements.
If we now add another element, the vector
will have to reallocate itself:
ivec.push_back(42); // add one more element
// size should be 51; capacity will be >= 51 and is implementation defined
cout << "ivec: size: " << ivec.size()
<< " capacity: " << ivec.capacity() << endl;
The output from this portion of the program
indicates that this vector
implementation appears to follow a strategy of doubling the current capacity each time it has to allocate new storage.
We can call shrink_to_fit
to ask that memory beyond what is needed for the current size be returned to the system:
ivec.shrink_to_fit(); // ask for the memory to be returned
// size should be unchanged; capacity is implementation defined
cout << "ivec: size: " << ivec.size()
<< " capacity: " << ivec.capacity() << endl;
Calling shrink_to_fit
is only a request; there is no guarantee that the library will return the memory.
Each vector
implementation can choose its own allocation strategy. However, it must not allocate new memory until it is forced to do so.
A vector
may be reallocated only when the user performs an insert operation when the size
equals capacity
or by a call to resize
or reserve
with a value that exceeds the current capacity
. How much memory is allocated beyond the specified amount is up to the implementation.
Every implementation is required to follow a strategy that ensures that it is efficient to use push_back
to add elements to a vector
. Technically speaking, the execution time of creating an n-element vector
by calling push_back
n times on an initially empty vector
must never be more than a constant multiple of n.
Exercise 9.35: Explain the difference between a vector
’s capacity
and its size
.
Exercise 9.36: Can a container have a capacity
less than its size
?
Exercise 9.37: Why don’t list
or array
have a capacity
member?
Exercise 9.38: Write a program to explore how vector
s grow in the library you use.
Exercise 9.39: Explain what the following program fragment does:
vector<string> svec;
svec.reserve(1024);
string word;
while (cin >> word)
svec.push_back(word);
svec.resize(svec.size()+svec.size()/2);
Exercise 9.40: If the program in the previous exercise reads 256 words, what is its likely capacity
after it is resize
d? What if it reads 512? 1,000? 1,048?