Файл заголовка «is_permutation.hpp» содержит шесть вариантов одного алгоритма<is_permutation>. Алгоритм проверяет, является ли одна последовательность перестановкой второй; другими словами, он содержит все те же элементы, возможно, в другом порядке.

Распорядок<is_permutation>принимает две последовательности и (необязательно) предикат. Это верно, если две последовательности содержат одни и те же элементы. Если он проходит предикат, он использует предикат для сравнения элементов последовательности, чтобы увидеть, являются ли они одинаковыми.

<is_permutation>В трех формах. Первый использует два итератора для определения первого диапазона и стартовый итератор второго диапазона. Вторая форма требует двух итераторов для определения первого диапазона и еще двух для определения второго диапазона. Третья форма принимает один параметр диапазона и использует Boost. Диапазон, чтобы пройти его.

Interface

Функция<is_permutation>возвращается истинной, если две входные последовательности содержат одни и те же элементы. Существует шесть версий; две занимают три итератора, две занимают четыре итератора, а две другие занимают два диапазона.

В общем, вы должны предпочесть четыре версии итератора трем. Версия с тремя итераторами должна «создать» четвертый итератор внутренне, позвонив<std::advance(first2,std::distance(first1,last1))>, и если вторая последовательность короче первой, это неопределенное поведение.

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

<c1>, содержащее<{0,1, 2,3,14,15}>, и<c2>содержащее<{15, 14,3,1,2}>,

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>Работает на передних итераторах или лучше.

Complexity

Все варианты<is_permutation>работают вO(N^2)(квадратическое) время; то есть они сравниваются с каждым элементом в списке (потенциально) N раз. При прохождении итераторов случайного доступа<is_permutation>может быстро вернуться, если последовательности разного размера.

Exception Safety

Все варианты<is_permutation>берут свои параметры по стоимости и не зависят ни от какого глобального государства. Таким образом, все процедуры в этом файле обеспечивают сильную гарантию исключения.

Notes