Efficient use of std::vector requires that we reserve space in advance. While we often do not know the exact size of our vector, we do have some information about the scale of the problem. Which is why we choose to preallocate memory ahead of time.
This is where issues come out, frequently leading to surprising results. Look at the snippet below. You might think that the code gives you a vector with elements 0,1,2. But you will be mistaken.
#include <iostream>
#include <vector>
// C++17
int main(){
// WRONG !
auto v = std::vector<int>(3);
v.push_back(0);
v.push_back(1);
v.push_back(2);
for(auto e : v)
std::cout << e << ' '; // 0 0 0 0 1 2
}
std::vector<int> (3) gives you a vector of 3 elements - all with a default integer value 0. After that, it pushes 0, 1 and 2 to the end of the vector. The resulting vector is thus 0 0 0 0 1 2. Notice that we did not reserve space for 3 elements. In reality, we called the constructor with 3 default integer instances with the value 0. Afterward, we pushed back some more elements.
To correct the mistake we have to remove the count from the constructor and instead call std::vector::reserve(). See the snippet below:
#include <iostream>
#include <vector>
// C++17
int main(){
// CORRECT !
auto v = std::vector<int>{};
v.reserve(3);
v.push_back(0);
v.push_back(1);
v.push_back(2);
for(auto e : v)
std::cout << e << ' '; // 0 1 2
}
Tip: The usefulness of testing
The example above demonstrates why testing is so useful. If we had written a unit test for the scenario above, we would have spotted the problem immediately. The test would have failed since the contents of the vector wouldn't have met our expectations.
Explore I: Properties of std::vector and the preallocated buffer
1. You might have noticed that std::vector has a method size() which gives you the number of elements of the vector and a method capacity() which gives you the size of its internal buffer. Let's push_back another element into our vector, i.e. its size() is now four. What about its capacity()? Is size() or capacity() likely to produce a larger value?
2. Which method of std::vector should be used to reduce unused capacity? Do we have 100% guarantee that the unused capacity is going to be reduced by this method?
Explore II: Generating ranges with STL
1. STL offers alternative ways to generate a range of elements. One of them is std::iota. The snippet below generates the range 0 1 2. Notice that we first have to create a vector 0 0 0, only after are we allowed to call std::iota.
auto v = std::vector<int>(3); // 0 0 0
std::iota(std::begin(v), std::end(v), 0); // 0 1 2
How would you generate the sequence -1 0 1?
2. Can we generate an arbitrary sequence with std::iota?
3. STL offers a more flexible alternative to range generation, namely std::generate. This function accepts a user-defined rule for range generation, most commonly in the form of a lambda expression.
