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.78.1">
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>
30 <a name="range.reference.algorithms.mutating.stable_partition.h0"></a>
31 <span class="phrase"><a name="range.reference.algorithms.mutating.stable_partition.prototype"></a></span><a class="link" href="stable_partition.html#range.reference.algorithms.mutating.stable_partition.prototype">Prototype</a>
35 <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>
36 <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>
37 <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>
39 <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>
40 <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>
41 <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>
43 <span class="keyword">template</span><span class="special"><</span>
44 <span class="identifier">range_return_value</span> <span class="identifier">re</span><span class="special">,</span>
45 <span class="keyword">class</span> <span class="identifier">ForwardRange</span><span class="special">,</span>
46 <span class="keyword">class</span> <span class="identifier">UnaryPredicate</span>
47 <span class="special">></span>
48 <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>
49 <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>
51 <span class="keyword">template</span><span class="special"><</span>
52 <span class="identifier">range_return_value</span> <span class="identifier">re</span><span class="special">,</span>
53 <span class="keyword">class</span> <span class="identifier">ForwardRange</span><span class="special">,</span>
54 <span class="keyword">class</span> <span class="identifier">UnaryPredicate</span>
55 <span class="special">></span>
56 <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>
57 <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.h1"></a>
63 <span class="phrase"><a name="range.reference.algorithms.mutating.stable_partition.description"></a></span><a class="link" href="stable_partition.html#range.reference.algorithms.mutating.stable_partition.description">Description</a>
66 <code class="computeroutput"><span class="identifier">stable_partition</span></code> reorders
67 the elements in the range <code class="computeroutput"><span class="identifier">rng</span></code>
68 base on the function object <code class="computeroutput"><span class="identifier">pred</span></code>.
69 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
70 that fail to satisfy it. <code class="computeroutput"><span class="identifier">stable_partition</span></code>
71 differs from <code class="computeroutput"><span class="identifier">partition</span></code>
72 because it preserves relative order. It is stable.
75 For the versions that return an iterator, the return value is the iterator
76 to the first element that fails to satisfy <code class="computeroutput"><span class="identifier">pred</span></code>.
79 For versions that return a <code class="computeroutput"><span class="identifier">range_return</span></code>,
80 the <code class="computeroutput"><span class="identifier">found</span></code> iterator is
81 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.h2"></a>
85 <span class="phrase"><a name="range.reference.algorithms.mutating.stable_partition.definition"></a></span><a class="link" href="stable_partition.html#range.reference.algorithms.mutating.stable_partition.definition">Definition</a>
88 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.h3"></a>
92 <span class="phrase"><a name="range.reference.algorithms.mutating.stable_partition.requirements"></a></span><a class="link" href="stable_partition.html#range.reference.algorithms.mutating.stable_partition.requirements">Requirements</a>
94 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
96 <code class="computeroutput"><span class="identifier">ForwardRange</span></code> is a
97 model of the <a class="link" href="../../../concepts/forward_range.html" title="Forward Range">Forward
100 <li class="listitem">
101 <code class="computeroutput"><span class="identifier">ForwardRange</span></code> is mutable.
103 <li class="listitem">
104 <code class="computeroutput"><span class="identifier">UnaryPredicate</span></code> is
105 a model of the <code class="computeroutput"><span class="identifier">PredicateConcept</span></code>.
109 <a name="range.reference.algorithms.mutating.stable_partition.h4"></a>
110 <span class="phrase"><a name="range.reference.algorithms.mutating.stable_partition.complexity"></a></span><a class="link" href="stable_partition.html#range.reference.algorithms.mutating.stable_partition.complexity">Complexity</a>
113 Best case: <code class="computeroutput"><span class="identifier">O</span><span class="special">(</span><span class="identifier">N</span><span class="special">)</span></code>
114 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>.
115 Worst case: <code class="computeroutput"><span class="identifier">N</span> <span class="special">*</span>
116 <span class="identifier">log</span><span class="special">(</span><span class="identifier">N</span><span class="special">)</span></code>
117 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>.
120 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
121 <td align="left"></td>
122 <td align="right"><div class="copyright-footer">Copyright © 2003-2010 Thorsten Ottosen,
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>