- template<typename _ForwardIterator1, typename _ForwardIterator2,
- typename _BinaryPredicate>
- _GLIBCXX20_CONSTEXPR
- bool
- __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
- _ForwardIterator2 __first2, _BinaryPredicate __pred)
- {
- // Efficiently compare identical prefixes: O(N) if sequences
- // have the same elements in the same order.
- for (; __first1 != __last1; ++__first1, (void)++__first2)
- if (!__pred(__first1, __first2))
- break;
-
- if (__first1 == __last1)
- return true;
-
- // Establish __last2 assuming equal ranges by iterating over the
- // rest of the list.
- _ForwardIterator2 __last2 = __first2;
- std::advance(__last2, std::distance(__first1, __last1));
- for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
- {
- if (__scan != std::__find_if(__first1, __scan,
- __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
- continue; // We've seen this one before.
-
- auto __matches
- = std::__count_if(__first2, __last2,
- __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
- if (0 == __matches ||
- std::__count_if(__scan, __last1,
- __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
- != __matches)
- return false;
- }
- return true;
- }
-
- /**
- * @brief Checks whether a permutation of the second sequence is equal
- * to the first sequence.
- * @ingroup non_mutating_algorithms
- * @param __first1 Start of first range.
- * @param __last1 End of first range.
- * @param __first2 Start of second range.
- * @return true if there exists a permutation of the elements in the range
- * [__first2, __first2 + (__last1 - __first1)), beginning with
- * ForwardIterator2 begin, such that equal(__first1, __last1, begin)
- * returns true; otherwise, returns false.
- */
- template<typename _ForwardIterator1, typename _ForwardIterator2>
- _GLIBCXX20_CONSTEXPR
- inline bool
- is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
- _ForwardIterator2 __first2)
- {
- // concept requirements
- __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
- __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
- __glibcxx_function_requires(_EqualOpConcept<
- typename iterator_traits<_ForwardIterator1>::value_type,
- typename iterator_traits<_ForwardIterator2>::value_type>)
- __glibcxx_requires_valid_range(__first1, __last1);
-
- return std::__is_permutation(__first1, __last1, __first2,
- __gnu_cxx::__ops::__iter_equal_to_iter());
- }
-