9.4. How a vector Grows

Fundamental

To support fast random access, vector elements are stored contiguously—each element is adjacent to the previous element. Ordinarily, we should not care about how a library type is implemented; all we should care about is how to use it. However, in the case of vectors and strings, part of the implementation leaks into its interface.

Given that elements are contiguous, and that the size of the container is flexible, consider what must happen when we add an element to a vector or a string: If there is no room for the new element, the container can’t just add an element somewhere else in memory—the elements must be contiguous. Instead, the container must allocate new memory to hold the existing elements plus the new one, move the elements from the old location into the new space, add the new element, and deallocate the old memory. If vector did this memory allocation and deallocation each time we added an element, performance would be unacceptably slow.

INFO

Exercises Section 9.3.6

Exercise 9.31: The program on page 354 to remove even-valued elements and duplicate odd ones will not work on a list or forward_list. Why? Revise the program so that it works on these types as well.

Exercise 9.32: In the program onpage 354 would it be legal to write the call to insert as follows? If not, why not?

iter = vi.insert(iter, *iter++);

Exercise 9.33: In the final example in this section what would happen if we did not assign the result of insert to begin? Write a program that omits this assignment to see if your expectation was correct.

Exercise 9.34: Assuming vi is a container of ints that includes even and odd values, predict the behavior of the following loop. After you’ve analyzed this loop, write a program to test whether your expectations were correct.

iter = vi.begin();
while (iter != vi.end())
    if (*iter % 2)
        iter = vi.insert(iter, *iter);
    ++iter;

To avoid these costs, library implementors use allocation strategies that reduce the number of times the container is reallocated. When they have to get new memory, vector and string implementations typically allocate capacity beyond what is immediately needed. The container holds this storage in reserve and uses it to allocate new elements as they are added. Thus, there is no need to reallocate the container for each new element.

This allocation strategy is dramatically more efficient than reallocating the container each time an element is added. In fact, its performance is good enough that in practice a vector usually grows more efficiently than a list or a deque, even though the vector has to move all of its elements each time it reallocates memory.

Members to Manage Capacity

The vector and string types provide members, described in Table 9.10, that let us interact with the memory-allocation part of the implementation. The capacity operation tells us how many elements the container can hold before it must allocate more space. The reserve operation lets us tell the container how many elements it should be prepared to hold.

Table 9.10. Container Size Management

INFO

• shrink_to_fit valid only for vector, string, and deque.
• capacity and reserve valid only for vector and string.

Code	Description
c.shrink_to_fit()	Request to reduce capacity() to equal size()
c.capacity()	Number of elements c can have before reallocation is necessary.
c.reserve(n)	Allocate space for at least n elements.

INFO

reserve does not change the number of elements in the container; it affects only how much memory the vector preallocates.

A call to reserve changes the capacity of the vector only if the requested space exceeds the current capacity. If the requested size is greater than the current capacity, reserve allocates at least as much as (and may allocate more than) the requested amount.

If the requested size is less than or equal to the existing capacity, reserve does nothing. In particular, calling reserve with a size smaller than capacity does not cause the container to give back memory. Thus, after calling reserve, the capacity will be greater than or equal to the argument passed to reserve.

As a result, a call to reserve will never reduce the amount of space that the container uses. Similarly, the resize members (§ 9.3.5, p. 352) change only the number of elements in the container, not its capacity. We cannot use resize to reduce the memory a container holds in reserve.

C++11

Under the new library, we can call shrink_to_fit to ask a deque, vector, or string to return unneeded memory. This function indicates that we no longer need any excess capacity. However, the implementation is free to ignore this request. There is no guarantee that a call to shrink_to_fit will return memory.

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

ivec: size: 51 capacity: 100

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.

INFO

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_backn times on an initially empty vector must never be more than a constant multiple of n.

INFO

Exercises Section 9.4

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 vectors 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 resized? What if it reads 512? 1,000? 1,048?