1[/ File is_permutation.qbk] 2 3[section:is_permutation is_permutation ] 4 5[/license 6Copyright (c) 2010-2012 Marshall Clow 7 8Distributed under the Boost Software License, Version 1.0. 9(See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 10] 11 12The 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. 13 14The 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. 15 16`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. 17 18 19[heading Interface] 20 21The 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. 22 23In 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. 24 25`` 26template< class ForwardIterator1, class ForwardIterator2 > 27bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2 ); 28 29template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate > 30bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, 31 ForwardIterator2 first2, BinaryPredicate p ); 32 33 34template< class ForwardIterator1, class ForwardIterator2 > 35bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2 ); 36 37template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate > 38bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, 39 ForwardIterator2 first2, ForwardIterator2 last2, 40 BinaryPredicate p ); 41 42template <typename Range, typename ForwardIterator> 43bool is_permutation ( const Range &r, ForwardIterator first2 ); 44 45template <typename Range, typename ForwardIterator, typename BinaryPredicate> 46bool is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred ); 47 48`` 49 50[heading Examples] 51 52Given the container `c1` containing `{ 0, 1, 2, 3, 14, 15 }`, and `c2` containing `{ 15, 14, 3, 1, 2 }`, then 53`` 54is_permutation ( c1.begin(), c1.end (), c2.begin(), c2.end ()) --> false 55is_permutation ( c1.begin() + 1, c1.end (), c2.begin(), c2.end ()) --> true 56 57is_permutation ( c1.end (), c1.end (), c2.end(), c2.end ()) --> true // all empty ranges are permutations of each other 58`` 59 60[heading Iterator Requirements] 61 62`is_permutation` works on forward iterators or better. 63 64[heading Complexity] 65 66All 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. 67 68[heading Exception Safety] 69 70All 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. 71 72[heading Notes] 73 74* The three iterator versions of the routine `is_permutation` are also available as part of the C++11 standard. 75 76* 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). 77 78* `is_permutation` returns true when passed a pair of empty ranges, no matter what predicate is passed to test with. 79 80[endsect] 81 82[/ File is_permutation.qbk 83Copyright 2011 Marshall Clow 84Distributed under the Boost Software License, Version 1.0. 85(See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt). 86] 87 88