libs/algorithm/doc/html/the_boost_algorithm_library/CXX11/partition_point.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   4 <title>partition_point</title>
   5 <link rel="stylesheet" href="../../../../../../doc/src/boostbook.css" type="text/css">
   6 <meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
   7 <link rel="home" href="../../index.html" title="The Boost Algorithm Library">
   8 <link rel="up" href="../../algorithm/CXX11.html" title="C++11 Algorithms">
   9 <link rel="prev" href="is_permutation.html" title="is_permutation">
  10 <link rel="next" href="../../algorithm/CXX14.html" title="C++14 Algorithms">
  11 </head>
  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>
  20 </tr></table>
  21 <hr>
  22 <div class="spirit-nav">
  23 <a accesskey="p" href="is_permutation.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../../algorithm/CXX11.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="../../algorithm/CXX14.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
  24 </div>
  25 <div class="section">
  26 <div class="titlepage"><div><div><h3 class="title">
  27 <a name="the_boost_algorithm_library.CXX11.partition_point"></a><a class="link" href="partition_point.html" title="partition_point">partition_point
  28       </a>
  29 </h3></div></div></div>
  30 <p>
  31         The header file 'partition_point.hpp' contains two variants of a single algorithm,
  32         <code class="computeroutput"><span class="identifier">partition_point</span></code>. Given a
  33         partitioned sequence and a predicate, the algorithm finds the partition point;
  34         i.e, the first element in the sequence that does not satisfy the predicate.
  35       </p>
  36 <p>
  37         The routine <code class="computeroutput"><span class="identifier">partition_point</span></code>
  38         takes a partitioned sequence and a predicate. It returns an iterator which
  39         'points to' the first element in the sequence that does not satisfy the predicate.
  40         If all the items in the sequence satisfy the predicate, then it returns one
  41         past the final element in the sequence.
  42       </p>
  43 <p>
  44         <code class="computeroutput"><span class="identifier">partition_point</span></code> come in two
  45         forms; the first one takes two iterators to define the range. The second
  46         form takes a single range parameter, and uses Boost.Range to traverse it.
  47       </p>
  48 <h5>
  49 <a name="the_boost_algorithm_library.CXX11.partition_point.h0"></a>
  50         <span class="phrase"><a name="the_boost_algorithm_library.CXX11.partition_point.interface"></a></span><a class="link" href="partition_point.html#the_boost_algorithm_library.CXX11.partition_point.interface">interface</a>
  51       </h5>
  52 <p>
  53         There are two versions; one takes two iterators, and the other takes a range.
  54       </p>
  55 <p>
  56 </p>
  57 <pre class="programlisting"><span class="keyword">template</span><span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">ForwardIterator</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Predicate</span><span class="special">&gt;</span>
  58         <span class="identifier">ForwardIterator</span> <span class="identifier">partition_point</span> <span class="special">(</span> <span class="identifier">ForwardIterator</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">ForwardIterator</span> <span class="identifier">last</span><span class="special">,</span> <span class="identifier">Predicate</span> <span class="identifier">p</span> <span class="special">);</span>
  59 <span class="keyword">template</span><span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">Range</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Predicate</span><span class="special">&gt;</span>
  60         <span class="identifier">boost</span><span class="special">::</span><span class="identifier">range_iterator</span><span class="special">&lt;</span><span class="identifier">Range</span><span class="special">&gt;</span> <span class="identifier">partition_point</span> <span class="special">(</span> <span class="keyword">const</span> <span class="identifier">Range</span> <span class="special">&amp;</span><span class="identifier">r</span><span class="special">,</span> <span class="identifier">Predicate</span> <span class="identifier">p</span> <span class="special">);</span>
  61 </pre>
  62 <p>
  63       </p>
  64 <h5>
  65 <a name="the_boost_algorithm_library.CXX11.partition_point.h1"></a>
  66         <span class="phrase"><a name="the_boost_algorithm_library.CXX11.partition_point.examples"></a></span><a class="link" href="partition_point.html#the_boost_algorithm_library.CXX11.partition_point.examples">Examples</a>
  67       </h5>
  68 <p>
  69         Given the container <code class="computeroutput"><span class="identifier">c</span></code> containing
  70         <code class="computeroutput"><span class="special">{</span> <span class="number">0</span><span class="special">,</span> <span class="number">1</span><span class="special">,</span>
  71         <span class="number">2</span><span class="special">,</span> <span class="number">3</span><span class="special">,</span> <span class="number">14</span><span class="special">,</span> <span class="number">15</span> <span class="special">}</span></code>,
  72         then
  73 </p>
  74 <pre class="programlisting"><span class="keyword">bool</span> <span class="identifier">lessThan10</span> <span class="special">(</span> <span class="keyword">int</span> <span class="identifier">i</span> <span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">i</span> <span class="special">&lt;</span> <span class="number">10</span><span class="special">;</span> <span class="special">}</span>
  75 <span class="keyword">bool</span> <span class="identifier">isOdd</span> <span class="special">(</span> <span class="keyword">int</span> <span class="identifier">i</span> <span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">i</span> <span class="special">%</span> <span class="number">2</span> <span class="special">==</span> <span class="number">1</span><span class="special">;</span> <span class="special">}</span>
  76
  77 <span class="identifier">partition_point</span> <span class="special">(</span> <span class="identifier">c</span><span class="special">,</span> <span class="identifier">lessThan10</span> <span class="special">)</span> <span class="special">--&gt;</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span> <span class="special">()</span> <span class="special">+</span> <span class="number">4</span>  <span class="special">(</span><span class="identifier">pointing</span> <span class="identifier">at</span> <span class="number">14</span><span class="special">)</span>
  78 <span class="identifier">partition_point</span> <span class="special">(</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span> <span class="special">(),</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span> <span class="special">(),</span> <span class="identifier">lessThan10</span> <span class="special">)</span> <span class="special">--&gt;</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span> <span class="special">()</span> <span class="special">+</span> <span class="number">4</span>  <span class="special">(</span><span class="identifier">pointing</span> <span class="identifier">at</span> <span class="number">14</span><span class="special">)</span>
  79 <span class="identifier">partition_point</span> <span class="special">(</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span> <span class="special">(),</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span> <span class="special">()</span> <span class="special">+</span> <span class="number">3</span><span class="special">,</span> <span class="identifier">lessThan10</span> <span class="special">)</span> <span class="special">-&gt;</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span> <span class="special">()</span> <span class="special">+</span> <span class="number">3</span> <span class="special">(</span><span class="identifier">end</span><span class="special">)</span>
  80 <span class="identifier">partition_point</span> <span class="special">(</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span> <span class="special">(),</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span> <span class="special">(),</span> <span class="identifier">isOdd</span> <span class="special">)</span> <span class="special">--&gt;</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span> <span class="special">()</span>  <span class="comment">// empty range</span>
  81 </pre>
  82 <p>
  83       </p>
  84 <h5>
  85 <a name="the_boost_algorithm_library.CXX11.partition_point.h2"></a>
  86         <span class="phrase"><a name="the_boost_algorithm_library.CXX11.partition_point.iterator_requirements"></a></span><a class="link" href="partition_point.html#the_boost_algorithm_library.CXX11.partition_point.iterator_requirements">Iterator
  87         Requirements</a>
  88       </h5>
  89 <p>
  90         <code class="computeroutput"><span class="identifier">partition_point</span></code> requires
  91         forward iterators or better; it will not work on input iterators or output
  92         iterators.
  93       </p>
  94 <h5>
  95 <a name="the_boost_algorithm_library.CXX11.partition_point.h3"></a>
  96         <span class="phrase"><a name="the_boost_algorithm_library.CXX11.partition_point.complexity"></a></span><a class="link" href="partition_point.html#the_boost_algorithm_library.CXX11.partition_point.complexity">Complexity</a>
  97       </h5>
  98 <p>
  99         Both of the variants of <code class="computeroutput"><span class="identifier">partition_point</span></code>
 100         run in <span class="emphasis"><em>O( log (N))</em></span> (logarithmic) time; that is, the
 101         predicate will be will be applied approximately <span class="emphasis"><em>log(N)</em></span>
 102         times. To do this, however, the algorithm needs to know the size of the sequence.
 103         For forward and bidirectional iterators, calculating the size of the sequence
 104         is an <span class="emphasis"><em>O(N)</em></span> operation.
 105       </p>
 106 <h5>
 107 <a name="the_boost_algorithm_library.CXX11.partition_point.h4"></a>
 108         <span class="phrase"><a name="the_boost_algorithm_library.CXX11.partition_point.exception_safety"></a></span><a class="link" href="partition_point.html#the_boost_algorithm_library.CXX11.partition_point.exception_safety">Exception
 109         Safety</a>
 110       </h5>
 111 <p>
 112         Both of the variants of <code class="computeroutput"><span class="identifier">partition_point</span></code>
 113         take their parameters by value or const reference, and do not depend upon
 114         any global state. Therefore, all the routines in this file provide the strong
 115         exception guarantee.
 116       </p>
 117 <h5>
 118 <a name="the_boost_algorithm_library.CXX11.partition_point.h5"></a>
 119         <span class="phrase"><a name="the_boost_algorithm_library.CXX11.partition_point.notes"></a></span><a class="link" href="partition_point.html#the_boost_algorithm_library.CXX11.partition_point.notes">Notes</a>
 120       </h5>
 121 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
 122 <li class="listitem">
 123             The iterator-based version of the routine <code class="computeroutput"><span class="identifier">partition_point</span></code>
 124             is also available as part of the C++11 standard.
 125           </li>
 126 <li class="listitem">
 127             For empty ranges, the partition point is the end of the range.
 128           </li>
 129 </ul></div>
 130 </div>
 131 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 132 <td align="left"></td>
 133 <td align="right"><div class="copyright-footer">Copyright &#169; 2010-2012 Marshall Clow<p>
 134         Distributed under the Boost Software License, Version 1.0. (See accompanying
 135         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>)
 136       </p>
 137 </div></td>
 138 </tr></table>
 139 <hr>
 140 <div class="spirit-nav">
 141 <a accesskey="p" href="is_permutation.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../../algorithm/CXX11.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="../../algorithm/CXX14.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
 142 </div>
 143 </body>
 144 </html>