<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>partition_point</title>
<link rel="stylesheet" href="../../../../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../../index.html" title="The Boost Algorithm Library">
<link rel="up" href="../../algorithm/CXX11.html" title="C++11 Algorithms">
<link rel="prev" href="is_permutation.html" title="is_permutation">
<link rel="next" href="../../algorithm/CXX14.html" title="C++14 Algorithms">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
<td align="center"><a href="../../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<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>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="the_boost_algorithm_library.CXX11.partition_point"></a><a class="link" href="partition_point.html" title="partition_point">partition_point
      </a>
</h3></div></div></div>
<p>
        The header file 'partition_point.hpp' contains two variants of a single algorithm,
        <code class="computeroutput"><span class="identifier">partition_point</span></code>. Given a
        partitioned sequence and a predicate, the algorithm finds the partition point;
        i.e, the first element in the sequence that does not satisfy the predicate.
      </p>
<p>
        The routine <code class="computeroutput"><span class="identifier">partition_point</span></code>
        takes a partitioned sequence and a predicate. It returns an iterator which
        'points to' the first element in the sequence that does not satisfy the predicate.
        If all the items in the sequence satisfy the predicate, then it returns one
        past the final element in the sequence.
      </p>
<p>
        <code class="computeroutput"><span class="identifier">partition_point</span></code> come in two
        forms; the first one takes two iterators to define the range. The second
        form takes a single range parameter, and uses Boost.Range to traverse it.
      </p>
<h5>
<a name="the_boost_algorithm_library.CXX11.partition_point.h0"></a>
        <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>
      </h5>
<p>
        There are two versions; one takes two iterators, and the other takes a range.
      </p>
<p>
</p>
<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>
	<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>
<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>
	<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>
</pre>
<p>
      </p>
<h5>
<a name="the_boost_algorithm_library.CXX11.partition_point.h1"></a>
        <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>
      </h5>
<p>
        Given the container <code class="computeroutput"><span class="identifier">c</span></code> containing
        <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>
        <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>,
        then
</p>
<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>
<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>

<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>
<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>
<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>
<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>
</pre>
<p>
      </p>
<h5>
<a name="the_boost_algorithm_library.CXX11.partition_point.h2"></a>
        <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
        Requirements</a>
      </h5>
<p>
        <code class="computeroutput"><span class="identifier">partition_point</span></code> requires
        forward iterators or better; it will not work on input iterators or output
        iterators.
      </p>
<h5>
<a name="the_boost_algorithm_library.CXX11.partition_point.h3"></a>
        <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>
      </h5>
<p>
        Both of the variants of <code class="computeroutput"><span class="identifier">partition_point</span></code>
        run in <span class="emphasis"><em>O( log (N))</em></span> (logarithmic) time; that is, the
        predicate will be will be applied approximately <span class="emphasis"><em>log(N)</em></span>
        times. To do this, however, the algorithm needs to know the size of the sequence.
        For forward and bidirectional iterators, calculating the size of the sequence
        is an <span class="emphasis"><em>O(N)</em></span> operation.
      </p>
<h5>
<a name="the_boost_algorithm_library.CXX11.partition_point.h4"></a>
        <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
        Safety</a>
      </h5>
<p>
        Both of the variants of <code class="computeroutput"><span class="identifier">partition_point</span></code>
        take their parameters by value or const reference, and do not depend upon
        any global state. Therefore, all the routines in this file provide the strong
        exception guarantee.
      </p>
<h5>
<a name="the_boost_algorithm_library.CXX11.partition_point.h5"></a>
        <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>
      </h5>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
            The iterator-based version of the routine <code class="computeroutput"><span class="identifier">partition_point</span></code>
            is also available as part of the C++11 standard.
          </li>
<li class="listitem">
            For empty ranges, the partition point is the end of the range.
          </li>
</ul></div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright &#169; 2010-2012 Marshall Clow<p>
        Distributed under the Boost Software License, Version 1.0. (See accompanying
        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>)
      </p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<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>
</div>
</body>
</html>
