3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
4 <title>stable_partition</title>
5 <link rel="stylesheet" href="../../../../../../../../doc/src/boostbook.css" type="text/css">
6 <meta name="generator" content="DocBook XSL Stylesheets V1.75.2">
7 <link rel="home" href="../../../../index.html" title="Chapter 1. Range 2.0">
8 <link rel="up" href="../mutating.html" title="Mutating algorithms">
9 <link rel="prev" href="sort.html" title="sort">
10 <link rel="next" href="stable_sort.html" title="stable_sort">
12 <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
13 <table cellpadding="2" width="100%"><tr>
14 <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../../../boost.png"></td>
15 <td align="center"><a href="../../../../../../../../index.html">Home</a></td>
16 <td align="center"><a href="../../../../../../../../libs/libraries.htm">Libraries</a></td>
17 <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
18 <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
19 <td align="center"><a href="../../../../../../../../more/index.htm">More</a></td>
22 <div class="spirit-nav">
23 <a accesskey="p" href="sort.html"><img src="../../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../mutating.html"><img src="../../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../../index.html"><img src="../../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="stable_sort.html"><img src="../../../../../../../../doc/src/images/next.png" alt="Next"></a>
26 <div class="titlepage"><div><div><h5 class="title">
27 <a name="range.reference.algorithms.mutating.stable_partition"></a><a class="link" href="stable_partition.html" title="stable_partition">stable_partition</a>
28 </h5></div></div></div>
29 <a name="range.reference.algorithms.mutating.stable_partition.prototype"></a><h6>
30 <a name="id704324"></a>
31 <a class="link" href="stable_partition.html#range.reference.algorithms.mutating.stable_partition.prototype">Prototype</a>
36 <pre class="programlisting"><span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">ForwardRange</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">UnaryPredicate</span><span class="special">></span>
37 <span class="keyword">typename</span> <span class="identifier">range_iterator</span><span class="special"><</span><span class="identifier">ForwardRange</span><span class="special">>::</span><span class="identifier">type</span>
38 <span class="identifier">stable_partition</span><span class="special">(</span><span class="identifier">ForwardRange</span><span class="special">&</span> <span class="identifier">rng</span><span class="special">,</span> <span class="identifier">UnaryPredicate</span> <span class="identifier">pred</span><span class="special">);</span>
40 <span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">ForwardRange</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">UnaryPredicate</span><span class="special">></span>
41 <span class="keyword">typename</span> <span class="identifier">range_iterator</span><span class="special"><</span><span class="keyword">const</span> <span class="identifier">ForwardRange</span><span class="special">>::</span><span class="identifier">type</span>
42 <span class="identifier">stable_partition</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">ForwardRange</span><span class="special">&</span> <span class="identifier">rng</span><span class="special">,</span> <span class="identifier">UnaryPredicate</span> <span class="identifier">pred</span><span class="special">);</span>
44 <span class="keyword">template</span><span class="special"><</span>
45 <span class="identifier">range_return_value</span> <span class="identifier">re</span><span class="special">,</span>
46 <span class="keyword">class</span> <span class="identifier">ForwardRange</span><span class="special">,</span>
47 <span class="keyword">class</span> <span class="identifier">UnaryPredicate</span>
48 <span class="special">></span>
49 <span class="keyword">typename</span> <span class="identifier">range_return</span><span class="special"><</span><span class="identifier">ForwardRange</span><span class="special">,</span> <span class="identifier">re</span><span class="special">>::</span><span class="identifier">type</span>
50 <span class="identifier">stable_partition</span><span class="special">(</span><span class="identifier">ForwardRange</span><span class="special">&</span> <span class="identifier">rng</span><span class="special">,</span> <span class="identifier">UnaryPredicate</span> <span class="identifier">pred</span><span class="special">);</span>
52 <span class="keyword">template</span><span class="special"><</span>
53 <span class="identifier">range_return_value</span> <span class="identifier">re</span><span class="special">,</span>
54 <span class="keyword">class</span> <span class="identifier">ForwardRange</span><span class="special">,</span>
55 <span class="keyword">class</span> <span class="identifier">UnaryPredicate</span>
56 <span class="special">></span>
57 <span class="keyword">typename</span> <span class="identifier">range_return</span><span class="special"><</span><span class="keyword">const</span> <span class="identifier">ForwardRange</span><span class="special">,</span> <span class="identifier">re</span><span class="special">>::</span><span class="identifier">type</span>
58 <span class="identifier">stable_partition</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">ForwardRange</span><span class="special">&</span> <span class="identifier">rng</span><span class="special">,</span> <span class="identifier">UnaryPredicate</span> <span class="identifier">pred</span><span class="special">);</span>
62 <a name="range.reference.algorithms.mutating.stable_partition.description"></a><h6>
63 <a name="id704898"></a>
64 <a class="link" href="stable_partition.html#range.reference.algorithms.mutating.stable_partition.description">Description</a>
67 <code class="computeroutput"><span class="identifier">stable_partition</span></code> reorders
68 the elements in the range <code class="computeroutput"><span class="identifier">rng</span></code>
69 base on the function object <code class="computeroutput"><span class="identifier">pred</span></code>.
70 Once this function has completed all of the elements that satisfy <code class="computeroutput"><span class="identifier">pred</span></code> appear before all of the elements
71 that fail to satisfy it. <code class="computeroutput"><span class="identifier">stable_partition</span></code>
72 differs from <code class="computeroutput"><span class="identifier">partition</span></code>
73 because it preserves relative order. It is stable.
76 For the versions that return an iterator, the return value is the iterator
77 to the first element that fails to satisfy <code class="computeroutput"><span class="identifier">pred</span></code>.
80 For versions that return a <code class="computeroutput"><span class="identifier">range_return</span></code>,
81 the <code class="computeroutput"><span class="identifier">found</span></code> iterator is
82 the iterator to the first element that fails to satisfy <code class="computeroutput"><span class="identifier">pred</span></code>.
84 <a name="range.reference.algorithms.mutating.stable_partition.definition"></a><h6>
85 <a name="id705039"></a>
86 <a class="link" href="stable_partition.html#range.reference.algorithms.mutating.stable_partition.definition">Definition</a>
89 Defined in the header file <code class="computeroutput"><span class="identifier">boost</span><span class="special">/</span><span class="identifier">range</span><span class="special">/</span><span class="identifier">algorithm</span><span class="special">/</span><span class="identifier">stable_partition</span><span class="special">.</span><span class="identifier">hpp</span></code>
91 <a name="range.reference.algorithms.mutating.stable_partition.requirements"></a><h6>
92 <a name="id705110"></a>
93 <a class="link" href="stable_partition.html#range.reference.algorithms.mutating.stable_partition.requirements">Requirements</a>
95 <div class="itemizedlist"><ul class="itemizedlist" type="disc">
97 <code class="computeroutput"><span class="identifier">ForwardRange</span></code> is a
98 model of the <a class="link" href="../../../concepts/forward_range.html" title="Forward Range">Forward
101 <li class="listitem">
102 <code class="computeroutput"><span class="identifier">ForwardRange</span></code> is mutable.
104 <li class="listitem">
105 <code class="computeroutput"><span class="identifier">UnaryPredicate</span></code> is
106 a model of the <code class="computeroutput"><span class="identifier">PredicateConcept</span></code>.
109 <a name="range.reference.algorithms.mutating.stable_partition.complexity"></a><h6>
110 <a name="id705203"></a>
111 <a class="link" href="stable_partition.html#range.reference.algorithms.mutating.stable_partition.complexity">Complexity</a>
114 Best case: <code class="computeroutput"><span class="identifier">O</span><span class="special">(</span><span class="identifier">N</span><span class="special">)</span></code>
115 where <code class="computeroutput"><span class="identifier">N</span></code> is <code class="computeroutput"><span class="identifier">distance</span><span class="special">(</span><span class="identifier">rng</span><span class="special">)</span></code>.
116 Worst case: <code class="computeroutput"><span class="identifier">N</span> <span class="special">*</span>
117 <span class="identifier">log</span><span class="special">(</span><span class="identifier">N</span><span class="special">)</span></code>
118 swaps, where <code class="computeroutput"><span class="identifier">N</span></code> is <code class="computeroutput"><span class="identifier">distance</span><span class="special">(</span><span class="identifier">rng</span><span class="special">)</span></code>.
121 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
122 <td align="left"></td>
123 <td align="right"><div class="copyright-footer">Copyright © 2003 -2010 Thorsten Ottosen, Neil Groves<p>
124 Distributed under the Boost Software License, Version 1.0. (See accompanying
125 file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
130 <div class="spirit-nav">
131 <a accesskey="p" href="sort.html"><img src="../../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../mutating.html"><img src="../../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../../index.html"><img src="../../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="stable_sort.html"><img src="../../../../../../../../doc/src/images/next.png" alt="Next"></a>