Inserting and erasing in a std::vector

vec.push_back(t) adds an item to the end of the vector. There is no corresponding .push_front() member function, because as you can see from the diagram at the start of this section, there's no efficient way to push anything onto the front of a vector.

vec.emplace_back(args...) is a perfect-forwarding variadic function template that acts just like .push_back(t), except that, instead of placing a copy of t at the end of the vector, it places a T object constructed as if by T(args...).

Both push_back and emplace_back have what is called "amortized constant time" performance. To see what this means, consider what would happen to a naive vector if you call v.emplace_back() a hundred times in a row. With each call, the vector needs to get just a little bit bigger; so it reallocates its underlying array and moves all v.size() elements from the old array to the new one. Soon you'd be spending more time copying old data from place to place than you're spending actually "pushing back" new data! Fortunately, std::vector is smart enough to avoid this trap. Whenever an operation such as v.emplace_back() causes reallocation, the vector won't make room for just capacity() + 1 elements in the new array; it will make room for k * capacity() elements (where k is 2 for libc++ and libstdc++, and approximately 1.5 for Visual Studio). So, although reallocation gets more and more expensive as the vector grows, you do fewer and fewer reallocations per push_back--and so the cost of a single push_back is constant, on average. This trick is known as geometric resizing.

vec.insert(it, t) adds an item into the middle of the vector, at the position indicated by the iterator it. If it == vec.end(), then this is equivalent to push_back; if it == vec.begin(), then this is a poor man's version of push_front. Notice that, if you insert anywhere but the end of the vector, all the elements after the insertion point in the underlying array will get shifted over to make room; this can be expensive.

There are several different overloads of .insert(). Generally speaking, none of these will be useful to you, but you might want to be aware of them in order to interpret the cryptic error messages (or cryptic runtime bugs) that will show up if you accidentally provide the wrong arguments to .insert() and overload resolution ends up picking one of these instead of the one you expected:

    std::vector<int> v = {1, 2};
    std::vector<int> w = {5, 6};

    // Insert a single element.
    v.insert(v.begin() + 1, 3);
    assert((v == std::vector{1, 3, 2}));

    // Insert n copies of a single element.
    v.insert(v.end() - 1, 3, 4);
    assert((v == std::vector{1, 3, 4, 4, 4, 2}));

    // Insert a whole range of elements.
    v.insert(v.begin() + 3, w.begin(), w.end());
    assert((v == std::vector{1, 3, 4, 5, 6, 4, 4, 2}));

    // Insert a braced list of elements.
    v.insert(v.begin(), {7, 8});
    assert((v == std::vector{7, 8, 1, 3, 4, 5, 6, 4, 4, 2}));

vec.emplace(it, args...) is to insert as emplace_back is to push_back: it's a perfect-forwarding version of the C++03 function. Prefer emplace and emplace_back over insert and push_back, when possible.

vec.erase(it) erases a single item from the middle of a vector, at the position indicated by the iterator it. There's also a two-iterator version, vec.erase(it, it), which erases a contiguous range of items. Notice that this two-iterator version is the same one we used in the erase-remove idiom in the previous chapter.

To delete just the last element from the vector, you could use either vec.erase(vec.end()-1) or vec.erase(vec.end()-1, vec.end()); but since this is a common operation, the standard library provides a synonym in the form of vec.pop_back(). You can implement a dynamically growable stack using nothing more than the push_back() and pop_back() methods of std::vector.