| <!-- |
| Licensed to the Apache Software Foundation (ASF) under one or more |
| contributor license agreements. See the NOTICE file distributed |
| with this work for additional information regarding copyright |
| ownership. The ASF licenses this file to you under the Apache |
| License, Version 2.0 (the License); you may not use this file |
| except in compliance with the License. You may obtain a copy of |
| the License at |
| |
| http://www.apache.org/licenses/LICENSE-2.0 |
| |
| Unless required by applicable law or agreed to in writing, software |
| distributed under the License is distributed on an "AS IS" BASIS, |
| WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or |
| implied. See the License for the specific language governing |
| permissions and limitations under the License. |
| |
| Copyright 1999-2007 Rogue Wave Software, Inc. |
| --> |
| |
| <HTML> |
| <HEAD> |
| <TITLE>list Operations</TITLE> |
| <LINK REL=StyleSheet HREF="../rw.css" TYPE="text/css" TITLE="Apache stdcxx Stylesheet"></HEAD> |
| <BODY BGCOLOR=#FFFFFF> |
| <A HREF="6-1.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="6-3.html"><IMG SRC="images/bnext.gif" WIDTH=25 HEIGHT=21 ALT="Next file" BORDER=O></A><DIV CLASS="DOCUMENTNAME"><B>Apache C++ Standard Library User's Guide</B></DIV> |
| <H2>6.2 list Operations</H2> |
| <A NAME="idx103"><!></A> |
| <P>In this section, each of the member functions provided by the <B><I><A HREF="../stdlibref/list.html">list</A></I></B> datatype are described in more detail. These member functions provide the basic operations for <B><I>list</I></B>s. They can be greatly extended through the generic algorithms described in <A HREF="13.html">Chapter 13</A>.</P> |
| <A NAME="621"><H3>6.2.1 Declaration and Initialization of lists</H3></A> |
| <P>A list may contain elements of a primitive language type, such as an <SAMP>int</SAMP> or <SAMP>double</SAMP>, a pointer type, or a user-defined type. A user-defined type <I>must</I> implement a copy constructor, as this constructor is used to initialize newly created elements.</P> |
| <A NAME="idx104"><!></A> |
| <P>There are a variety of ways to declare a <B><I><A HREF="../stdlibref/list.html">list</A></I></B>. In the simplest form, a <B><I>list</I></B> is declared by simply stating the type of element the <B><I>list</I></B> will maintain. A <B><I>list</I></B> declared in this fashion initially contains no elements:</P> |
| |
| <UL><PRE> |
| std::list<int> list_one; |
| std::list<Widget*> list_two; |
| std::list<Widget> list_three; |
| </PRE></UL> |
| <BLOCKQUOTE><HR><B> |
| NOTE -- If you declare a container as holding pointers, you are responsible for managing the memory for the objects pointed to. The container classes will not automatically free memory for these objects when an item is erased from the container. |
| </B><HR></BLOCKQUOTE> |
| <P>An alternative form of declaration creates a collection that initially contains some number of equal elements. The constructor takes two arguments, a <I>size</I> and an <I>initial value</I>. The second argument is optional if the contained type has a default constructor. If only the number of initial elements to be created is given, these values are initialized with the default constructor; otherwise the elements are initialized with the value of the second argument:</P> |
| |
| <UL><PRE> |
| std::list<int> list_four (5); // five elements, |
| // each initialized to zero |
| |
| std::list<double> list_five (4, 3.14); // 4 values, |
| // each initially 3.14 |
| |
| std::list<Widget> list_six (4); // 4 elements, each created using |
| // default constructor for Widget |
| |
| std::list<Widget> list_six (3, Widget(7)); // 3 elements, each a |
| // copy of Widget(7) |
| </PRE></UL> |
| <P><B><I><A HREF="../stdlibref/list.html">list</A></I></B>s can also be initialized using elements from another collection, with a beginning and ending iterator pair. The arguments can be any form of iterator; thus collections can be initialized with values drawn from any of the container classes in the C++ Standard Library that support iterators.</P> |
| |
| <UL><PRE> |
| std::list<double> list_seven(aVector.begin(), aVector.end()); |
| </PRE></UL> |
| <P>The <SAMP>insert()</SAMP> operation can also be used to place values denoted by an iterator into a <B><I><A HREF="../stdlibref/list.html">list</A></I></B> (<A HREF="6-2.html#623">Section 6.2.3</A>). Insert iterators can be used to initialize a <B><I>list</I></B> with a sequence of values produced by a <I>generator</I> (<A HREF="13-2.html#1323">Section 13.2.3</A>). This is illustrated by the following:</P> |
| |
| <UL><PRE> |
| std::list<int> list_nine; |
| |
| // initialize list 1 2 3 ... 7 |
| |
| std::generate_n(std::inserter(list_nine, list_nine.begin()), |
| 7, iotaGen(1)); |
| </PRE></UL> |
| <P>A <I>copy constructor</I> can be used to initialize a <B><I><A HREF="../stdlibref/list.html">list</A></I></B> with values drawn from another <B><I>list</I></B>. The assignment operator performs the same actions. In both cases the assignment operator for the element type is used to copy each new value.</P> |
| |
| <UL><PRE> |
| std::list<int> list_ten (list_nine); // copy constructor |
| std::list<Widget> list_eleven; |
| std::list_eleven = list_six; // values copied by assignment |
| </PRE></UL> |
| <A NAME="idx105"><!></A> |
| <P>The <SAMP>assign()</SAMP> member function is similar to the assignment operator, but is more versatile and, in some cases, requires more arguments. Like an assignment, the existing values in the container are deleted, and replaced with the values specified by the arguments. If a destructor is provided for the container element type, it is invoked for the elements being removed. There are two forms of <SAMP>assign()</SAMP>:</P> |
| <UL> |
| <LI><P CLASS="LIST">The first form takes two iterator arguments that specify a sub-sequence of an existing container. The values from this sub-sequence then become the new elements in the receiver. </P></LI> |
| <LI><P CLASS="LIST">The second form takes a count and an optional value of the container element type. After the call the container holds the number of elements specified by the count, which is equal to either the default value for the container type or the initial value specified. The initial value must be specified if the contained type does not have a default constructor.</P></LI> |
| |
| <UL><PRE> |
| list_six.assign(list_ten.begin(), list_ten.end()); |
| list_four.assign(3, 7); // three copies of value seven |
| list_five.assign(12); // twelve copies of value zero |
| </PRE></UL> |
| </UL> |
| <A NAME="idx106"><!></A> |
| <P>Finally, two <B><I><A HREF="../stdlibref/list.html">list</A></I></B>s can exchange their entire contents by means of the operation <SAMP>swap()</SAMP>. The argument container takes on the values of the receiver, while the receiver assumes those of the argument. A swap is very efficient, and should be used in preference to an explicit element-by-element transfer where appropriate.</P> |
| |
| <UL><PRE> |
| list_ten.swap(list_nine); // exchange lists nine and ten |
| </PRE></UL> |
| <A NAME="622"><H3>6.2.2 Type Definitions</H3></A> |
| <A NAME="idx107"><!></A> |
| <P>The class <B><I><A HREF="../stdlibref/list.html">list</A></I></B> includes a number of type definitions, most commonly used in declaration statements. For example, an iterator for a <B><I>list</I></B> of integers can be declared as follows:</P> |
| |
| <UL><PRE> |
| std::list<int>::iterator location; |
| </PRE></UL> |
| <P>In addition to <SAMP>iterator</SAMP>, <B><I><A HREF="../stdlibref/list.html">list</A></I></B> defines the following types:</P> |
| <H4><A NAME="Table 11">Table 11: Type definitions for class list</A></H4> |
| <TABLE BORDER="1" CELLPADDING="3" CELLSPACING="3"> |
| <tr><td valign=top><B>Type</B> |
| </td><td valign=top><B>Definition</B> |
| </td></tr> |
| <tr><td valign=top><P CLASS="TABLE"><SAMP>value_type</SAMP></P> |
| </td><td valign=top><P CLASS="TABLE">The type of the elements maintained by the list.</P> |
| </td></tr> |
| <tr><td valign=top><P CLASS="TABLE"><SAMP>const_iterator</SAMP></P> |
| </td><td valign=top><P CLASS="TABLE">An iterator that does not allow modification of the underlying sequence.</P> |
| </td></tr> |
| <tr><td valign=top><P CLASS="TABLE"><SAMP>reverse_iterator</SAMP></P> |
| </td><td valign=top><P CLASS="TABLE">An iterator that moves in a backward direction.</P> |
| </td></tr> |
| <tr><td valign=top><P CLASS="TABLE"><SAMP>const_reverse_iterator</SAMP></P> |
| </td><td valign=top><P CLASS="TABLE">A combination constant and reverse iterator.</P> |
| </td></tr> |
| <tr><td valign=top><P CLASS="TABLE"><SAMP>reference</SAMP></P> |
| </td><td valign=top><P CLASS="TABLE">A reference to an underlying element.</P> |
| </td></tr> |
| <tr><td valign=top><P CLASS="TABLE"><SAMP>const_reference</SAMP></P> |
| </td><td valign=top><P CLASS="TABLE">A reference to an underlying element that will not permit the element to be modified.</P> |
| </td></tr> |
| <tr><td valign=top><P CLASS="TABLE"><SAMP>pointer</SAMP></P> |
| </td><td valign=top><P CLASS="TABLE">A pointer to an underlying element</P> |
| </td></tr> |
| <tr><td valign=top><P CLASS="TABLE"><SAMP>const_pointer</SAMP></P> |
| </td><td valign=top><P CLASS="TABLE">A constant pointer to an underlying element.</P> |
| </td></tr> |
| <tr><td valign=top><P CLASS="TABLE"><SAMP>size_type</SAMP></P> |
| </td><td valign=top><P CLASS="TABLE">An unsigned integer type, used to refer to the size of containers.</P> |
| </td></tr> |
| <tr><td valign=top><P CLASS="TABLE"><SAMP>difference_type</SAMP></P> |
| </td><td valign=top><P CLASS="TABLE">A signed integer type, used to describe distances between iterators.</P> |
| </td></tr> |
| <tr><td valign=top><P CLASS="TABLE"><SAMP>allocator_type</SAMP></P> |
| </td><td valign=top><P CLASS="TABLE">The allocator type used for all storage management by the list.</P> |
| </td></tr> |
| </TABLE> |
| <A NAME="623"><H3>6.2.3 Placing Elements into a list</H3></A> |
| <A NAME="idx108"><!></A> |
| <P>Values can be inserted into a <B><I><A HREF="../stdlibref/list.html">list</A></I></B> in a variety of ways. Elements are most commonly added to the front or back of a <B><I>list</I></B>. These tasks are provided by the <SAMP>push_front()</SAMP> and <SAMP>push_back()</SAMP> operations, respectively. These operations are efficient (constant time) for both types of containers:</P> |
| |
| <UL><PRE> |
| list_seven.push_front(1.2); |
| list_eleven.push_back(Widget(6)); |
| </PRE></UL> |
| <A NAME="idx109"><!></A> |
| <P>In <A HREF="6-2.html#621">Section 6.2.1</A> we noted how values can be placed into a <B><I><A HREF="../stdlibref/list.html">list</A></I></B> at a location denoted by an iterator with the aid of an insert iterator and the <SAMP>std::copy()</SAMP> or <SAMP>std::generate()</SAMP> generic algorithm. There is also a member function, named <SAMP>insert(),</SAMP> that avoids the need to construct the inserter. As we will describe shortly, the values returned by the iterator generating functions <SAMP>begin()</SAMP> and <SAMP>end()</SAMP> denote the beginning and end of a <B><I>list</I></B>, respectively. An insert using one of these is equivalent to <SAMP>push_front()</SAMP> or <SAMP>push_back()</SAMP>, respectively. If we specify only one iterator, the default element value is inserted:</P> |
| |
| <UL><PRE> |
| // insert default type at beginning of list |
| list_eleven.insert(list_eleven.begin()); |
| // insert widget 8 at end of list |
| list_eleven.insert(list_eleven.end(), Widget(8)); |
| </PRE></UL> |
| <P>An iterator can denote a location in the middle of a <B><I><A HREF="../stdlibref/list.html">list</A></I></B>. 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="13-3.html">Section 13.3</A>, such as an invocation of the <SAMP>find()</SAMP> generic algorithm: </P> |
| |
| <UL><PRE> |
| // find the location of the first occurrence of the |
| // value 5 in list |
| std::list<int>::iterator location = |
| std::find(list_nine.begin(), list_nine.end(), 5); |
| |
| // and insert an 11 immediately before it |
| location = list_nine.insert(location, 11); |
| </PRE></UL> |
| <P>Here 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> |
| <BLOCKQUOTE><HR><B> |
| NOTE -- Unlike a vector or deque, insertions or removals from the middle of a list will not invalidate references or pointers to other elements in the container. This property can be important if two or more iterators are being used to refer to the same container. |
| </B><HR></BLOCKQUOTE> |
| <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> |
| |
| <UL><PRE> |
| line_nine.insert(location, 5, 12); // insert five twelves |
| </PRE></UL> |
| <P>Finally, an entire sequence denoted by an iterator pair can be inserted into a <B><I><A HREF="../stdlibref/list.html">list</A></I></B>. Again, no value is returned as a result of the <SAMP>insert().</SAMP></P> |
| |
| <UL><PRE> |
| // insert entire contents of list_ten into list_nine |
| list_nine.insert(location, list_ten.begin(), list_ten.end()); |
| </PRE></UL> |
| <A NAME="623-1"><H4>6.2.3.1 Splicing</H4></A> |
| <A NAME="idx110"><!></A> |
| <P>There are several 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 source list. For this reason, a splice can be performed 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 <B><I><A HREF="../stdlibref/list.html">list</A></I></B>, a single element in a <B><I>list</I></B> (denoted by an iterator), or a sub-sequence of a <B><I>list</I></B> (denoted by a pair of iterators).</P> |
| |
| <UL><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></UL> |
| <A NAME="idx111"><!></A> |
| <P>Two ordered <B><I><A HREF="../stdlibref/list.html">list</A></I></B>s can be combined into one using the <SAMP>merge()</SAMP> operation. Values from the argument <B><I>list</I></B> are merged into the ordered <B><I>list</I></B>, leaving the argument <B><I>list</I></B> empty. The merge is stable; that is, elements retain their relative ordering from the original <B><I>list</I></B>s. As with the generic algorithm of the same name (<A HREF="14-5.html">Section 14.5</A>), two forms are supported. The first form uses the <SAMP>operator<()</SAMP> defined for the contained type. The second form uses the binary function supplied as argument to order values, but not all compilers suppor 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> |
| |
| <UL><PRE> |
| // merge with explicit compare function |
| list_eleven.merge(list_six, widgetCompare); |
| // similar merge using the generic algorithm |
| std::list<Widget> list_twelve; |
| std::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></UL> |
| <A NAME="624"><H3>6.2.4 Removing Elements</H3></A> |
| <P>Just as there are a number of different ways to insert an element into a <B><I><A HREF="../stdlibref/list.html">list</A></I></B>, there are a variety of ways to remove values from a <B><I>list</I></B>. 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. If a destructor is defined for the element type, it is invoked as the element is removed. These member functions simply remove the given element, and do not themselves yield a result. To retrieve the values before deletion, use the member functions<SAMP> front()</SAMP> or <SAMP>back()</SAMP>.</P> |
| <A NAME="idx112"><!></A> |
| <P>The <SAMP>erase()</SAMP> operation can be used to remove a value denoted by an iterator. For a <B><I><A HREF="../stdlibref/list.html">list</A></I></B>, 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 sub-sequence 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 <B><I>list</I></B>. Erasing elements from the middle of a <B><I>list</I></B> is an efficient operation, unlike erasing elements from the middle of a <B><I><A HREF="../stdlibref/vector.html">vector</A></I></B> or a <B><I><A HREF="../stdlibref/deque.html">deque</A></I></B>:</P> |
| |
| <UL><PRE> |
| list_nine.erase (location); |
| |
| // erase values between the first occurrence of 5 |
| // and the following occurrence of 7 |
| |
| std::list<int>::iterator location = |
| find(list_nine.begin(), list_nine.end(), 5); |
| std::list<int>::iterator location2 = |
| find(location, list_nine.end(), 7); |
| list_nine.erase(location, location2); |
| </PRE></UL> |
| <A NAME="idx113"><!></A> |
| <P>The <SAMP>remove()</SAMP> member function removes all occurrences of a given value from a <B><I><A HREF="../stdlibref/list.html">list</A></I></B>. A variation, <SAMP>remove_if()</SAMP>, removes all values that satisfy a given predicate. An alternative to either of these are the <SAMP>remove()</SAMP> or <SAMP>remove_if()</SAMP> generic algorithms (<A HREF="13-5.html#1351">Section 13.5.1</A>). The generic algorithms do not reduce the size of the <B><I>list</I></B>; instead they move the elements to be retained to the front of the <B><I>list</I></B>, leave the remainder of the <B><I>list</I></B> 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> |
| |
| <UL><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 |
| std::list<int>::iterator location3 = |
| std::remove_if(list_nine.begin(), list_nine.end(), |
| divisibleByThree); |
| list_nine.erase(location3, list_nine.end()); |
| </PRE></UL> |
| <A NAME="idx114"><!></A> |
| <P>The member function <SAMP>unique()</SAMP> erases duplicate elements from a <B><I><A HREF="../stdlibref/list.html">list</A></I></B>. To do this, the function iterates over the <B><I>list</I></B> and removes every element that is equal to the preceeding element. An alternative version takes a binary function and compares adjacent elements using the function, removing the second value in those situations where the function yields a true value. The more general <SAMP>unique()</SAMP> generic algorithm can also be used (<A HREF="13-5.html#1352">Section 13.5.2</A>). In the following example, the binary function is the greater-than operator, which removes all elements smaller than a preceding element:</P> |
| |
| <UL><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, using the |
| // generic algorithm unique() rather than the list member |
| // function |
| |
| std::list<int>::iterator location3 = |
| std::unique(list_nine.begin(), |
| list_nine.end(), greater<int>()); |
| list_nine.erase(location3, list_nine.end()); |
| </PRE></UL> |
| <A NAME="625"><H3>6.2.5 Extent and Size-Changing Operations</H3></A> |
| <A NAME="idx115"><!></A> |
| <P>The member function <SAMP>size()</SAMP> returns the number of elements being held by a container. The member function <SAMP>empty()</SAMP> returns <SAMP>true</SAMP> if the container is empty, and is more efficient than comparing the <SAMP>size()</SAMP> against 0.</P> |
| |
| <UL><PRE> |
| std::cout << "Number of elements: " |
| << list_nine.size () << std::endl; |
| |
| if ( list_nine.empty() ) |
| std::cout << "list is empty " << std::endl; |
| else |
| std::cout << "list is not empty " << std::endl; |
| </PRE></UL> |
| <A NAME="idx116"><!></A> |
| <P>The member function <SAMP>resize()</SAMP> changes the size of the <B><I><A HREF="../stdlibref/list.html">list</A></I></B> 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> |
| |
| <UL><PRE> |
| // become size 12, adding values of 17 if necessary |
| list_nine.resize(12, 17); |
| </PRE></UL> |
| <A NAME="626"><H3>6.2.6 Access and Iteration</H3></A> |
| <A NAME="idx117"><!></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. A <B><I><A HREF="../stdlibref/list.html">list</A></I></B> does not provide random access. Access to elements other than the first and last elements is possible only by removing elements until the desired element becomes the front or back element, or by using 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 <B><I><A HREF="../stdlibref/list.html">list</A></I></B> datatype, <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 <B><I>list</I></B> to the front.</P> |
| <A NAME="627"><H3>6.2.7 Test for Inclusion</H3></A> |
| <P>The <B><I><A HREF="../stdlibref/list.html">list</A></I></B> datatypes do not directly provide any method that can be used to determine if a specific value is contained in the collection. However, either of the generic algorithms <SAMP>std::find()</SAMP> or <SAMP>std::count()</SAMP> can be used for this purpose (<A HREF="13-3.html#1331">Section 13.3.1</A> and <A HREF="13-6.html#1361">Section 13.6.1</A>). For example, to test whether an integer list contains the element 17:</P> |
| |
| <UL><PRE> |
| find(vec_five.begin(), vec_five.end(), 17); |
| </PRE></UL> |
| <P>If your compiler does not support partial specialization, then you must use the following interface instead:</P> |
| |
| <UL><PRE> |
| // test for inclusion using count |
| |
| int num = 0; |
| std::count(list_five.begin(), list_five.end(), 17, num); |
| if (num > 0) |
| std::cout << "contains a 17" << std::endl; |
| else |
| std::cout << "does not contain a 17" << std::endl; |
| |
| // test for inclusion using find |
| |
| if (std::find(list_five.begin(), list_five.end(), 17) != |
| list_five.end()) |
| std::cout << "contains a 17" << std::endl; |
| else |
| std::cout << "does not contain a 17" << std::endl; |
| </PRE></UL> |
| <A NAME="628"><H3>6.2.8 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> |
| |
| <UL><PRE> |
| list_ten.sort(); // order elements |
| |
| list_twelve.sort(widgetCompare); // sort with widget compare |
| // function |
| </PRE></UL> |
| <P>Once a <B><I><A HREF="../stdlibref/list.html">list</A></I></B> has been sorted, a number of the generic algorithms for ordered collections can be used with <B><I>list</I></B>s (<A HREF="14.html">Chapter 14</A>).</P> |
| <A NAME="629"><H3>6.2.9 Searching Operations</H3></A> |
| <P>The various forms of searching functions described in <A HREF="13-3.html">Chapter 13.3</A>, namely <SAMP>std::find()</SAMP>, <SAMP>std::find_if()</SAMP>, <SAMP>std::adjacent_find()</SAMP>, <SAMP>std::mismatch()</SAMP>, <SAMP>std::max_element()</SAMP>, <SAMP>std::min_element()</SAMP>, or <SAMP>std::search()</SAMP>, can be applied to <B><I><A HREF="../stdlibref/list.html">list</A></I></B>. 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> |
| <BLOCKQUOTE><HR><B> |
| NOTE -- The searching algorithms in the C++ Standard Library always return the end of range iterator if no element matching the search condition is found. Unless the result is guaranteed to be valid, it is a good idea to check for the end of range condition. |
| </B><HR></BLOCKQUOTE> |
| <A NAME="6210"><H3>6.2.10 In-Place Transformations</H3></A> |
| <P>A number of operations can be applied to <B><I><A HREF="../stdlibref/list.html">list</A></I></B>s 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="13.html">Chapter 13</A>.</P> |
| <A NAME="idx118"><!></A> |
| <P>For a list, the member function <SAMP>reverse()</SAMP> reverses the order of elements in the list:</P> |
| |
| <UL><PRE> |
| list_ten.reverse(); // elements are now reversed |
| </PRE></UL> |
| <P>The generic algorithm <SAMP>std::transform()</SAMP> can be used to modify every value in a container by simply using the same container as both input and result for the operation (<A HREF="13-7.html#1371">Section 13.7.1</A>). For example, the following code increments each element of a list by one: </P> |
| |
| <UL><PRE> |
| std::transform(list_ten.begin(), list_ten.end(), list_ten.begin(), |
| std::bind1st(std::plus<int>(), 1)); |
| </PRE></UL> |
| <P>To construct the necessary unary function, the first argument of the binary integer addition function is bound to the value 1 using the <B><I><A HREF="../stdlibref/bind1st.html">bind1st</A></I></B> function adapter (<A HREF="3-5.html">Section 3.5</A>). The version of <SAMP>std::transform()</SAMP> that manipulates two parallel sequences can also be used this way.</P> |
| <P>Similarly, the functions <SAMP>std::replace()</SAMP> and <SAMP>std::replace_if()</SAMP> can be used to replace elements of a <B><I><A HREF="../stdlibref/list.html">list</A></I></B> with specific values (<A HREF="13-4.html#1342">Section 13.4.2</A>). Rotations and partitions can also be performed with <B><I>list</I></B>s (<A HREF="13-4.html#1343">Section 13.4.3</A> and <A HREF="13-4.html#1344">Section 13.4.4</A>):</P> |
| |
| <UL><PRE> |
| // find the location of the value 5, and rotate around it |
| |
| std::list<int>::iterator location = |
| std::find(list_ten.begin(), list_ten.end(), 5); |
| std::rotate(list_ten.begin(), location, list_ten.end()); |
| |
| // now partition using values greater than 7 std::partition(list_ten.begin(), list_ten.end(), |
| std::bind2nd(std::greater<int>(), 7)); |
| </PRE></UL> |
| <P>The functions <SAMP>std::next_permutation()</SAMP> and <SAMP>std::prev_permutation()</SAMP> can be used to generate the next permutation (or previous permutation) of a collection of values (<A HREF="13-4.html#1345">Section 13.4.5</A>):</P> |
| |
| <UL><PRE> |
| std::next_permutation(list_ten.begin(), list_ten.end()); |
| </PRE></UL> |
| <A NAME="6211"><H3>6.2.11 Other Operations</H3></A> |
| <P>The algorithm <SAMP>std::for_each()</SAMP> applies a function to every element of a collection (<A HREF="13-8.html">Section 13.8</A>). An illustration of this use is given in the radix sort example program in the section on the <B><I><A HREF="../stdlibref/deque.html">deque</A></I></B> data structure (<A HREF="7-3.html">Section 7.3</A>).</P> |
| <P>The <SAMP>std::accumulate()</SAMP> generic algorithm reduces a collection to a scalar value (<A HREF="13-6.html#1362">Chapter 13.6.2</A>). This can be used, for example, to compute the sum of a list of numbers. A more unusual use of <SAMP>std::accumulate()</SAMP> is illustrated in the radix sort example from <A HREF="7-3.html">Section 7.3</A>:</P> |
| |
| <UL><PRE> |
| std::cout << "Sum of list is: " |
| << std::accumulate(list_ten.begin(),list_ten.end(),0) |
| << std::endl; |
| </PRE></UL> |
| <P>Two <B><I><A HREF="../stdlibref/list.html">list</A></I></B>s can be compared against each other using the <SAMP>std::lexicographical_compare()</SAMP> algorithm (<A HREF="13-6.html#1365">Section 13.6.5</A>). The <B><I>list</I></B>s are equal if they are the same size and all corresponding elements are equal. A <B><I>list</I></B> is less than another <B><I>list</I></B> if it is lexicographically smaller.</P> |
| |
| <BR> |
| <HR> |
| <A HREF="6-1.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="6-3.html"><IMG SRC="images/bnext.gif" WIDTH=20 HEIGHT=21 ALT="Next file" BORDER=O></A> |
| |
| <!-- Google Analytics tracking code --> |
| <script src="http://www.google-analytics.com/urchin.js" type="text/javascript"> |
| </script> |
| <script type="text/javascript"> |
| _uacct = "UA-1775151-1"; |
| urchinTracker(); |
| </script> |
| <!-- end of Google Analytics tracking code --> |
| |
| </BODY> |
| </HTML> |
