|
|
9.3. Sequence Container OperationsEach sequential container defines a set of useful typedefs and supports operations that let us
9.3.1. Container TypedefsWe'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.
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.
9.3.2. begin and end MembersThe 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.
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 ContainerIn 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.
Adding Elements at a Specified Point in the ContainerThe 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
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 ElementsA 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 IteratorsAs 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.
Avoid Storing the Iterator Returned from endWhen 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.
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 OperatorsEach 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>. 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):
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 OperatorEach 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
9.3.5. Container Size OperationsEach 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).
For any container type, if resize shrinks the container, then any iterator to an element that is deleted is invalidated.
9.3.6. Accessing ElementsIf 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.
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
9.3.7. Erasing ElementsRecall 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 ElementThe 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.
Removing an Element From within the ContainerThe 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.
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 ContainerTo 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.
9.3.8. Assignment and swapThe 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.
Using assignThe 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.
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.
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 ElementsThe 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 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.
|
|
|
