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

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   4 <title>is_permutation</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_partitioned.html" title="is_partitioned">
  10 <link rel="next" href="partition_point.html" title="partition_point">
  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_partitioned.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="partition_point.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.is_permutation"></a><a class="link" href="is_permutation.html" title="is_permutation">is_permutation
  28       </a>
  29 </h3></div></div></div>
  30 <p>
  31         The header file 'is_permutation.hpp' contains six variants of a single algorithm,
  32         <code class="computeroutput"><span class="identifier">is_permutation</span></code>. The algorithm
  33         tests to see if one sequence is a permutation of a second one; in other words,
  34         it contains all the same members, possibly in a different order.
  35       </p>
  36 <p>
  37         The routine <code class="computeroutput"><span class="identifier">is_permutation</span></code>
  38         takes two sequences and an (optional) predicate. It returns true if the two
  39         sequences contain the same members. If it is passed a predicate, it uses
  40         the predicate to compare the elements of the sequence to see if they are
  41         the same.
  42       </p>
  43 <p>
  44         <code class="computeroutput"><span class="identifier">is_permutation</span></code> come in three
  45         forms. The first one takes two iterators to define the first range, and the
  46         starting iterator of the second range. The second form takes a two iterators
  47         to define the first range and two more to define the second range. The third
  48         form takes a single range parameter, and uses Boost.Range to traverse it.
  49       </p>
  50 <h5>
  51 <a name="the_boost_algorithm_library.CXX11.is_permutation.h0"></a>
  52         <span class="phrase"><a name="the_boost_algorithm_library.CXX11.is_permutation.interface"></a></span><a class="link" href="is_permutation.html#the_boost_algorithm_library.CXX11.is_permutation.interface">Interface</a>
  53       </h5>
  54 <p>
  55         The function <code class="computeroutput"><span class="identifier">is_permutation</span></code>
  56         returns true if the two input sequences contain the same elements. There
  57         are six versions; two take three iterators, two take four iterators, and
  58         the other two take two ranges.
  59       </p>
  60 <p>
  61         In general, you should prefer the four iterator versions over the three iterator
  62         ones. The three iterator version has to "create" the fourth iterator
  63         internally by calling <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">advance</span><span class="special">(</span><span class="identifier">first2</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">distance</span><span class="special">(</span><span class="identifier">first1</span><span class="special">,</span><span class="identifier">last1</span><span class="special">))</span></code>,
  64         and if the second sequence is shorter than the first, that's undefined behavior.
  65       </p>
  66 <p>
  67 </p>
  68 <pre class="programlisting"><span class="keyword">template</span><span class="special">&lt;</span> <span class="keyword">class</span> <span class="identifier">ForwardIterator1</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">ForwardIterator2</span> <span class="special">&gt;</span>
  69 <span class="keyword">bool</span> <span class="identifier">is_permutation</span> <span class="special">(</span> <span class="identifier">ForwardIterator1</span> <span class="identifier">first1</span><span class="special">,</span> <span class="identifier">ForwardIterator1</span> <span class="identifier">last1</span><span class="special">,</span> <span class="identifier">ForwardIterator2</span> <span class="identifier">first2</span> <span class="special">);</span>
  70
  71 <span class="keyword">template</span><span class="special">&lt;</span> <span class="keyword">class</span> <span class="identifier">ForwardIterator1</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">ForwardIterator2</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">BinaryPredicate</span> <span class="special">&gt;</span>
  72 <span class="keyword">bool</span> <span class="identifier">is_permutation</span> <span class="special">(</span> <span class="identifier">ForwardIterator1</span> <span class="identifier">first1</span><span class="special">,</span> <span class="identifier">ForwardIterator1</span> <span class="identifier">last1</span><span class="special">,</span>
  73                       <span class="identifier">ForwardIterator2</span> <span class="identifier">first2</span><span class="special">,</span> <span class="identifier">BinaryPredicate</span> <span class="identifier">p</span> <span class="special">);</span>
  74
  75
  76 <span class="keyword">template</span><span class="special">&lt;</span> <span class="keyword">class</span> <span class="identifier">ForwardIterator1</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">ForwardIterator2</span> <span class="special">&gt;</span>
  77 <span class="keyword">bool</span> <span class="identifier">is_permutation</span> <span class="special">(</span> <span class="identifier">ForwardIterator1</span> <span class="identifier">first1</span><span class="special">,</span> <span class="identifier">ForwardIterator1</span> <span class="identifier">last1</span><span class="special">,</span> <span class="identifier">ForwardIterator2</span> <span class="identifier">first2</span><span class="special">,</span> <span class="identifier">ForwardIterator2</span> <span class="identifier">last2</span> <span class="special">);</span>
  78
  79 <span class="keyword">template</span><span class="special">&lt;</span> <span class="keyword">class</span> <span class="identifier">ForwardIterator1</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">ForwardIterator2</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">BinaryPredicate</span> <span class="special">&gt;</span>
  80 <span class="keyword">bool</span> <span class="identifier">is_permutation</span> <span class="special">(</span> <span class="identifier">ForwardIterator1</span> <span class="identifier">first1</span><span class="special">,</span> <span class="identifier">ForwardIterator1</span> <span class="identifier">last1</span><span class="special">,</span>
  81                       <span class="identifier">ForwardIterator2</span> <span class="identifier">first2</span><span class="special">,</span> <span class="identifier">ForwardIterator2</span> <span class="identifier">last2</span><span class="special">,</span>
  82                       <span class="identifier">BinaryPredicate</span> <span class="identifier">p</span> <span class="special">);</span>
  83
  84 <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">ForwardIterator</span><span class="special">&gt;</span>
  85 <span class="keyword">bool</span> <span class="identifier">is_permutation</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">ForwardIterator</span> <span class="identifier">first2</span> <span class="special">);</span>
  86
  87 <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">ForwardIterator</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">BinaryPredicate</span><span class="special">&gt;</span>
  88 <span class="keyword">bool</span> <span class="identifier">is_permutation</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">ForwardIterator</span> <span class="identifier">first2</span><span class="special">,</span> <span class="identifier">BinaryPredicate</span> <span class="identifier">pred</span> <span class="special">);</span>
  89 </pre>
  90 <p>
  91       </p>
  92 <h5>
  93 <a name="the_boost_algorithm_library.CXX11.is_permutation.h1"></a>
  94         <span class="phrase"><a name="the_boost_algorithm_library.CXX11.is_permutation.examples"></a></span><a class="link" href="is_permutation.html#the_boost_algorithm_library.CXX11.is_permutation.examples">Examples</a>
  95       </h5>
  96 <p>
  97         Given the container <code class="computeroutput"><span class="identifier">c1</span></code> containing
  98         <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>
  99         <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>,
 100         and <code class="computeroutput"><span class="identifier">c2</span></code> containing <code class="computeroutput"><span class="special">{</span> <span class="number">15</span><span class="special">,</span>
 101         <span class="number">14</span><span class="special">,</span> <span class="number">3</span><span class="special">,</span> <span class="number">1</span><span class="special">,</span> <span class="number">2</span> <span class="special">}</span></code>,
 102         then
 103 </p>
 104 <pre class="programlisting"><span class="identifier">is_permutation</span> <span class="special">(</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span>     <span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span> <span class="special">(),</span> <span class="identifier">c2</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">c2</span><span class="special">.</span><span class="identifier">end</span> <span class="special">())</span> <span class="special">--&gt;</span> <span class="keyword">false</span>
 105 <span class="identifier">is_permutation</span> <span class="special">(</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()</span> <span class="special">+</span> <span class="number">1</span><span class="special">,</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span> <span class="special">(),</span> <span class="identifier">c2</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">c2</span><span class="special">.</span><span class="identifier">end</span> <span class="special">())</span> <span class="special">--&gt;</span> <span class="keyword">true</span>
 106
 107 <span class="identifier">is_permutation</span> <span class="special">(</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span> <span class="special">(),</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span> <span class="special">(),</span> <span class="identifier">c2</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="identifier">c2</span><span class="special">.</span><span class="identifier">end</span> <span class="special">())</span> <span class="special">--&gt;</span> <span class="keyword">true</span>  <span class="comment">// all empty ranges are permutations of each other</span>
 108 </pre>
 109 <p>
 110       </p>
 111 <h5>
 112 <a name="the_boost_algorithm_library.CXX11.is_permutation.h2"></a>
 113         <span class="phrase"><a name="the_boost_algorithm_library.CXX11.is_permutation.iterator_requirements"></a></span><a class="link" href="is_permutation.html#the_boost_algorithm_library.CXX11.is_permutation.iterator_requirements">Iterator
 114         Requirements</a>
 115       </h5>
 116 <p>
 117         <code class="computeroutput"><span class="identifier">is_permutation</span></code> works on forward
 118         iterators or better.
 119       </p>
 120 <h5>
 121 <a name="the_boost_algorithm_library.CXX11.is_permutation.h3"></a>
 122         <span class="phrase"><a name="the_boost_algorithm_library.CXX11.is_permutation.complexity"></a></span><a class="link" href="is_permutation.html#the_boost_algorithm_library.CXX11.is_permutation.complexity">Complexity</a>
 123       </h5>
 124 <p>
 125         All of the variants of <code class="computeroutput"><span class="identifier">is_permutation</span></code>
 126         run in <span class="emphasis"><em>O(N^2)</em></span> (quadratic) time; that is, they compare
 127         against each element in the list (potentially) N times. If passed random-access
 128         iterators, <code class="computeroutput"><span class="identifier">is_permutation</span></code>
 129         can return quickly if the sequences are different sizes.
 130       </p>
 131 <h5>
 132 <a name="the_boost_algorithm_library.CXX11.is_permutation.h4"></a>
 133         <span class="phrase"><a name="the_boost_algorithm_library.CXX11.is_permutation.exception_safety"></a></span><a class="link" href="is_permutation.html#the_boost_algorithm_library.CXX11.is_permutation.exception_safety">Exception
 134         Safety</a>
 135       </h5>
 136 <p>
 137         All of the variants of <code class="computeroutput"><span class="identifier">is_permutation</span></code>
 138         take their parameters by value, and do not depend upon any global state.
 139         Therefore, all the routines in this file provide the strong exception guarantee.
 140       </p>
 141 <h5>
 142 <a name="the_boost_algorithm_library.CXX11.is_permutation.h5"></a>
 143         <span class="phrase"><a name="the_boost_algorithm_library.CXX11.is_permutation.notes"></a></span><a class="link" href="is_permutation.html#the_boost_algorithm_library.CXX11.is_permutation.notes">Notes</a>
 144       </h5>
 145 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
 146 <li class="listitem">
 147             The three iterator versions of the routine <code class="computeroutput"><span class="identifier">is_permutation</span></code>
 148             are also available as part of the C++11 standard.
 149           </li>
 150 <li class="listitem">
 151             The four iterator versions of the routine <code class="computeroutput"><span class="identifier">is_permutation</span></code>
 152             are part of the proposed C++14 standard. When C++14 standard libraries
 153             become available, the implementation should be changed to use the implementation
 154             from the standard library (if available).
 155           </li>
 156 <li class="listitem">
 157             <code class="computeroutput"><span class="identifier">is_permutation</span></code> returns
 158             true when passed a pair of empty ranges, no matter what predicate is
 159             passed to test with.
 160           </li>
 161 </ul></div>
 162 </div>
 163 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 164 <td align="left"></td>
 165 <td align="right"><div class="copyright-footer">Copyright &#169; 2010-2012 Marshall Clow<p>
 166         Distributed under the Boost Software License, Version 1.0. (See accompanying
 167         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>)
 168       </p>
 169 </div></td>
 170 </tr></table>
 171 <hr>
 172 <div class="spirit-nav">
 173 <a accesskey="p" href="is_partitioned.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="partition_point.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
 174 </div>
 175 </body>
 176 </html>