📄 par_1563.htm
字号:
<HTML><TITLE>partial_sort_copy</TITLE><BODY>
<A HREF="ref.htm"><IMG SRC="images/banner.gif"></A>
<P><STRONG>Click on the banner to return to the Class Reference home page.</STRONG></P>
<P>©Copyright 1996 Rogue Wave Software</P>
<H2>partial_sort_copy</H2>
<HR><PRE> Algorithm</PRE><HR>
<A NAME="Summary"><H3>Summary</H3></A>
<P>Templated algorithm for sorting collections of entities.</P>
<PRE></PRE>
<H3>Contents</H3>
<UL>
<A HREF="#Synopsis"><LI>Synopsis</LI></A>
<A HREF="#Description"><LI>Description</LI></A>
<A HREF="#Complexity"><LI>Complexity</LI></A>
<A HREF="#Example"><LI>Example</LI></A>
<A HREF="#Warning"><LI>Warning</LI></A>
<A HREF="#See Also"><LI>See Also</LI></A>
</UL>
<A NAME="Synopsis"><H3>Synopsis</H3></A>
<PRE>#include <algorithm>
template <class InputIterator,
class RandomAccessIterator>
void <B>partial_sort_copy</B> (InputIterator first,
InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);</PRE><PRE>template <class InputIterator,
class RandomAccessIterator,
class Compare>
void <B>partial_sort_copy</B> (InputIterator first,
InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last,
Compare comp);</PRE>
<A NAME="Description"><H3>Description</H3></A>
<P>The <B><I>partial_sort_copy</B></I> algorithm places the smaller of <SAMP>last - first</SAMP> and <SAMP>result_last - result_first</SAMP> sorted elements from the range <SAMP>[first, last)</SAMP> into the range beginning at <SAMP>result_first</SAMP>. (i.e., the range: <SAMP>[result_first, result_first+min(last - first, result_last - result_first))</SAMP>. Basically, the effect is as if the range <SAMP>[first,last)</SAMP> were placed in a temporary buffer, sorted and then as many elements as possible were coppied into the range <SAMP>[result_first, result_last)</SAMP>.</P>
<P>The first version of the algorithm uses less than (<SAMP>operator<</SAMP>) as the comparison operator for the sort. The second version uses the comparision function <SAMP>comp.</SAMP></P>
<A NAME="Complexity"><H3>Complexity</H3></A>
<P><B><I>partial_sort_copy</B></I> does approximately<SAMP> (last-first) * log(min(last-first, result_last-result_first))</SAMP> comparisons.</P>
<A NAME="Example"><H3>Example</H3></A>
<PRE>//
// partsort.cpp
// #include <vector>
#include <algorithm>
#include <iostream.h></PRE><PRE> int main()
{
int d1[20] = {17, 3, 5, -4, 1, 12, -10, -1, 14, 7,
-6, 8, 15, -11, 2, -2, 18, 4, -3, 0};
//
// Set up a vector.
//
vector<int> v1(d1+0, d1+20);
//
// Output original vector.
//
cout << "For the vector: ";
copy(v1.begin(), v1.end(), ostream_iterator<int>(cout," "));
//
// Partial sort the first seven elements.
//
partial_sort(v1.begin(), v1.begin()+7, v1.end());
//
// Output result.
//
cout << endl << endl << "A partial_sort of 7 elements gives: "
<< endl << " ";
copy(v1.begin(), v1.end(), ostream_iterator<int>(cout," "));
cout << endl;
//
// A vector of ten elements.
//
vector<int> v2(10, 0);
//
// Sort the last ten elements in v1 into v2.
//
<B>partial_sort_copy</B>(v1.begin()+10, v1.end(), v2.begin(), v2.end());</PRE>
<PRE> //
// Output result.
//
cout << endl << "A partial_sort_copy of the last ten elements gives: " << endl << " ";</PRE>
<PRE> copy(v2.begin(), v2.end(), ostream_iterator<int>(cout," "));
cout << endl;</PRE><PRE> return 0;
}</PRE>
<PRE>Output :
For the vector: 17 3 5 -4 1 12 -10 -1 14 7 -6 8 15 -11 2 -2 18 4 -3 0
A partial_sort of seven elements gives:
-11 -10 -6 -4 -3 -2 -1 17 14 12 7 8 15 5 3 2 18 4 1 0
A partial_sort_copy of the last ten elements gives:
0 1 2 3 4 5 7 8 15 18
</PRE>
<A NAME="Warning"><H3>Warning</H3></A>
<P>If your compiler does not support default template parameters, then you need to always provide the <SAMP>Allocator</SAMP> template argument. For instance, you will need to write :</P>
<P><SAMP>vector<int, allocator></SAMP></P>
<P>instead of :</P>
<P><SAMP>vector<int></SAMP></P>
<A NAME="See Also"><H3>See Also</H3></A>
<P><A HREF="sor_1439.htm"><B><I>sort</B></I></A>_ <A HREF="sta_5767.htm"><B><I>stable_sort</B></I></A>, <A HREF="par_4963.htm"><B><I>partial_sort</B></I></A></P>
<HR>
<A HREF="par_4963.htm"><IMG SRC="images/prev.gif"></A> <A HREF="ref.htm#contents"><IMG SRC="images/toc.gif"></A> <A HREF="par_6923.htm"><IMG SRC="images/next.gif"></A></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -