Boost C++ Libraries

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.

Interface

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 );

Examples

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

Iterator Requirements

is_permutation works on forward iterators or better.

Complexity

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.

Exception Safety

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.

Notes