لطفا منتظر باشید ...
9.3. Sequence Container Operations
Each sequential container defines a set of useful typedefs and supports operations that let usAdd elements to the containerDelete elements from the containerDetermine the size of the containerFetch 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 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 Chapter 16.Expressions that use a container-defined type can look intimidating:
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.
// 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;
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.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 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:
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,
// read from standard input putting each word onto the end of container
string text_word;
while (cin >> text_word)
container.push_back(text_word);
uses push_back to add the sequence 0, 1, 2, 3 to the end of ilist.Alternatively, we could use push_front
list<int> ilist;
// add elements at the end of ilist
for (size_t ix = 0; ix != 4; ++ix)
ilist.push_back(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.
// add elements to the start of ilist
for (size_t ix = 0; ix != 4; ++ix)
ilist.push_front(ix);
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:
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
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);
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:
slist.insert(iter, spouse); // insert spouse just before iter
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:
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
svec.insert(svec.end(), 10, "Anna");
we can insert all or a subset of the array elements into our list of strings:
string sarray[4] = {"quasi", "simba", "frollo", "scar"};
// 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:
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.
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
}
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: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:
ivec1 < ivec2
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?
What, if any, constraints are there on c1 and c2?
if (c1 < 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:
Section 3.3.1, p. 92).
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
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:
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.Section 6.13, p. 215):
// 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(); }
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:
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.
while (!ilist.empty()) {
process(ilist.front()); // do something with the current top of ilist
ilist.pop_front(); // done; remove first element
}
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 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:
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.
string searchValue("Quasimodo");
list<string>::iterator iter =
find(slist.begin(), slist.end(), searchValue);
if (iter != slist.end())
slist.erase(iter);
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:
The iterator-pair version of erase lets us delete a subrange of elements:
slist.clear(); // delete all the elements within the container
slist.erase(slist.begin(), slist.end()); // equivalent
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.
// 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);
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.
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.
int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };
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:
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.
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
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 = c2Deletes 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: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.
// equivalent to slist1 = slist2
slist1.assign(slist2.begin(), slist2.end());
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 valueAfter executing this statement, slist1 has 10 elements, each of which has the value Hiya!.
// equivalent to: slist1.clear();
// followed by slist1.insert(slist1.begin(), 10, "Hiya!");
slist1.assign(10, "Hiya!"); // 10 elements; each one is 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:
After the swap, svec1 contains 24 string elements and svec2 contains 10.
vector<string> svec1(10); // vector with 10 elements
vector<string> svec2(24); // vector with 24 elements
svec1.swap(svec2);
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.
