123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687 |
- [/ File is_permutation.qbk]
- [section:is_permutation is_permutation ]
- [/license
- Copyright (c) 2010-2012 Marshall Clow
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- ]
- 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.
- [heading 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 );
- ``
- [heading 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
- ``
- [heading Iterator Requirements]
- `is_permutation` works on forward iterators or better.
- [heading 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.
- [heading 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.
- [heading Notes]
- * The three iterator versions of the routine `is_permutation` are also available as part of the C++11 standard.
- * The four iterator versions of the routine `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.
- [endsect]
- [/ File is_permutation.qbk
- Copyright 2011 Marshall Clow
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt).
- ]
|