...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
The header file 'is_permutation.hpp' contains six variants of a single algorithm,
is_permutation
. The algorithm
tests to see if one sequence is a permutation of a second one; in other words,
it contains all the same members, possibly in a different order.
The routine is_permutation
takes two sequences and an (optional) predicate. It returns true if the two
sequences contain the same members. If it is passed a predicate, it uses
the predicate to compare the elements of the sequence to see if they are
the same.
is_permutation
come in three
forms. The first one takes two iterators to define the first range, and the
starting iterator of the second range. The second form takes a two iterators
to define the first range and two more to define the second range. The third
form takes a single range parameter, and uses Boost.Range to traverse it.
The function is_permutation
returns true if the two input sequences contain the same elements. There
are six versions; two take three iterators, two take four iterators, and
the other two take two ranges.
In general, you should prefer the four iterator versions over the three iterator
ones. The three iterator version has to "create" the fourth iterator
internally by calling std::advance(first2, std::distance(first1,last1))
,
and if the second sequence is shorter than the first, that's undefined behavior.
template< class ForwardIterator1, class ForwardIterator2 > bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2 ); template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate > bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, BinaryPredicate p ); template< class ForwardIterator1, class ForwardIterator2 > bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2 ); template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate > bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate p ); template <typename Range, typename ForwardIterator> bool is_permutation ( const Range &r, ForwardIterator first2 ); template <typename Range, typename ForwardIterator, typename BinaryPredicate> bool is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred );
Given the container c1
containing
{ 0, 1,
2, 3, 14, 15 }
,
and c2
containing { 15,
14, 3, 1, 2 }
,
then
is_permutation ( c1.begin(), c1.end (), c2.begin(), c2.end ()) --> false is_permutation ( c1.begin() + 1, c1.end (), c2.begin(), c2.end ()) --> true is_permutation ( c1.end (), c1.end (), c2.end(), c2.end ()) --> true // all empty ranges are permutations of each other
is_permutation
works on forward
iterators or better.
All of the variants of is_permutation
run in O(N^2) (quadratic) time; that is, they compare
against each element in the list (potentially) N times. If passed random-access
iterators, is_permutation
can return quickly if the sequences are different sizes.
All of the variants of is_permutation
take their parameters by value, and do not depend upon any global state.
Therefore, all the routines in this file provide the strong exception guarantee.
is_permutation
are also available as part of the C++11 standard.
is_permutation
are part of the proposed C++14 standard. When C++14 standard libraries
become available, the implementation should be changed to use the implementation
from the standard library (if available).
is_permutation
returns
true when passed a pair of empty ranges, no matter what predicate is
passed to test with.