equality (1) template <class ForwardIterator1, class ForwardIterator2> bool is_permutation (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); predicate (2) template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> bool is_permutation (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, BinaryPredicate pred);
功能：
判断区间[ first1 , last1 )是否是以first2为开始的区间的一个排列，如果是，返回真。
例子：
// is_permutation example #include <iostream> // std::cout #include <algorithm> // std::is_permutation #include <array> // std::array int main () { std::array<int,5> foo = {1,2,3,4,5}; std::array<int,5> bar = {3,1,4,5,2}; if ( std::is_permutation (foo.begin(), foo.end(), bar.begin()) ) std::cout << "foo and bar contain the same elements.\n"; return 0; }运行如下：foo and bar contain the same elements.
二：源码剖析 不得不说这完全可以作为一个笔试面试算法题，源码给出的解答也相当巧妙，值得学习。
源码有点长，记得从底往上读！！！
// TEMPLATE FUNCTION next template<class _FwdIt> inline _FwdIt next(_FwdIt _First, typename iterator_traits<_FwdIt>::difference_type _Off = 1) { // increment iterator static_assert(is_base_of<forward_iterator_tag, typename iterator_traits<_FwdIt>::iterator_category>::value, "next requires forward iterator"); _STD advance(_First, _Off); return (_First); } // TEMPLATE FUNCTION _Count_pr WITH PRED template<class _InIt, class _Ty, class _Pr> inline typename iterator_traits<_InIt>::difference_type _Count_pr(_InIt _First, _InIt _Last, const _Ty& _Val, _Pr _Pred) { // count elements that match _Val, using _Pred typename iterator_traits<_InIt>::difference_type _Count = 0; for (; _First != _Last; ++_First) if (_Pred(*_First, _Val)) ++_Count; return (_Count); } // TEMPLATE FUNCTION _Find_pr WITH PRED template<class _InIt, class _Ty, class _Pr> inline _InIt _Find_pr(_InIt _First, _InIt _Last, const _Ty& _Val, _Pr _Pred) { // find first matching _Val, using _Pred for (; _First != _Last; ++_First) if (_Pred(*_First, _Val)) break; return (_First); } // TEMPLATE FUNCTION _Trim_matching_suffixes WITH PRED template<class _FwdIt1, class _FwdIt2, class _Pr> inline void _Trim_matching_suffixes(_FwdIt1&, _FwdIt2&, _Pr, forward_iterator_tag, forward_iterator_tag) { // trim matching suffixes, forward iterators (do nothing) } template<class _FwdIt1, class _FwdIt2, class _Pr> inline void _Trim_matching_suffixes(_FwdIt1& _Last1, _FwdIt2& _Last2, _Pr _Pred, bidirectional_iterator_tag, bidirectional_iterator_tag) { // trim matching suffixes, bidirectional iterators // assumptions: same lengths, non-empty, !_Pred(*_First1, *_First2) while (_Pred(*--_Last1, *--_Last2)) ; // find last inequality ++_Last1; ++_Last2; } // TEMPLATE FUNCTION _Check_match_counts WITH PRED template<class _FwdIt1, class _FwdIt2, class _Pr> inline bool _Check_match_counts(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred) { // test if [_First1, _Last1) == permuted [_First2, _Last2), using _Pred, same lengths _Trim_matching_suffixes(_Last1, _Last2, _Pred,//从尾往前查看区间是否满足pred，即查看它们的后缀，具体函数在上面 _Iter_cat(_Last1), _Iter_cat(_Last2)); typedef typename iterator_traits<_FwdIt1>::difference_type _Diff1; typedef typename iterator_traits<_FwdIt2>::difference_type _Diff2; for (_FwdIt1 _Next1 = _First1; _Next1 != _Last1; ++_Next1) if (_Next1 == _Find_pr(_First1, _Next1, *_Next1, _Pred)) { // new value, compare match counts _Diff2 _Count2 = _Count_pr(_First2, _Last2, *_Next1, _Pred); if (_Count2 == 0) return (false); // second range lacks value, fail _FwdIt1 _Skip1 = _STD next(_Next1); _Diff1 _Count1 = _Count_pr(_Skip1, _Last1, *_Next1, _Pred) + 1; if (_Count2 != _Count1) return (false); // match counts differ, fail } return (true); } // TEMPLATE FUNCTION is_permutation WITH PRED template<class _FwdIt1, class _FwdIt2, class _Pr> inline bool _Is_permutation(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _Pr _Pred) { // test if [_First1, _Last1) == permuted [_First2, ...), using _Pred for (; _First1 != _Last1; ++_First1, (void)++_First2) if (!_Pred(*_First1, *_First2)) { // found first inequality, check match counts in suffix _FwdIt2 _Last2 = _STD next(_First2,//必须要保证比较的两个区间长度，后者一定比前者长，或者相等 _STD distance(_First1, _Last1)); return (_Check_match_counts(_First1, _Last1,//实际的源码的判断在上面_Check_match_counts() _First2, _Last2, _Pred)); } return (true); } #if _ITERATOR_DEBUG_LEVEL == 0 template<class _FwdIt1, class _FwdIt2, class _Pr> inline bool is_permutation(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _Pr _Pred) { // test if [_First1, _Last1) == permuted [_First2, ...), using _Pred return (_Is_permutation(_Unchecked(_First1), _Unchecked(_Last1), _Unchecked(_First2), _Pred)); } #else /* _ITERATOR_DEBUG_LEVEL == 0 */ template<class _FwdIt1, class _FwdIt2, class _Pr> inline bool _Is_permutation2(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _Pr _Pred, true_type) { // test if [_First1, _Last1) == permuted [_First2, ...), // using _Pred, checked input return (_Is_permutation(_First1, _Last1, _First2, _Pred)); } template<class _FwdIt1, class _FwdIt2, class _Pr> inline _SCL_INSECURE_DEPRECATE bool _Is_permutation2(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _Pr _Pred, false_type) { // test if [_First1, _Last1) == permuted [_First2, ...), // using _Pred, unchecked input return (_Is_permutation(_First1, _Last1, _First2, _Pred)); } template<class _FwdIt1, class _FwdIt2, class _Pr> inline bool is_permutation(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _Pr _Pred) { // test if [_First1, _Last1) == permuted [_First2, ...), using _Pred _DEBUG_RANGE_PTR(_First1, _Last1, _First2); _DEBUG_POINTER_IF(_First1 != _Last1, _Pred); return (_Is_permutation2(_Unchecked(_First1), _Unchecked(_Last1), _First2, _Pred, _Is_checked(_First2))); } #if _ITERATOR_DEBUG_ARRAY_OVERLOADS template<class _FwdIt1, class _InTy, size_t _InSize, class _Pr> inline bool is_permutation(_FwdIt1 _First1, _FwdIt1 _Last1, _InTy (&_First2)[_InSize], _Pr _Pred) { // test if [_First1, _Last1) == permuted [_First2, ...), using _Pred return (_STD is_permutation(_First1, _Last1, _Array_iterator<_InTy, _InSize>(_First2), _Pred)); } #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */ #endif /* _ITERATOR_DEBUG_LEVEL == 0 */ // TEMPLATE FUNCTION is_permutation template<class _FwdIt1, class _FwdIt2> inline bool is_permutation(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2) { // test if [_First1, _Last1) == permuted [_First2, ...) return (_STD is_permutation(_First1, _Last1, _First2, equal_to<>())); } #if _ITERATOR_DEBUG_ARRAY_OVERLOADS template<class _FwdIt1, class _InTy, size_t _InSize> inline bool is_permutation(_FwdIt1 _First1, _FwdIt1 _Last1, _InTy (&_First2)[_InSize]) { // test if [_First1, _Last1) == permuted [_First2, ...) return (_STD is_permutation(_First1, _Last1, _First2, equal_to<>())); } #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */
源码摘抄自Visual Studio 2015安装目录algorithm文件中。
点击进入目录----> C++源码剖析目录
