📄 lis_8858.htm
字号:
<A HREF="sidebar.htm#sidebar19"><IMG SRC="images/note.gif" BORDER=0> <STRONG>Iteration Invalidation</STRONG></A>
<P>An iterator can denote a location in the middle of a list. There are several ways to produce this iterator. For example, we can use the result of any of the searching operations described in <a href="sea_9743.htm">Chapter 13 (<i>Searching Opertations</i>)</a>, such as an invocation of the <SAMP>find()</SAMP> generic algorithm. The new value is inserted immediately <I>prior </I>to the location denoted by the iterator. The <SAMP>insert()</SAMP> operation itself returns an iterator denoting the location of the inserted value. This result value was ignored in the invocations shown above.</P>
<PRE> // find the location of the first occurrence of the
// value 5 in list
list<int>::iterator location =
find(list_nine.begin(), list_nine.end(), 5);
// and insert an 11 immediate before it
location = list_nine.insert(location, 11);
</PRE>
<P>It is also possible to insert a fixed number of copies of an argument value. This form of <SAMP>insert()</SAMP> does not yield the location of the values.</P>
<PRE> line_nine.insert (location, 5, 12); // insert five twelves
</PRE>
<P>Finally, an entire sequence denoted by an iterator pair can be inserted into a list. Again, no useful value is returned as a result of the <SAMP>insert().</SAMP></P>
<PRE> // insert entire contents of list_ten into list_nine
list_nine.insert (location, list_ten.begin(), list_ten.end());
</PRE>
<P>There are a variety of ways to <I>splice</I> one list into another. A splice differs from an insertion in that the item is simultaneously added to the receiver list and removed from the argument list. For this reason, a splice can be performed very efficiently, and should be used whenever appropriate. As with an insertion, the member function <SAMP>splice()</SAMP> uses an iterator to indicate the location in the receiver list where the splice should be made. The argument is either an entire list, a single element in a list (denoted by an iterator), or a subsequence of a list (denoted by a pair of iterators).</P>
<PRE> // splice the last element of list ten
list_nine.splice (location, list_ten, list_ten.end());
// splice all of list ten
list_nine.splice (location, list_ten);
// splice list 9 back into list 10
list_ten.splice (list_ten.begin(), list_nine,
list_nine.begin(), location);
</PRE>
<P>Two ordered lists can be combined into one using the <SAMP>merge()</SAMP> operation. Values from the argument list are merged into the ordered list, leaving the argument list empty. The merge is stable; that is, elements retain their relative ordering from the original lists. As with the generic algorithm of the same name (<i><a href="mer_3553.htm">Chapter 14: Merge Ordered Sequences</a></i>), two forms are supported. The second form uses the binary function supplied as argument to order values. Not all compilers support the second form. If the second form is desired and not supported, the more general generic algorithm can be used, although this is slightly less efficient.</P>
<PRE> // merge with explicit compare function
list_eleven.merge(list_six, widgetCompare);
//the following is similar to the above
list<Widget> list_twelve;
merge (list_eleven.begin(), list_eleven.end(),
list_six.begin(), list_six.end(),
inserter(list_twelve, list_twelve.begin()), widgetCompare);
list_eleven.swap(list_twelve);
</PRE>
<A NAME="removingelements"><H3>Removing Elements</H3></A>
<P>Just as there are a number of different ways to insert an element into a list, there are a variety of ways to remove values from a list. The most common operations used to remove a value are <SAMP>pop_front()</SAMP> or <SAMP>pop_back(),</SAMP> which delete the single element from the front or the back of the list, respectively. These member functions simply remove the given element, and do not themselves yield any useful result. If a destructor is defined for the element type it will be invoked as the element is removed. To look at the values before deletion, use the member functions<SAMP> front()</SAMP> or <SAMP>back().</SAMP></P>
<P>The <SAMP>erase()</SAMP> operation can be used to remove a value denoted by an iterator. For a list, the argument iterator, and any other iterators that denote the same location, become invalid after the removal, but iterators denoting other locations are unaffected. We can also use <SAMP>erase()</SAMP> to remove an entire subsequence, denoted by a pair of iterators. The values beginning at the initial iterator and up to, but not including, the final iterator are removed from the list. Erasing elements from the middle of a list is an efficient operation, unlike erasing elements from the middle of a vector or a deque.</P>
<PRE> list_nine.erase (location);
// erase values between the first occurrence of 5
// and the following occurrence of 7
list<int>::iterator
location = find(list_nine.begin(), list_nine.end(), 5);
list<int>::iterator location2 =
find(location, list_nine.end(), 7);
list_nine.erase (location, location2);
</PRE>
<P>The <SAMP>remove()</SAMP> member function removes all occurrences of a given value from a list. A variation, <SAMP>remove_if(),</SAMP> removes all values that satisfy a given predicate. An alternative to the use of either of these is to use the <SAMP>remove()</SAMP> or <SAMP>remove_if()</SAMP> generic algorithms (<i><a href="rem_8388.htm#removeunwantedelements">Chapter 13: Remove Unwanted Elements</a></i>). The generic algorithms do not reduce the size of the list, instead they move the elements to be retained to the front of the list, leave the remainder of the list unchanged, and return an iterator denoting the location of the first unmodified element. This value can be used in conjunction with the <SAMP>erase()</SAMP> member function to remove the remaining values.</P>
<PRE> list_nine.remove(4); // remove all fours
list_nine.remove_if(divisibleByThree); //remove any div by 3
// the following is equivalent to the above
list<int>::iterator location3 =
remove_if(list_nine.begin(), list_nine.end(),
divisibleByThree);
list_nine.erase(location3, list_nine.end());
</PRE>
<P>The operation <SAMP>unique()</SAMP> will erase all but the first element from every consecutive group of equal elements in a list. The list need not be ordered. An alternative version takes a binary function, and compares adjacent elements using the function, removing the second value in those situations were the function yields a true value. As with <SAMP>remove_if(),</SAMP> not all compilers support the second form of <SAMP>unique().</SAMP> In this case the more general <SAMP>unique()</SAMP> generic algorithm can be used (<i>see <a href="rem_8388.htm#removerunsofsimilarvalues">Chapter 13: Remove Overruns of Similar Values</a></i>). In the following example the binary function is the greater-than operator, which will remove all elements smaller than a preceding element.</P>
<PRE> // remove first from consecutive equal elements
list_nine.unique();
// explicitly give comparison function
list_nine.unique(greater<int>());
// the following is equivalent to the above
location3 =
unique(list_nine.begin(), list_nine.end(), greater<int>());
list_nine.erase(location3, list_nine.end());
</PRE>
<A NAME="extentandsizechangingoperations"><H3>Extent and Size-Changing Operations</H3></A>
<P>The member function <SAMP>size()</SAMP> will return the number of elements being held by a container. The function <SAMP>empty()</SAMP> will return <SAMP>true</SAMP> if the container is empty, and is more efficient than comparing the size against the value <SAMP>zero</SAMP>.</P>
<PRE> cout << "Number of elements: " << list_nine.size () << endl;
if ( list_nine.empty () )
cout << "list is empty " << endl;
else
cout << "list is not empty " << endl;
</PRE>
<P>The member function <SAMP>resize()</SAMP> changes the size of the list to the value specified by the argument. Values are either added or erased from the end of the collection as necessary. An optional second argument can be used to provide the initial value for any new elements added to the collection.</P>
<PRE> // become size 12, adding values of 17 if necessary
list_nine.resize (12, 17); </PRE>
<A NAME="accessanditeration"><H3>Access and Iteration</H3></A>
<P>The member functions <SAMP>front()</SAMP> and<SAMP> back()</SAMP> return, but do not remove, the first and last items in the container, respectively. For a list, access to other elements is possible only by removing elements (until the desired element becomes the front or back) or through the use of iterators.</P>
<P>There are three types of iterators that can be constructed for lists. The functions <SAMP>begin()</SAMP> and <SAMP>end()</SAMP> construct iterators that traverse the list in forward order. For the <A HREF="../stdref/lis_3222.htm"><B><I>list</I></B></A> data type <SAMP>begin()</SAMP> and <SAMP>end()</SAMP> create bidirectional iterators. The alternative functions <SAMP>rbegin()</SAMP> and <SAMP>rend()</SAMP> construct iterators that traverse in reverse order, moving from the end of the list to the front.</P>
<A NAME="testforinclusion"><H3>Test for Inclusion</H3></A>
<P>The list data types do not directly provide any method that can be used to determine if a specific value is contained in the collection. However, either the generic algorithms <SAMP>find()</SAMP> or <SAMP>count()</SAMP> (<i>Chapter 13: <a href="sea_9743.htm#findanelementsatisfyingacondition">Find an Element Satisfying a Condition</a> and <a href="sca_1926.htm#countthenumberofelementsthatsatisfyacondition">Count the Number of Elements that Satisfy a Condition</a></i>) can be used for this purpose. The following statements, for example, test to see whether an integer list contains the element 17.</P>
<PRE>int num = 0;
count(list_five.begin(), list_five.end(), 17, num);
if (num > 0)
cout << "contains a 17" << endl;
else
cout << "does not contain a 17" << endl;
if (find(list_five.begin(), list_five.end(), 17) != list_five.end())
cout << "contains a 17" << endl;
else
cout << "does not contain a 17" << endl;
</PRE>
<A NAME="sortingandsortedlistoperations"><H3>Sorting and Sorted List Operations</H3></A>
<P>The member function <SAMP>sort()</SAMP> places elements into ascending order. If a comparison operator other than <SAMP><</SAMP> is desired, it can be supplied as an argument.</P>
<PRE>list_ten.sort ( ); // place elements into sequence
list_twelve.sort (widgetCompare); // sort with widget compare
// function
</PRE>
<P>Once a list has been sorted, a number of the generic algorithms for ordered collections can be used with lists. These are described in detail in <a href="ord_1635.htm">Chapter 14</a>.</P>
<A NAME="searchingoperations"><H3>Searching Operations</H3></A>
<P>The various forms of searching functions described in <a href="gen_9895.htm">Chapter 13</a>, namely <SAMP>find(),</SAMP> <SAMP>find_if(),</SAMP> <SAMP>adjacent find(),</SAMP> <SAMP>mismatch(),</SAMP> <SAMP>max_element()</SAMP>, <SAMP>min_element()</SAMP> or <SAMP>search()</SAMP> can be applied to list. In all cases the result is an iterator, which can be dereferenced to discover the denoted element, or used as an argument in a subsequent operation.</P>
<A HREF="sidebar.htm#sidebar20"><IMG SRC="images/note.gif" BORDER=0> <STRONG>Verify Search Results</STRONG></A>
<A NAME="inplacetransformations"><H3>In Place Transformations</H3></A>
<P>A number of operations can be applied to lists in order to transform them in place. Some of these are provided as member functions. Others make use of some of the generic functions described in <a href="gen_9895.htm">Chapter 13</a>.</P>
<P>For a list, the member function <SAMP>reverse()</SAMP> reverses the order of elements in the list.</P>
<PRE> list_ten.reverse(); // elements are now reversed
</PRE>
<P>The generic algorithm <SAMP>transform()</SAMP> (<i><a href="seq_4302.htm#transformoneortwosequences">Chapter 13: Transform One or Two Sequences</a></i>) can be used to modify every value in a container, by simply using the same container as both input and as result for the operation. The following, for example, increments each element of a list by one. To construct the necessary unary function, the first argument of the binary integer addition function is bound to the value one. The version of <SAMP>transform()</SAMP> that manipulates two parallel sequences can be used in a similar fashion.</P>
<PRE> transform(list_ten.begin(), list_ten.end(),
list_ten.begin(), bind1st(plus<int>(), 1));
</PRE>
<P>Similarly, the functions <SAMP>replace()</SAMP> and <SAMP>replace_if()</SAMP> (Section 12.4.2) can be used to replace elements of a list with specific values. Rotations (<i> <a href="inp_4704.htm#rotateelementsaroundamidpoint">Chapter 13: Rotate Elements Around a Midpoint</a></i>) and partitions (<i><a href="inp_4704.htm#partitionasequenceintotwogroups">Chapter 13: Partition a Sequence...</a></i>), can also be performed with lists.</P>
<PRE> // find the location of the value 5, and rotate around it
location = find(list_ten.begin(), list_ten.end(), 5);
rotate(list_ten.begin(), location, list_ten.end());
// now partition using values greater than 7
partition(list_ten.begin(), list_ten.end(),
bind2nd(greater<int>(), 7));
</PRE>
<P>The functions <SAMP>next_permutation()</SAMP> and <SAMP>prev_permutation()</SAMP> (<i><a href="inp_4704.htm#generatepermutationsinsequence">Chapter 13: Generate Permutations in Sequence</a></i>) can be used to generate the next permutation (or previous permutation) of a collection of values.</P>
<PRE> next_permutation (list_ten.begin(), list_ten.end());
</PRE>
<A NAME="otheroperations"><H3>Other Operations</H3></A>
<P>The algorithm <SAMP>for_each()</SAMP> (<i><a href="mis_2456.htm#applyafunctiontoallelementsinacollection">Section 13: Apply a Function to All Elements...</a></i>) will apply a function to every element of a collection. An illustration of this use will be given in the radix sort example program in the section on the deque data structure.</P>
<P>The <SAMP>accumulate()</SAMP> generic algorithm reduces a collection to a scalar value (<i>see <a href="sca_1926.htm#reducesequencetoasinglevalue">Chapter 13: Reduce Sequence to a Single Value</a></i>). This can be used, for example, to compute the sum of a list of numbers. A more unusual use of <SAMP>accumulate()</SAMP> will be illustrated in the radix sort example.</P>
<PRE> cout << "Sum of list is: " <<
accumulate(list_ten.begin(), list_ten.end(), 0) << endl;
</PRE>
<P>Two lists can be compared against each other. They are equal if they are the same size and all corresponding elements are equal. A list is less than another list if it is lexicographically smaller (<i>see <a href="sca_1926.htm#generalizedinnerproduct">Chapter 13: Generalized Inner Product</a></i>).</P>
<HR>
<A HREF="lis_0449.htm"><IMG SRC="images/prev.gif"></A> <A HREF="booktoc.htm"><IMG SRC="images/toc.gif"></A> <A HREF="exa_3285.htm"><IMG SRC="images/next.gif"></A></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -