sta_4791.htm
来自「ARM编辑、编译软件」· HTM 代码 · 共 79 行
HTM
79 行
<HTML><TITLE>stable_partition</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>stable_partition</H2>
<HR><PRE> Algorithm</PRE><HR>
<A NAME="Summary"><H3>Summary</H3></A>
<P>Places all of the entities that satisfy the given predicate before all of the entities that do not, while maintaining the relative order of elements in each group.</P>
<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></PRE>
<PRE>
template <class BidirectionalIterator, class Predicate>
BidirectionalIterator
<B>stable_partition</B> (BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred);
</PRE>
<A NAME="Description"><H3>Description</H3></A>
<P>The <B><I>stable_partition</B></I> algorithm places all the elements in the range <SAMP>[first, last)</SAMP> that satisfy <SAMP>pred</SAMP> before all the elements that do not satisfy it. It returns an iterator <SAMP>i</SAMP> that is one past the end of the group of elements that satisfy <SAMP>pred</SAMP>. In other words <B><I>stable_partition</B></I> returns <SAMP>i</SAMP> such that for any iterator <SAMP>j</SAMP> in the range <SAMP>[first, i)</SAMP>, <SAMP>pred(*j) == true</SAMP>, and for any iterator <SAMP>k</SAMP> in the range <SAMP>[i, last)</SAMP>, <SAMP>pred(*j) == false</SAMP>. The relative order of the elements in both groups is preserved. </P>
<P>The <A HREF="par_0264.htm"><B><I>partition</B></I></A> algorithm can be used when it is not necessary to maintain the relative order of elements within the groups that do and do not match the predicate.</P>
<A NAME="Complexity"><H3>Complexity</H3></A>
<P>The <B><I>stable_partition</B></I> algorithm does at most <SAMP>(last - first) * log(last - first)</SAMP> swaps. and applies the predicate exactly <SAMP>last - first</SAMP> times. </P>
<A NAME="Example"><H3>Example</H3></A>
<PRE>//
// prtition.cpp
//
#include <functional>
#include <deque>
#include <algorithm>
#include <iostream.h>
//Create a new predicate from unary_function
template<class Arg>
class is_even : public unary_function<Arg, bool>
{
public:
bool operator()(const Arg& arg1)
{
return (arg1 % 2) == 0;
}
};
int main()
{
//Initialize a deque with an array of ints
int init[10] = {1,2,3,4,5,6,7,8,9,10};
deque<int> d(init, init+10);
//Print out the original values
cout << "Unpartitioned values: " << endl << " ";
copy(d.begin(),d.end(),ostream_iterator<int>(cout," "));
cout << endl << endl;
//Partition the deque according to even/oddness
<B> stable_partition</B>(d.begin(), d.end(), is_even<int>());
//Output result of partition
cout << "Partitioned values: " << endl << " ";
copy(d.begin(),d.end(),ostream_iterator<int>(cout," "));
return 0;
}
Output :
Unpartitioned values: 1 2 3 4 5 6 7 8 9 10
Partitioned values: 10 2 8 4 6 5 7 3 9 1
Stable partitioned values: 2 4 6 8 10 1 3 5 7 9</PRE>
<A NAME="Warning"><H3>Warning</H3></A>
<P>If your compiler does not support default template parameters, then you need to always supply the <SAMP>Allocator</SAMP> template argument. For instance, you will need to write :</P>
<P><SAMP>deque<int, allocator></SAMP></P>
<P>instead of :</P>
<P><SAMP>deque<int></SAMP></P>
<A NAME="See Also"><H3>See Also</H3></A>
<P><A HREF="par_0264.htm"><B><I>partition</B></I></A></P>
<HR>
<A HREF="sor_3899.htm"><IMG SRC="images/prev.gif"></A> <A HREF="ref.htm#contents"><IMG SRC="images/toc.gif"></A> <A HREF="sta_5767.htm"><IMG SRC="images/next.gif"></A></BODY></HTML>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?