9.3. Sequential Container Operations

The sequential and associative containers differ in how they organize their elements. These differences affect how elements are stored, accessed, added, and removed. The previous section covered operations common to all containers (those listed in Table 9.2 (p. 330)). We’ll cover the operations specific to the sequential containers in the remainder of this chapter.

9.3.1. Adding Elements to a Sequential Container

Fundamental

Excepting array, all of the library containers provide flexible memory management. We can add or remove elements dynamically changing the size of the container at run time. Table 9.5 (p. 343) lists the operations that add elements to a (nonarray) sequential container.

Table 9.5. Operations That Add Elements to a Sequential Container

INFO

These operations change the size of the container; they are not supported by array.
forward_list has special versions of insert and emplace; see § 9.3.4 (p. 350).
push_back and emplace_back not valid for forward_list.
push_front and emplace_front not valid for vector or string.

Code	Description
`c.push_back(t)` `c.emplace_back(args)`	Creates an clement with value `t` or constructed from `args` at the end of `c`. Returns `void`.
`c.push_front(t)` `c.emplace_front(args)`	Creates an clement with value `t` or constructed from `args` at the front of `c`. Returns `void`.
`c.insert(t)` `c.emplace(args)`	Creates an element with value `t` or constructed from `args` before the element denoted by iterator `p`. Returns an iterator referring to the element that was added.
`c.insert(p, n, t)`	Inserts `n` elements with value `t` before the element denoted by iterator `p`. Returns an iterator to the first element inserted; if `n` is zero, returns `p`.
`c.insert(p, b, e)`	Inserts the elements from the range denoted by iterators `b` and `e` before the element denoted by iterator `p`. `b` and `e` may not refer to elements in `c`. Returns an iterator to the first element inserted; if the range is empty, returns `p`.
`c.insert(p, il)`	`il` is a braced list of element values. Inserts the given values before the element denoted by the iterator `p`. Returns an iterator to the first inserted element; if the list is empty returns `p`.

WARNING

Adding elements to a vector, string, or deque potentially invalidates all existing wanna iterators, references, and pointers into the container.

When we use these operations, we must remember that the containers use different strategies for allocating elements and that these strategies affect performance. Adding elements anywhere but at the end of a vector or string, or anywhere but the beginning or end of a deque, requires elements to be moved. Moreover, adding elements to a vector or a string may cause the entire object to be reallocated. Reallocating an object requires allocating new memory and moving elements from the old space to the new.

Using `push_back`

In § 3.3.2 (p. 100) we saw that push_back appends an element to the back of a vector. Aside from array and forward_list, every sequential container (including the string type) supports push_back.

As an example, the following loop reads one string at a time into word:

c++

// read from standard input, putting each word onto the end of container
string word;
while (cin >> word)
    container.push_back(word);

The call to push_back creates a new element at the end of container, increasing the size of container by 1. The value of that element is a copy of word. The type of container can be any of list, vector, or deque.

Because string is just a container of characters, we can use push_back to add characters to the end of the string:

c++

void pluralize(size_t cnt, string &word)
{
    if (cnt > 1)
        word.push_back('s');  // same as word += 's'
}

INFO

Key Concept: Container Elements Are Copies

When we use an object to initialize a container, or insert an object into a container, a copy of that object’s value is placed in the container, not the object itself. Just as when we pass an object to a nonreference parameter (§ 6.2.1, p. 209), there is no relationship between the element in the container and the object from which that value originated. Subsequent changes to the element in the container have no effect on the original object, and vice versa.

Using `push_front`

In addition to push_back, the list, forward_list, and deque containers support an analogous operation named push_front. This operation inserts a new element at the front of the container:

c++

list<int> ilist;
// add elements to the start of ilist
for (size_t ix = 0; ix != 4; ++ix)
    ilist.push_front(ix);

This loop adds the elements 0, 1, 2, 3 to the beginning of ilist. Each element is inserted at the new beginning of the list. That is, when we insert 1, it goes in front of 0, and 2 in front of 1, and so forth. Thus, the elements added in a loop such as this one wind up in reverse order. After executing this loop, ilist holds the sequence 3,2,1,0.

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

The push_back and push_front operations provide convenient ways to insert a single element at the end or beginning of a sequential container. More generally, the insert members let us insert zero or more elements at any point in the container. The insert members are supported for vector, deque, list, and string. forward_list provides specialized versions of these members that we’ll cover in § 9.3.4 (p. 350).

Each of the insert functions takes an iterator as its first argument. The iterator indicates where in the container to put the element(s). It can refer to any position in the container, including one past the end of the container. Because the iterator might refer to a nonexistent element off the end of the container, and because it is useful to have a way to insert elements at the beginning of a container, element(s) are inserted before the position denoted by the iterator. For example, this statement

c++

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:

c++

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!");

WARNING

It is legal to insert anywhere in a vector, deque, or string. However, doing so can be an expensive operation.

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:

c++

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:

c++

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.

C++11

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.

Using the Return from `insert`

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

c++

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

INFO

It is important to understand how this loop operates—in particular, to understand why the loop is equivalent to 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.

C++11

When we call a push or insert member, we pass objects of the element type and those objects are copied into the container. When we call an emplace member, we pass arguments to a constructor for the element type. The emplace members use those arguments to construct an element directly in space managed by the container. For example, assuming c holds Sales_data (§ 7.1.4, p. 264) elements:

c++

// construct a Sales_data object at the end of c
// uses the three-argument Sales_data constructor
c.emplace_back("978-0590353403", 25, 15.99);
// error: there is no version of push_back that takes three arguments
c.push_back("978-0590353403", 25, 15.99);
// ok: we create a temporary Sales_data object to pass to push_back
c.push_back(Sales_data("978-0590353403", 25, 15.99));

The call to emplace_back and the second call to push_back both create new Sales_data objects. In the call to emplace_back, that object is created directly in space managed by the container. The call to push_back creates a local temporary object that is pushed onto the container.

The arguments to an emplace function vary depending on the element type. The arguments must match a constructor for the element type:

c++

// 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);

INFO

The emplace functions construct elements in the container. The arguments to these functions must match a constructor for the element type.

INFO

Exercises Section 9.3.1

Exercise 9.18: Write a program to read a sequence of strings from the standard input into a deque. Use iterators to write a loop to print the elements in the deque.

Exercise 9.19: Rewrite the program from the previous exercise to use a list. List the changes you needed to make.

Exercise 9.20: Write a program to copy elements from a list<int> into two deques. The even-valued elements should go into one deque and the odd ones into the other.

Exercise 9.21: Explain how the loop from page 345 that used the return from insert to add elements to a list would work if we inserted into a vector instead.

Exercise 9.22: Assuming iv is a vector of ints, what is wrong with the following program? How might you correct the problem(s)?

c++

vector<int>::iterator iter = iv.begin(),
                      mid = iv.begin() + iv.size()/2;
while (iter != mid)
    if (*iter == some_val)
        iv.insert(iter, 2 * some_val);

9.3.2. Accessing Elements

Fundamental

Table 9.6 lists the operations we can use to access elements in a sequential container. The access operations are undefined if the container has no elements.

Table 9.6. Operations to Access Elements in a Sequential Container

INFO

at and subscript operator valid only for string, vector, deque, and array.
back not valid for forward_list.

Code	Description
`c.back()`	Returns a reference to the last element in `c`. Undefined if `c` is empty.
`c.front()`	Returns a reference to the first element in `c`. Undefined if `c` is empty.
`c[n]`	Returns a reference to the element indexed by the unsigned integral value `n`. Undefined if `n >= c.size()`.
`c.at(n)`	Returns a reference to the element indexed by `n`. If the index is out of range, throw’s an `out_of_range` exception.

WARNING

Calling front or back on an empty container, like using a subscript that is out of range, is a serious programming error.

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:

c++

// 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
}

This program obtains references to the first and last elements in c in two different ways. The direct approach is to call front or back. Indirectly, we can obtain a reference to the same element by dereferencing the iterator returned by begin or decrementing and then dereferencing the iterator returned by end.

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:

c++

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

The containers that provide fast random access (string, vector, deque, and array) also provide the subscript operator (§ 3.3.3, p. 102). As we’ve seen, the subscript operator takes an index and returns a reference to the element at that position in the container. The index must be “in range,” (i.e., greater than or equal to 0 and less than the size of the container). It is up to the program to ensure that the index is valid; the subscript operator does not check whether the index is in range. Using an out-of-range value for an index is a serious programming error, but one that the compiler will not detect.

If we want to ensure that our index is valid, we can use the at member instead. The at member acts like the subscript operator, but if the index is invalid, at throws an out_of_range exception (§ 5.6, p. 193):

c++

vector<string> svec; // empty vector
cout << svec[0];     // run-time error: there are no elements in svec!
cout << svec.at(0);  // throws an out_of_range exception

INFO

Exercises Section 9.3.2

Exercise 9.23: In the first program in this section on page 346, what would the values of val, val2, val3, and val4 be if c.size() is 1?

Exercise 9.24: Write a program that fetches the first element in a vector using at, the subscript operator, front, and begin. Test your program on an empty vector.

9.3.3. Erasing Elements

Fundamental

Just as there are several ways to add elements to a (nonarray) container there are also several ways to remove elements. These members are listed in Table 9.7.

Table 9.7. erase Operations on Sequential Containers

INFO

These operations change the size of the container and so are not supported by array.
forward_list has a special version of erase; see § 9.3.4 (p. 350).
pop_back not valid for forward_list; pop_front not valid for vector and string.

Code	Description
`c.pop_back()`	Removes last element in `c`. Undefined if `c` is empty. Returns `void`.
`c.pop_front()`	Removes first element in `c`. Undefined if `c` is empty. Returns `void`.
`c.erase(p)`	Removes the element denoted by the iterator `p` and returns an iterator to the element after the one deleted or the off-the-end iterator if `p` denotes the last element. Undefined if `p` is the off-the-end iterator.
`c.erase(b, e)`	Removes the range of elements denoted by the iterators `b` and `e`. Returns an iterator to the element after the last one that was deleted, or an off-the-end iterator if `e` is itself an off-the-end iterator.
`c.clear()`	Removes all the elements in `c`. Returns `void`.

WARNING

Removing elements anywhere but the beginning or end of a deque invalidates all iterators, references, and pointers. Iterators, references, and pointers to elements after the erasure point in a vector or string are invalidated.

WARNING

The members that remove elements do not check their argument(s). The programmer must ensure that element(s) exist before removing them.

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:

c++

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

Removing an Element from within the Container

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:

c++

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:

c++

// 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.

To delete all the elements in a container, we can either call clear or pass the iterators from begin and end to erase:

c++

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

INFO

Exercises Section 9.3.3

Exercise 9.25: In the program on page 349 that erased a range of elements, what happens if elem1 and elem2 are equal? What if elem2 or both elem1 and elem2 are the off-the-end iterator?

Exercise 9.26: Using the following definition of ia, copy ia into a vector and into a list. Use the single-iterator form of erase to remove the elements with odd values from your list and the even values from your vector.

c++

int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };

9.3.4. Specialized `forward_list` Operations

Advanced

To understand why forward_list has special versions of the operations to add and remove elements, consider what must happen when we remove an element from a singly linked list. As illustrated in Figure 9.1, removing an element changes the links in the sequence. In this case, removing elem₃ changes elem₂; elem₂ had pointed to elem₃, but after we remove elem₃, elem₂ points to elem₄.

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.

Because these operations behave differently from the operations on the other containers, forward_list does not define insert, emplace, or erase. Instead it defines members (listed in Table 9.8) named insert_after, emplace_after, and erase_after. For example, in our illustration, to remove elem₃, we’d call erase_after on an iterator that denoted elem₂. To support these operations, forward_list also defines before_begin, which returns an off-the-beginning iterator. This iterator lets us add or remove elements “after” the nonexistent element before the first one in the list.

Table 9.8. Operations to Insert or Remove Elements in a forward_list

Code	Description
`lst.before_begin()` `lst.cbefore_begin()`	Iterator denoting the nonexistent element just before the beginning of the list. This iterator may not be dereferenced. `cbefore_begin()` returns a `const_iterator`.
`lst.insert_after(p, t)` `lst.insert_after(p, n, t)` `lst.insert_after(p, b, e)` `lst.insert_after(p, il)`	Inserts element(s) after the one denoted by iterator `p`. `t` is an object, `n` is a count, `b` and `e` are iterators denoting a range (`b` and `e` must not refer to `lst`), and `il` is a braced list. Returns an iterator to the fast inserted element. If the range is empty, returns `p`. Undefined if `p` is the off-the-end iterator.
`lst.emplace_after(p, args)`	Uses `args` to construct an element after the one denoted by iterator `p`. Returns an iterator to the new element. Undefined if `p` is the off-the-end iterator.
`lst.erase_after(p)` `lst.erase_after(b, e)`	Removes the element after the one denoted by iterator `p` or the range of elements from the one after the iterator `b` up to but not including the one denoted by `e`. Returns an iterator to the element after the one deleted, or the off-the-end iterator if there is no such element. Undefined if `p` denotes the last element in `lst` or is the off-the-end iterator.

When we add or remove elements in a forward_list, we have to keep track of two iterators—one to the element we’re checking and one to that element’s predecessor. As an example, we’ll rewrite the loop from page 349 that removed the odd-valued elements from a list to use a forward_list:

c++

forward_list<int> flst = {0,1,2,3,4,5,6,7,8,9};
auto prev = flst.before_begin(); // denotes element "off the start" of flst
auto curr = flst.begin();        // denotes the first element in flst
while (curr != flst.end()) {     // while there are still elements to process
    if (*curr % 2)                     // if the element is odd
        curr = flst.erase_after(prev); // erase it and move curr
    else {
        prev = curr;            // move the iterators to denote the next
        ++curr;                 // element and one before the next element
    }
}

Here, curr denotes the element we’re checking, and prev denotes the element before curr. We call begin to initialize curr, so that the first iteration checks whether the first element is even or odd. We initialize prev from before_begin, which returns an iterator to the nonexistent element just before curr.

When we find an odd element, we pass prev to erase_after. This call erases the element after the one denoted by prev; that is, it erases the element denoted by curr. We reset curr to the return from erase_after, which makes curr denote the next element in the sequence and we leave prev unchanged; prev still denotes the element before the (new) value of curr. If the element denoted by curr is not odd, then we have to move both iterators, which we do in the else.

INFO

Exercises Section 9.3.4

Exercise 9.27: Write a program to find and remove the odd-valued elements in a forward_list<int>.

Exercise 9.28: Write a function that takes a forward_list<string> and two additional string arguments. The function should find the first string and insert the second immediately following the first. If the first string is not found, then insert the second string at the end of the list.

9.3.5. Resizing a Container

With the usual exception of arrays, we can use resize, described in Table 9.9, to make a container larger or smaller. If the current size is greater than the requested size, elements are deleted from the back of the container; if the current size is less than the new size, elements are added to the back of the container:

c++

list<int> ilist(10, 42); // ten ints: each has value 42
ilist.resize(15);     // adds five elements of value 0 to the back of ilist
ilist.resize(25, -1); // adds ten elements of value -1 to the back of ilist
ilist.resize(5);      // erases 20 elements from the back of ilist

Table 9.9. Sequential Container Size Operations

INFO

resize not valid for array.

Code	Description
`c.resize(n)`	Resize `c` so that it has `n` elements. If `n < c.size()`, the excess elements are discarded. If new elements must be added, they are value initialized.
`c.resize(n, t)`	Resize `c` to have `n` elements. Any elements added have value `t`.

The resize operation takes an optional element-value argument that it uses to initialize any elements that are added to the container. If this argument is absent, added elements are value initialized (§ 3.3.1, p. 98). If the container holds elements of a class type and resize adds elements, we must supply an initializer or the element type must have a default constructor.

WARNING

If resize shrinks the container, then iterators, references, and pointers to the deleted elements are invalidated; resize on a vector, string, or deque potentially invalidates all iterators, pointers, and references.

INFO

Exercises Section 9.3.5

Exercise 9.29: Given that vec holds 25 elements, what does vec.resize(100) do? What if we next wrote vec.resize(10)?

Exercise 9.30: What, if any, restrictions does using the version of resize that takes a single argument place on the element type?

9.3.6. Container Operations May Invalidate Iterators

Fundamental

Operations that add or remove elements from a container can invalidate pointers, references, or iterators to container elements. An invalidated pointer, reference, or iterator is one that no longer denotes an element. Using an invalidated pointer, reference, or iterator is a serious programming error that is likely to lead to the same kinds of problems as using an uninitialized pointer (§ 2.3.2, p. 54).

After an operation that adds elements to a container

Iterators, pointers, and references to a vector or string are invalid if the container was reallocated. If no reallocation happens, indirect references to elements before the insertion remain valid; those to elements after the insertion are invalid.
Iterators, pointers, and references to a deque are invalid if we add elements anywhere but at the front or back. If we add at the front or back, iterators are invalidated, but references and pointers to existing elements are not.
Iterators, pointers, and references (including the off-the-end and the before-the-beginning iterators) to a list or forward_list remain valid,

It should not be surprising that when we remove elements from a container, iterators, pointers, and references to the removed elements are invalidated. After all, those elements have been destroyed. After we remove an element,

All other iterators, references, or pointers (including the off-the-end and the before-the-beginning iterators) to a list or forward_list remain valid.
All other iterators, references, or pointers to a deque are invalidated if the removed elements are anywhere but the front or back. If we remove elements at the back of the deque, the off-the-end iterator is invalidated but other iterators, references, and pointers are unaffected; they are also unaffected if we remove from the front.
All other iterators, references, or pointers to a vector or string remain valid for elements before the removal point. Note: The off-the-end iterator is always invalidated when we remove elements.

WARNING

It is a serious run-time error to use an iterator, pointer, or reference that has been invalidated.

INFO

Advice: Managing Iterators

When you use an iterator (or a reference or pointer to a container element), it is a good idea to minimize the part of the program during which an iterator must stay valid.

Because code that adds or removes elements to a container can invalidate iterators, you need to ensure that the iterator is repositioned, as appropriate, after each operation that changes the container. This advice is especially important for vector, string, and deque.

Writing Loops That Change a Container

Tricky

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:

c++

// 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`

Tricky

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.

As an example, consider a loop that processes each element and adds a new element following the original. We want the loop to ignore the added elements, and to process only the original elements. After each insertion, we’ll position the iterator to denote the next original element. If we attempt to “optimize” the loop, by storing the iterator returned by end(), we’ll have a disaster:

c++

// 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.

TIP

Don’t cache the iterator returned from end() in loops that insert or delete elements in a deque, string, or vector.

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

c++

// 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
}

Chapter 2. Variables and Basic Types

Chapter 3. Strings, Vectors, and Arrays

Chapter 4. Expressions

Chapter 5. Statements

Chapter 6. Functions

Chapter 7. Classes

Chapter 8. The IO Library

Chapter 9. Sequential Containers

Chapter 10. Generic Algorithms

Chapter 11. Associative Containers

Chapter 12. Dynamic Memory

Chapter 13. Copy Control

Chapter 14. Overloaded Operations and Conversions

Chapter 15. Object-Oriented Programming

Chapter 16. Templates and Generic Programming

Chapter 17. Specialized Library Facilities

Chapter 18. Tools for Large Programs

Chapter 19. Specialized Tools and Techniques

A.2. A Brief Tour of the Algorithms

A.3. Random Numbers