📄 ove_6146.htm
字号:
<HTML><HEAD><TITLE>14.1 Overview</TITLE></HEAD><BODY><A HREF="ug1.htm"><IMG SRC="images/banner.gif"></A><BR><A HREF="ord_1635.htm"><IMG SRC="images/prev.gif"></A><A HREF="booktoc1.htm"><IMG SRC="images/toc.gif"></A><A HREF="tindex1.htm"><IMG SRC="images/tindex.gif"></A><A HREF="sor_5132.htm"><IMG SRC="images/next.gif"></A><BR><STRONG>Click on the banner to return to the user guide home page.</STRONG><H2>14.1 Overview</H2><A NAME="idx168"><!></A><P>In this section we will describe the generic algorithms in the standard library that are specific to ordered collections. These are summarized by the following table:</P><CENTER><TABLE BORDER CELLSPACING=3 CELLPADDING=3><TR VALIGN=top><TD>Name<BR></TD><TD>Purpose<BR></TD></TR><TR VALIGN=top><TD><B>Sorting Algorithms - Sections <A HREF="sor_5132.htm">14.2</A> and <A HREF="par_1934.htm">14.3</A></B><BR></TD></TR><TR VALIGN=top><TD><SAMP>sort</SAMP><BR></TD><TD>rearrange sequence, place in order<BR></TD></TR><TR VALIGN=top><TD><SAMP>stable_sort</SAMP><BR></TD><TD>sort, retaining original order of equal elements<BR></TD></TR><TR VALIGN=top><TD><SAMP>partial_sort</SAMP><BR></TD><TD>sort only part of sequence<BR></TD></TR><TR VALIGN=top><TD><SAMP>partial_sort_copy</SAMP><BR></TD><TD>partial sort into copy<BR></TD></TR><TR VALIGN=top><TD><B>Find Nth largest Element - <A HREF="nth_1433.htm">Section 14.4</A></B><BR></TD></TR><TR VALIGN=top><TD><SAMP>nth_element</SAMP><BR></TD><TD>locate nth largest element<BR></TD></TR><TR VALIGN=top><TD><B>Binary Search - <A HREF="bin_2092.htm">Section 14.5</A></B><BR></TD></TR><TR VALIGN=top><TD><SAMP>binary_search</SAMP><BR></TD><TD>search, returning boolean<BR></TD></TR><TR VALIGN=top><TD><SAMP>lower_bound</SAMP><BR></TD><TD>search, returning first position<BR></TD></TR><TR VALIGN=top><TD><SAMP>upper_bound</SAMP><BR></TD><TD>search, returning last position<BR></TD></TR><TR VALIGN=top><TD><SAMP>equal_range</SAMP><BR></TD><TD>search, returning both positions<BR></TD></TR><TR VALIGN=top><TD><B>Merge Ordered Sequences - <A HREF="mer_3553.htm">Section 14.6</A></B><BR></TD></TR><TR VALIGN=top><TD><SAMP>merge</SAMP><BR></TD><TD>combine two ordered sequences<BR></TD></TR><TR VALIGN=top><TD><B>Set Operations - <A HREF="set_1753.htm">Section 14.7</A></B><BR></TD></TR><TR VALIGN=top><TD><SAMP>set_union</SAMP><BR></TD><TD>form union of two sets<BR></TD></TR><TR VALIGN=top><TD><SAMP>set_intersection</SAMP><BR></TD><TD> form intersection of two sets<BR></TD></TR><TR VALIGN=top><TD><SAMP>set_difference</SAMP><BR></TD><TD>form difference of two sets<BR></TD></TR><TR VALIGN=top><TD><SAMP>set_symmetric_difference</SAMP><BR></TD><TD>form symmetric difference of two sets<BR></TD></TR><TR VALIGN=top><TD><SAMP>includes</SAMP><BR></TD><TD>see if one set is a subset of another<BR></TD></TR><TR VALIGN=top><TD><B>Heap operations - <A HREF="hea_8081.htm">Section 14.8</A></B><BR></TD></TR><TR VALIGN=top><TD><SAMP>make_heap</SAMP><BR></TD><TD>turn a sequence into a heap<BR></TD></TR><TR VALIGN=top><TD><SAMP>push_heap</SAMP><BR></TD><TD>add a new value to the heap<BR></TD></TR><TR VALIGN=top><TD><SAMP>pop_heap</SAMP><BR></TD><TD>remove largest value from the heap<BR></TD></TR><TR VALIGN=top><TD><SAMP>sort_heap</SAMP><BR></TD><TD>turn heap into sorted collection<BR></TD></TR></TABLE></CENTER><P>Ordered collections can be created using the standard library in a variety of ways. For example:</P><UL><LI>The containers <A HREF="../stdlibcr/set_1649.htm"><B><I>set</I></B></A>, <A HREF="../stdlibcr/mul_0958.htm"><B><I>multiset</I></B></A>, <A HREF="../stdlibcr/map_8018.htm"><B><I>map</I></B></A> and <A HREF="../stdlibcr/mul_8396.htm"><B><I>multimap</I></B></A> are ordered collections by definition.</LI><LI>A <A HREF="../stdlibcr/lis_3222.htm"><B><I>list</I></B></A> can be ordered by invoking the <SAMP>sort()</SAMP> member function.</LI><LI>A <A HREF="../stdlibcr/vec_0251.htm"><B><I>vector</I></B></A>, <A HREF="../stdlibcr/deq_4164.htm"><B><I>deque</I></B></A> or ordinary C++ array can be ordered by using one of the sorting algorithms described later in this section.</LI></UL><P>Like the generic algorithms described in the previous section, the algorithms described here are not specific to any particular container class. This means they can be used with a wide variety of types. Many of them do, however, require the use of random-access iterators. For this reason they are most easily used with vectors, deques, or ordinary arrays.</P><A HREF="sidebar1.htm#sidebar73"><IMG SRC="images/note.gif" BORDER=0> <STRONG>Obtaining the Sample Programs</STRONG></A><P>Almost all the algorithms described in this section have two versions. The first version uses the<SAMP> less than</SAMP> operator (operator <SAMP><</SAMP>) for comparisons appropriate to the container element type. The second, and more general, version uses an explicit comparison function object, which we will write as <SAMP>Compare</SAMP>. This function object must be a binary predicate (see <A HREF="pre_1157.htm">Section 3.2</A>). Since this argument is optional, we will write it within square brackets in the description of the argument types.</P><P>A sequence is considered to be ordered if for every valid (that is, denotable) iterator <SAMP>i</SAMP> with a denotable successor<SAMP> j</SAMP>, it is the case that the comparison <SAMP>Compare(*j, *i)</SAMP> is false. Note that this does not necessarily imply that <SAMP>Compare(*i, *j)</SAMP> is true. It is assumed that the relation imposed by <SAMP>Compare</SAMP> is transitive, and induces a total ordering on the values.</P><P>In the descriptions that follow, two values <SAMP>x</SAMP> and <SAMP>y</SAMP> are said to be equivalent if both <SAMP>Compare(x, y)</SAMP> and <SAMP>Compare(y, x)</SAMP> are false. Note that this need not imply that <SAMP>x == y</SAMP>.</P><A NAME="14.1.1"><H3>14.1.1 Include Files</H3></A><P>As with the algorithms described in Section 13, before you can use any of the algorithms described in this section in a program you must include the <SAMP>algorithm</SAMP> header file:</P><PRE> # include <algorithm></PRE><HR><A HREF="ord_1635.htm"><IMG SRC="images/prev.gif"></A> <A HREF="booktoc1.htm"><IMG SRC="images/toc.gif"></A><A HREF="tindex1.htm"><IMG SRC="images/tindex.gif"></A><A HREF="sor_5132.htm"><IMG SRC="images/next.gif"></A><P>©Copyright 1996, Rogue Wave Software, Inc.</P></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -