Section 9.3. Sequence Container Operations

9.3. Sequence Container Operations

Each sequential container defines a set of useful typedefs and supports operations that let us

• Add elements to the container

• Delete elements from the container

• Determine the size of the container

• Fetch the first and last elements from the container, if any

9.3.1. Container Typedefs

We've used three of the container-defined types: size_type, iterator, and const_iterator. Each container defines these types, along with several others shown in Table 9.5.

Table 9.5. Container-Defined Typedefs

size_type	Unsigned integral type large enough to hold size of largest possible container of this container type
iterator	Type of the iterator for this container type
const_iterator	Type of the iterator that can read but not write the elements
reverse_iterator	Iterator that addresses elements in reverse order
const_reverse_iterator	Reverse iterator that can read but not write the elements
difference_type	Signed integral type large enough to hold the difference, which might be negative, between two iterators
value_type	Element type
reference	Element's lvalue type; synonym for value_type&
const_reference	Element's const lvalue type; same as const value_type&

We'll have more to say about reverse iterators in Section 11.3.3 (p. 412), but briefly, a reverse iterator is an iterator that goes backward through a container and inverts the iterator operations: For example, saying ++ on a reverse iterator yields the previous element in the container.

The last three types in Table 9.5 on the facing page let us use the type of the elements stored in a container without directly knowing what that type is. If we need the element type, we refer to the container's value_type. If we need a reference to that type, we use reference or const_reference. The utility of these element-related typedefs will be more apparent when we define our own generic programs in Chapter 16.

Expressions that use a container-defined type can look intimidating:

      // iter is the iterator type defined by list<string>      list<string>::iterator iter;      // cnt is the difference_type type defined by vector<int>      vector<int>::difference_type cnt; 

The declaration of iter uses the scope operator to say that we want the name on the right-hand side of the :: from the scope of the left-hand side. The effect is to declare that iter has whatever type is defined for the iterator member from the list class that holds elements of type string.

Exercises Section 9.3.1

Exercise 9.16:	What type should be used as the index into a vector of ints?
Exercise 9.17:	What type should be used to read the elments in a list of strings?

9.3.2. begin and end Members

The begin and end operations yield iterators that refer to the first and one past the last element in the container. These iterators are most often used to form an iterator range that encompasses all the elements in the container.

Table 9.6. Container begin and end Operations

c.begin()	Yields an iterator referring to the first element in c
c.end()	Yields an iterator referring to the one past the last element in c
c.rbegin()	Yields a reverse iterator referring to the last element in c
c.rend()	Yields a reverse iterator referring one past (i.e., before) the first element in c

There are two different versions of each of these operations: One is a const member (Section 7.7.1, p. 260) and the other is nonconst. The return type of these operations varies on whether the container is const. In each case, if the container is nonconst, then the result's type is iterator or reverse_iterator. If the object is const, then the type is prefixed by const_, that is, const_iterator or const_reverse_iterator. We cover reverse iterators in Section 11.3.3 (p. 412).

9.3.3. Adding Elements to a Sequential Container

In Section 3.3.2 (p. 94) we saw one way to add elements: push_back. Every sequential container supports push_back, which appends an element to the back of the container. The following loop reads one string at a time into text_word:

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

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

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

      list<int> ilist;      // add elements at the end of ilist      for (size_t ix = 0; ix != 4; ++ix)          ilist.push_back(ix); 

uses push_back to add the sequence 0, 1, 2, 3 to the end of ilist.

Alternatively, we could use push_front

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

to add the elements 0, 1, 2, 3 to the beginning of ilist. Because each element is inserted at the new beginning of the list, they wind up in reverse order. After executing both loops, ilist holds the sequence 3,2,1,0,0,1,2,3.

Key Concept: Container Elements Are Copies

When we add an element to a container, we do so by copying the element value into the container. Similarly, when we initialize a container by providing a range of elements, the new container contains copies of the original range of elements. There is no relationship between the element in the container and the value from which it was copied. Subsequent changes to the element in the container have no effect on the value that was copied, and vice versa.

Table 9.7. Operations that Add Elements to a Sequential Container

c.push_back(t)	Adds element with value t to the end of c. Returns void.
c.push_front(t)	Adds element with value t to front of c. Returns void. Valid only for list or deque.
c.insert(p,t)	Inserts element with value t before the element referred to 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 referred to by iterator p. Returns void.
c.insert(p,b,e)	Inserts elements in the range denoted by iterators b and e before the element referred to by iterator p. Returns void.

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, insert allows us to insert elements at any particular point in the container. There are three versions of insert. The first takes an iterator and an element value. The iterator refers to the position at which to insert the value. We could use this version of insert to insert an element at the beginning of a container:

      vector<string> svec;      list<string> slist;      string spouse("Beth");      // equivalent to calling slist.push_front (spouse);      slist.insert(slist.begin(), spouse);      // no push_front on vector but we can insert before begin()      // warning: inserting anywhere but at the end of a vector is an expensive operation      svec.insert(svec.begin(), spouse); 

The value is inserted before the position referred to by the iterator. The iterator 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, insert inserts before the position rather than after it. This code

      slist.insert(iter, spouse); // insert spouse just before iter 

inserts a copy of spouse just before the element referred to by iter.

This version of insert returns an iterator referring to the newly inserted element. We could use the return value to repeatedly insert elements at a specified position in the container:

      list<string> lst;      list<string>::iterator iter = lst.begin();      while (cin >> word)         iter = lst.insert(iter, word); // same as calling push_front 

It is important to understand thoroughly how this loop operatesin particular to understand why we say that the loop is equivalent to calling push_front.

Before the loop, we initialize iter to lst.begin(). Because the list is empty, lst.begin() and lst.end() are equal, so iter refers one past the end of the (empty) list. The first call to insert puts the element we just read in front of the element referred to by iter. The value returned by insert is an iterator referring to this new element, which is now the first, and only, element in lst. 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 value of the newly inserted element. That element is always the first element, so each iteration inserts an element ahead of the first element in the list.

Inserting a Range of Elements

A second form of insert adds a specified number of identical elements at an indicated 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 final form of insert adds a range of elements denoted by an iterator pair into the container. For example, given the following array of strings

      string sarray[4] = {"quasi", "simba", "frollo", "scar"}; 

we can insert all or a subset of the array elements into our list of strings:

      // insert all the elements in sarray at end of slist      slist.insert(slist.end(), sarray, sarray+4);      list<string>::iterator slist_iter = slist.begin();      // insert last two elements of sarray before slist_iter      slist.insert(slist_iter, sarray+2, sarray+4); 

Inserting Elements Can Invalidate Iterators

As we'll see in Section 9.4 (p. 330), adding elements to a vector can cause the entire container to be relocated. If the container is relocated, then all iterators into the container are invalidated. Even if the vector does not have to be relocated, any iterator to an element after the one inserted is invalidated.

Iterators may be invalidated after doing any insert or push operation on a vector or deque. When writing loops that insert elements into a vector or a deque, the program must ensure that the iterator is refreshed on each trip through the loop.

Avoid Storing the Iterator Returned from end

When we add elements to a vector or deque, some or all of the iterators may be invalidated. It is safest to assume that all iterators are invalid. This advice is particularly true for the iterator returned by end. That iterator is always invalidated by any insertion anywhere in the container.

As an example, consider a loop that reads each element, processes it and adds a new element following the original. We want the loop to process each original element. We'll use the form of insert that takes a single value and returns an iterator to the element that was just inserted. After each insertion, we'll increment the iterator that is returned so that the loop is positioned to operate on the next original element. If we attempt to "optimize" the loop, by storing an iterator to the end(), we'll have a disaster:

      vector<int>::iterator first = v.begin(),                            last = v.end(); // cache end iterator      // diaster: behavior of this loop is undefined      while (first != last) {          // do some processing          // insert new value and reassign first, which otherwise would be invalid          first = v.insert(first, 42);          ++first;  // advance first just past the element we 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 last. In the body of the loop, we add an element. Adding an element invalidates the iterator stored in last. That iterator neither refers to an element in v nor any longer refers to one past the last element in v.

Don't cache the iterator returned from end. Inserting or deleting elements in a deque or vector will invalidate the cached iterator.

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 (first != v.end()) {          // do some processing          first = v.insert(first, 42); // insert new value          ++first; // advance first just past the element we added      } 

9.3.4. Relational Operators

Each container supports the relational operators (Section 5.2, p. 152) that can be used to compare two containers. The containers must be the same kind of container and must hold elements of the same type. We can compare a vector<int> only with another vector<int>. We cannot compare a vector<int> with a list<int> or a vector<double>.

Exercises Section 9.3.3

Exercise 9.18:	Write a program to copy elements from a list of ints into two deques. The list elements that are even should go into one deque and those that are odd into the second.
Exercise 9.19:	Assuming iv is a vector of ints, what is wrong with the following program? How might you correct the problem(s)? vector<int>::iterator mid = iv.begin() + iv.size()/2; while (vector<int>::iterator iter != mid) if (iter == some_val) iv.insert(iter, 2 * some_val);

Comparing two containers is based on a pairwise comparison of the elements of the containers. The comparison uses the same relational operator as defined by the element type: Comparing two containers using != uses the != operator for the element type. If the element type doesn't support the operator, then the containers cannot be compared using that operator.

These operators work similarly to the string relationals (Section 3.2.3, p. 85):

• If both containers are the same size and all the elements are equal, then the two containers are equal; otherwise, they are unequal.

• If the containers have different sizes but every element of the shorter one is equal to the corresponding element of the longer one, then the shorter one is considered to be less than the other.

• If neither container is an initial subsequence of the other, then the comparison depends on comparing the first unequal elements.

The easiest way to understand these operators is by studying examples:

      /*                   ivec1: 1 3 5 7 9 12                   ivec2: 0 2 4 6 8 10 12                   ivec3: 1 3 9                   ivec4: 1 3 5 7                   ivec5: 1 3 5 7 9 12      */      // ivec1 and ivec2 differ at element[0]: ivec1 greater than ivec2      ivec1 < ivec2 // false      ivec2 < ivec1 // true      // ivec1 and ivec3 differ at element[2]: ivec1 less than ivec3      ivec1 < ivec3 // true      // all elements equal, but ivec4 has fewer elements, so ivec1 is greater than ivec4      ivec1 < ivec4 // false      ivec1 == ivec5 // true; each element equal and same number of elements      ivec1 == ivec4 // false; ivec4 has fewer elements than ivec1      ivec1 != ivec4 // true; ivec4 has fewer elements than ivec1 

Relational Operators Use Their Element's Relational Operator

We can compare two containers only if the same relational operator defined for the element types.

Each container relational operator executes by comparing pairs of elements from the two containers:

      ivec1 < ivec2 

Assuming ivec1 and ivec2 are vector<int>, then this comparison uses the built-in int less-than operator. If the vectors held strings, then the string less-than operator would be used.

If the vectors held objects of the Sales_item type that we used in Section 1.5 (p. 20), then the comparison would be illegal. We did not define the relational operators for Sales_item. If we have two containers of Sales_items, we could not compare them:

      vector<Sales_item> storeA;      vector<Sales_item> storeB;      if (storeA < storeB) // error: Sales_item has no less-than operator 

Exercises Section 9.3.4

Exercise 9.20:	Write a program to compare whether a vector<int> contains the same elements as a list<int>.
Exercise 9.21:	Assuming c1 and c2 are containers, what constraints does the following usage place on the element types in c1 and c2? if (c1 < c2) What, if any, constraints are there on c1 and c2?

9.3.5. Container Size Operations

Each container type supports four size-related operations. We used size and empty in Section 3.2.3 (p. 83): size returns the number of elements in the container; empty returns a bool that is true if size is zero and false otherwise.

The resize operation changes the number of elements in the container. If the current size is greater than the new size, then elements are deleted from the back of the container. If the current size is less than the new size, then elements are added to the back of the container:

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

The resize operation takes an optional element-value argument. If this argument is present, then any newly added elements receive this value. If this argument is absent, then any new elements are value initialized (Section 3.3.1, p. 92).

resize can invalidate iterators. A resize operation on a vector or deque potentially invalidates all iterators.

For any container type, if resize shrinks the container, then any iterator to an element that is deleted is invalidated.

Table 9.8. Sequential Container Size Operations

c.size()	Returns the number of elements in c. Return type is c::size_type.
c.max_size()	Returns maximum number of elements c can contain. Return type is c::size_type.
c.empty()	Returns a bool that indicates whether size is 0 or not.
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.

Exercises Section 9.3.5

Exercise 9.22:	Given that vec holds 25 elements, what does vec.resize(100) do? What if we next wrote vec.resize(10)?
Exercise 9.23:	What, if any, restrictions does using resize with a single size argument place on the element types?

9.3.6. Accessing Elements

If a container is not empty, then the front and back members return references bound to the first or last elements in the container:

      // check that there are elements before dereferencing an iterator      // or calling front or back      if (!ilist.empty()) {          // val and val2 refer to the same element          list<int>::reference val = *ilist.begin();          list<int>::reference val2 = ilist.front();          // last and last2 refer to the same element          list<int>::reference last = *--ilist.end();          list<int>::reference last2 = ilist.back(); } 

This program uses two different approaches to fetch a reference to the first and last elements in ilist. 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 the element one before the iterator returned by end. Two things are noteworthy in this program: The end iterator refers "one past the end" of the container so 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 ilist isn't empty. If the list were empty all of the operations in the if would be undefined.

When we introduced subscripting in Section 3.3.2 (p. 94), we noted that the programmer must ensure that an element exists at the indicated subscript location. The subscript operator itself does not check. The same caution applies to using the front or back operations. If the container is empty, these operations yield an undefined result. If the container has only one element, then front and back each return a reference to that element.

Using a subscript that is out-of-range or calling front or back on an empty container are serious programming errors.

Table 9.9. Operations to Access Elements in a Sequential Container

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 n. Undefined if n <0 or n >= c.size(). Valid only for vector and deque.
c.at(n)	Returns a reference to the element indexed by n. If index is out of range, throws out_of_range exception. Valid only for vector and deque.

An alternative to subscripting is to use the at member. This function acts like the subscript operation but if the index is invalid, at throws an out_of_range exception (Section 6.13, p. 215):

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

Exercises Section 9.3.6

Exercise 9.24:

Write a program that fetches the first element in a vector. Do so using at, the subscript operator, front, and begin. Test the program on an empty vector.

9.3.7. Erasing Elements

Recall that there is both a general insert operation that inserts anywhere in the container and specific push_front and push_back operations to add elements only at the front or back. Similarly, there is a general erase and specific pop_front and pop_back operations to remove elements.

Removing the First or Last Element

The pop_front and pop_back functions remove the first and last elements in the container. There is no pop_front operation for vectors. These operations remove the indicated element and return void.

One common use of pop_front is to use it together with front to process a container as a stack:

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

This loop is pretty simple: We use front to get a value to operate on and then call pop_front to remove that element from the list.

The pop_front and pop_back return void; they do not return the value of the element popped. To examine that value, it is necessary to call front or back prior to popping the element.

Table 9.10. Operations to Remove Elements from a Sequential Container

c.erase(p)	Removes element referred to by the iterator p. Returns an iterator referring to the element after the one deleted, or an off-the-end iterator if p referred to the last element. Undefined if p is an off-the-end iterator.
c.erase(b,e)	Removes the range of elements denoted by the iterators b and e. Returns an iterator referring after the last one in the range 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.
c.pop_back()	Removes the last element in c. Returns void. Undefined if c is empty.
c.pop_front()	Removes the first element in c. Returns void. Undefined if c is empty. Valid only for list or deque.

Removing an Element From within the Container

The more general way to remove an element, or range of elements, is through erase. There are two versions of erase: We can delete a single element referred to 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 element or range that was removed. That is, if element j is the element immediately after i and we erase element i from the container, then the iterator returned will refer to j.

As usual, the erase operations don't check their argument(s). It is up to the programmer to ensure that the iterator or iterator range is valid.

The erase operation is often used after finding an element that should be removed from the container. The easiest way to find a given element is to use the library find algorithm. We'll see more about find in Section 11.1 (p. 392). To use find or any other generic algorithm, we must include the algorithm header. The find function takes a pair of iterators that denote a range in which to look, and a value to look for within that range. find returns an iterator referring to the first element with that value or the off-the-end iterator:

      string searchValue("Quasimodo");      list<string>::iterator iter =             find(slist.begin(), slist.end(), searchValue);      if (iter != slist.end())           slist.erase(iter); 

Note that we check that the iterator is not the end iterator before erasing the element. When we ask erase to erase a single element, the element must existthe behavior of erase is undefined if we ask it to erase an off-the-end iterator.

Removing All the Elements in a Container

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

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

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

      // delete range of elements between two values      list<string>::iterator elem1, elem2;      // elem1 refers to val1      elem1 = find(slist.begin(), slist.end(), val1);      // elem2 refers to the first occurrence of val2 after val1      elem2 = find(elem1, slist.end(), val2);      // erase range from val1 up to but not including val2      slist.erase(elem1, elem2); 

This code starts by calling find twice to obtain iterators to two elements. The iterator elem1 refers to the first occurrence of val1 or to the off-the-end iterator if val1 is not present in the list. The iterator elem2 refers to the first occurrence of val2 that appears after val1 if that element exists, otherwise, elem2 is an off the-end iterator. The call to erase removes the elements starting from the referred to by elem1 up to but not including elem2.

The erase, pop_front, and pop_back functions invalidate any iterators that refer to the removed elements. For vectors, iterators to elements after the erasure point are also invalidated. For deque, if the erase does not include either the first or last element, all iterators into the deque are invalidated.

Exercises Section 9.3.7

Exercise 9.25:	What happens in the program that erased a range of elements if val1 is equal to val2. What happens if either val1 or val2 or both are not present.
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. int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };
Exercise 9.27:	Write a program to process a list of strings. Look for a particular value and, if found, remove it. Repeat the program using a deque.

9.3.8. Assignment and swap

The assignment-related operators act on the entire container. Except for swap, they can be expressed in terms of erase and insert operations. The assignment operator erases the entire range of elements in the left-hand container and then inserts the elements of the right-hand container object into the left-hand container:

      c1 = c2; // replace contents of c1 with a copy of elements in c2      // equivalent operation using erase and insert      c1.erase(c1.begin(), c1.end()); // delete all elements in c1      c1.insert(c1.begin(), c2.begin(), c2.end()); // insert c2 

After the assignment, the left- and right-hand containers are equal: Even if the containers had been of unequal size, after the assignment both containers have the size of the right-hand operand.

Assignment and the assign operations invalidate all iterators into the left-hand container. swap does not invalidate iterators. After swap, iterators continue to refer to the same elements, although those elements are now in a different container.

Using assign

The assign operation deletes all the elements in the container and then inserts new elements as specified by the arguments. Like the constructor that copies elements from a container, the assignment operator (=) can be used to assign one container to another only if the container and element type are the same. If we want to assign elements of a different but compatible element type and/or from a different container type, then we must use the assign operation. For example, we could use assign to assign a range of char* values from a vector into a list of string.

Table 9.11. Sequential Container Assignment Operations

c1 = c2	Deletes elements in c1 and copies elements from c2 into c1. c1 and c2 must be the same type.
c1.swap(c2)	Swaps contents: After the call c1 has elements that were in c2, and c2 has elements that were in c1. c1 and c2 must be the same type. Execution time usually much faster than copying elements from c2 to c1.
c.assign(b,e)	Replaces the elements in c by those in the range denoted by iterators b and e. The iterators b and e must not refer to elements in c.
c.assign(n,t)	Replaces the elements in c by n elements with value t.

Because the original elements are deleted, the iterators passed to assign must not refer to elements in the container on which assign is called.

The arguments to assign determine how many elements are inserted and what values the new elements will have. This statement:

      // equivalent to slist1 = slist2      slist1.assign(slist2.begin(), slist2.end()); 

uses the version of assign that takes a pair of iterators. After deleting the elements in slist1, the function copies the elements in the range denoted by the iterators into slist2. Thus, this code is equivalent to assigning slist2 to slist1.

The assign operator that takes an iterator pair lets us assign elements of one container type to another.

A second version of assign takes an integral value and an element value. It replaces the elements in the container by the specified number of elements, each of which has the specified element value

      // equivalent to: slist1.clear();      // followed by slist1.insert(slist1.begin(), 10, "Hiya!");      slist1.assign(10, "Hiya!"); // 10 elements; each one is Hiya! 

After executing this statement, slist1 has 10 elements, each of which has the value Hiya!.

Using swap to Avoid the Cost of Deleting Elements

The swap operation swaps the values of its two operands. The types of the containers must match: The operands must be the same kind of container, and they must hold values of the same type. After the call to swap, the elements that had been in the right-hand operand are in the left, and vice versa:

      vector<string> svec1(10); // vector with 10 elements      vector<string> svec2(24); // vector with 24 elements      svec1.swap(svec2); 

After the swap, svec1 contains 24 string elements and svec2 contains 10.

The important thing about swap is that it does not delete or insert any elements and is guaranteed to run in constant time. No elements are moved, and so iterators are not invalidated.

The fact that elements are not moved means that iterators are not invalidated. They refer to the same elements as they did before the swap. However, after the swap, those elements are in a different container. For example, had iter referred to the string at position svec1[3] before the swap it will refer to the element at position svec2[3] after the swap.

Exercises Section 9.3.8

Exercise 9.28:

Write a program to assign the elements from a list of char* pointers to C-style character strings to a vector of strings.