Using push_back

Note that deque, which like vector offers fast random access to its elements, provides the push_front member even though vector does not. A deque guarantees constant-time insert and delete of elements at the beginning and end of the container. As with vector, inserting elements other than at the front or back of a deque is a potentially expensive operation.

Adding Elements at a Specified Point in the Container

slist.insert(iter, "Hello!"); // insert "Hello!" just before iter

inserts a string with value "Hello" just before the element denoted by iter.

Even though some containers do not have a push_front operation, there is no similar constraint on insert. We can insert elements at the beginning of a container without worrying about whether the container has push_front:

vector<string> svec;
list<string> slist;
// equivalent to calling slist.push_front("Hello!");
slist.insert(slist.begin(), "Hello!");
// no push_front on vector but we can insert before begin()
// warning: inserting anywhere but at the end of a vector might be slow
svec.insert(svec.begin(), "Hello!");

Inserting a Range of Elements

The arguments to insert that appear after the initial iterator argument are analogous to the container constructors that take the same parameters. The version that takes an element count and a value adds the specified number of identical elements before the given position:

svec.insert(svec.end(), 10, "Anna");

This code inserts ten elements at the end of svec and initializes each of those elements to the string "Anna".

The versions of insert that take a pair of iterators or an initializer list insert the elements from the given range before the given position:

vector<string> v = {"quasi", "simba", "frollo", "scar"};
// insert the last two elements of v at the beginning of slist
slist.insert(slist.begin(), v.end() - 2, v.end());
slist.insert(slist.end(), {"these", "words", "will",
                           "go", "at", "the", "end"});
// run-time error: iterators denoting the range to copy from
// must not refer to the same container as the one we are changing
slist.insert(slist.begin(), slist.begin(), slist.end());

When we pass a pair of iterators, those iterators may not refer to the same container as the one to which we are adding elements.

Under the new standard, the versions of insert that take a count or a range return an iterator to the first element that was inserted. (In prior versions of the library, these operations returned void.) If the range is empty, no elements are inserted, and the operation returns its first parameter.

We can use the value returned by insert to repeatedly insert elements at a specified position in the container:

list<string> 1st;
auto iter = 1st.begin();
while (cin >> word)
   iter = 1st.insert(iter, word); // same as calling push_front

Before the loop, we initialize iter to 1st.begin(). The first call to insert takes the string we just read and puts it in front of the element denoted by iter. The value returned by insert is an iterator referring to this new element. We assign that iterator to iter and repeat the while, reading another word. As long as there are words to insert, each trip through the while inserts a new element ahead of iter and reassigns to iter the location of the newly inserted element. That element is the (new) first element. Thus, each iteration inserts an element ahead of the first element in the list.

Using the Emplace Operations

The new standard introduced three new members—emplace_front, emplace, and emplace_back—that construct rather than copy elements. These operations correspond to the push_front, insert, and push_back operations in that they let us put an element at the front of the container, in front of a given position, or at the back of the container, respectively.

// iter refers to an element in c, which holds Sales_data elements
c.emplace_back(); // uses the Sales_data default constructor
c.emplace(iter, "999-999999999"); // uses Sales_data(string)
// uses the Sales_data constructor that takes an ISBN, a count, and a price
c.emplace_front("978-0590353403", 25, 15.99);

9.3.2. Accessing Elements

Each sequential container, including array, has a front member, and all except forward_list also have a back member. These operations return a reference to the first and last element, respectively:

// check that there are elements before dereferencing an iterator or calling front or back
if (!c.empty()) {
    // val and val2 are copies of the value of the first element in c
    auto val = *c.begin(), val2 = c.front();
    // val3 and val4 are copies of the of the last element in c
    auto last = c.end();
    auto val3 = *(--last); // can't decrement forward_list iterators
    auto val4 = c.back();  // not supported by forward_list
}

Two things are noteworthy in this program: The end iterator refers to the (nonexistent) element one past the end of the container. To fetch the last element we must first decrement that iterator. The other important point is that before calling front or back (or dereferencing the iterators from begin or end), we check that c isn’t empty. If the container were empty, the operations inside the if would be undefined.

The Access Members Return References

The members that access elements in a container (i.e., front, back, subscript, and at) return references. If the container is a const object, the return is a reference to const. If the container is not const, the return is an ordinary reference that we can use to change the value of the fetched element:

if (!c.empty()) {
    c.front()  = 42;      // assigns 42 to the first element in c
    auto &v =  c.back();  // get a reference to the last element
    v = 1024;             // changes the element in c
    auto v2 =  c.back();  // v2 is not a reference; it's a copy of c.back()
    v2 = 0;               // no change to the element in c
}

As usual, if we use auto to store the return from one of these functions and we want to use that variable to change the element, we must remember to define our variable as a reference type.

Subscripting and Safe Random Access

9.3.3. Erasing Elements

The pop_front and pop_back Members

The pop_front and pop_back functions remove the first and last elements, respectively. Just as there is no push_front for vector and string, there is also no pop_front for those types. Similarly, forward_list does not have pop_back. Like the element access members, we may not use a pop operation on an empty container.

These operations return void. If you need the value you are about to pop, you must store that value before doing the pop:

while (!ilist.empty()) {
    process(ilist.front()); // do something with the current top of ilist
    ilist.pop_front();      // done; remove the first element
}

The erase members remove element(s) at a specified point in the container. We can delete a single element denoted by an iterator or a range of elements marked by a pair of iterators. Both forms of erase return an iterator referring to the location after the (last) element that was removed. That is, if j is the element following i, then erase(i) will return an iterator referring to j.

As an example, the following loop erases the odd elements in a list:

list<int> lst = {0,1,2,3,4,5,6,7,8,9};
auto it = lst.begin();
while (it != lst.end())
    if (*it % 2)             // if the element is odd
        it = lst.erase(it);  // erase this element
    else
        ++it;

On each iteration, we check whether the current element is odd. If so, we erase that element, setting it to denote the element after the one we erased. If *it is even, we increment it so we’ll look at the next element on the next iteration.

Removing Multiple Elements

The iterator-pair version of erase lets us delete a range of elements:

// delete the range of elements between two iterators
// returns an iterator to the element just after the last removed element
elem1 = slist.erase(elem1, elem2); // after the call elem1 == elem2

The iterator elem1 refers to the first element we want to erase, and elem2 refers to one past the last element we want to remove.

slist.clear(); // delete all the elements within the container
slist.erase(slist.begin(), slist.end()); // equivalent

9.3.4. Specialized forward_list Operations

Figure 9.1. forward_list Specialized Operations

When we add or remove an element, the element before the one we added or removed has a different successor. To add or remove an element, we need access to its predecessor in order to update that element’s links. However, forward_list is a singly linked list. In a singly linked list there is no easy way to get to an element’s predecessor. For this reason, the operations to add or remove elements in a forward_list operate by changing the element after the given element. That way, we always have access to the elements that are affected by the change.

9.3.5. Resizing a Container

9.3.6. Container Operations May Invalidate Iterators

Writing Loops That Change a Container

Loops that add or remove elements of a vector, string, or deque must cater to the fact that iterators, references, or pointers might be invalidated. The program must ensure that the iterator, reference, or pointer is refreshed on each trip through the loop. Refreshing an iterator is easy if the loop calls insert or erase. Those operations return iterators, which we can use to reset the iterator:

// silly loop to remove even-valued elements and insert a duplicate of odd-valued elements
vector<int> vi = {0,1,2,3,4,5,6,7,8,9};
auto iter = vi.begin(); // call begin, not cbegin because we're changing vi
while (iter != vi.end()) {
    if (*iter % 2) {
        iter = vi.insert(iter, *iter);  // duplicate the current element
        iter += 2; // advance past this element and the one inserted before it
    } else
        iter = vi.erase(iter);          // remove even elements
        // don't advance the iterator; iter denotes the element after the one we erased
}

This program removes the even-valued elements and duplicates each odd-valued one. We refresh the iterator after both the insert and the erase because either operation can invalidate the iterator.

After the call to erase, there is no need to increment the iterator, because the iterator returned from erase denotes the next element in the sequence. After the call to insert, we increment the iterator twice. Remember, insert inserts before the position it is given and returns an iterator to the inserted element. Thus, after calling insert, iter denotes the (newly added) element in front of the one we are processing. We add two to skip over the element we added and the one we just processed. Doing so positions the iterator on the next, unprocessed element.

Avoid Storing the Iterator Returned from end

When we add or remove elements in a vector or string, or add elements or remove any but the first element in a deque, the iterator returned by end is always invalidated. Thus, loops that add or remove elements should always call end rather than use a stored copy. Partly for this reason, C++ standard libraries are usually implemented so that calling end() is a very fast operation.

// disaster: the behavior of this loop is undefined
auto begin = v.begin(),
     end = v.end(); // bad idea, saving the value of the end iterator
while (begin != end) {
    // do some processing
    // insert the new value and reassign begin, which otherwise would be invalid
    ++begin;  // advance begin because we want to insert after this element
    begin = v.insert(begin, 42);  // insert the new value
    ++begin;  // advance begin past the element we just added
}

The behavior of this code is undefined. On many implementations, we’ll get an infinite loop. The problem is that we stored the value returned by the end operation in a local variable named end. In the body of the loop, we added an element. Adding an element invalidates the iterator stored in end. That iterator neither refers to an element in v nor any longer refers to one past the last element in v.

Rather than storing the end() iterator, we must recompute it after each insertion:

// safer: recalculate end on each trip whenever the loop adds/erases elements
while (begin != v.end()) {
    // do some processing
    ++begin;  // advance begin because we want to insert after this element
    begin = v.insert(begin, 42);  // insert the new value
    ++begin;  // advance begin past the element we just added
}