C++11

// <algorithm> 
// 等价比较(1)    
template <class ForwardIterator1,
    class ForwardIterator2>
    bool is_permutation (
        ForwardIterator1 first1,
        ForwardIterator1 last1,
        ForwardIterator2 first2);
// 自定义谓词比较(2)    
template <class ForwardIterator1,
    class ForwardIterator2,
    class BinaryPredicate>
    bool is_permutation (
        ForwardIterator1 first1,
        ForwardIterator1 last1,
        ForwardIterator2 first2,
        BinaryPredicate 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, ++_First2)
            if (!_Pred(*_First1, *_First2))
                break;    // find first inequality
        if (_First1 != _Last1)
            {    // check match counts in suffix
            _FwdIt2 _Last2 = _First2;
            advance(_Last2, distance(_First1, _Last1));
            for (_FwdIt1 _Next1 = _First1; _Next1 != _Last1; ++_Next1)
                if (_Next1 == _Find_pr(_First1, _Next1, *_Next1, _Pred))
                    {    // new value, compare match counts
                    typename iterator_traits<_FwdIt2>::difference_type _Count =
                        _Count_pr(_First2, _Last2, *_Next1, _Pred);
                    if (_Count == 0
                        || _Count != _Count_pr(_Next1, _Last1, *_Next1, _Pred))
                        return (false);    // match counts differ, fail
                    }
            }
        return (true);
    }
  • first1last1

    分别指向一个序列中初始及末尾位置的输入迭代器(Input iterators)。这个范围即 [first1,last1) ,包括 first1 到 last1 间的所有元素,包括 first1 指向的元素,但不包括 last1 指向的元素。

    first2

    指向第二个序列中初始位置的输入迭代器(Input iterators)。当前函数最多访问与范围 [first1,last1)  中相同元素个数的元素。

    pred

    二元谓词(Binary)函数,以两个元素为参数,然后返回一个可转换成 bool 类型的值。

    其返回值表明指定两个元素是否满足当前函数所检测的匹配条件。

    该函数不能修改其参数。

    可以是函数指针(Function pointer)类型或函数对象(Function object)类型。

    返回

    如果在范围 [first1,last1) 中的所有元素与从 first2 开始的范围中的所有元素按任意顺序存在等价,则返回 ture

    否则返回 false

  • 例 1

    #include <iostream>
    #include <algorithm>
    #include <vector>
    
    #define CLASSFOO_VECTOR(type, name, ...) \
    static const type name##_a[] = __VA_ARGS__; \
    std::vector<type> name(name##_a, name##_a + sizeof(name##_a) / sizeof(*name##_a))
    
    namespace ClassFoo{
        bool IfEqual(int m, int n) {
            return (m == n);
        }
        void IsPermutation_1() {
            CLASSFOO_VECTOR(int, BigVector, { 8, 23, 5, 6, 7, 29, 0, 5, 6, 7, 1, 1 });
            CLASSFOO_VECTOR(int, SmallVector, { 23, 5, 8, 6, 7, 29, 0, 7, 6, 5, 1, 1 });
            // 等价比较
            bool b = std::is_permutation(
                std::begin(BigVector),
                std::end(BigVector),
                std::begin(SmallVector));
            if (b) {
                std::cout << "相等" << '\n';
            }
            // 自定谓词比较
            b = std::is_permutation(
                std::begin(BigVector),
                std::end(BigVector),
                std::begin(SmallVector),
                IfEqual);
            if (b) {
                std::cout << "相等" << '\n';
            }
        }
    }
    int main()
    {
        ClassFoo::IsPermutation_1();
        return 0;
    }

    相等
    相等

    例 2

    C++11

    #include <iostream>
    #include <algorithm>
    #include <vector>
    
    namespace ClassFoo{
        void IsPermutation_2() {
            std::vector<int> BigVector = { 8, 23, 5, 6, 7, 29, 0, 5, 6, 7, 1, 1 };
            std::vector<int> SmallVector = { 23, 5, 8, 6, 7, 29, 0, 7, 6, 5, 1, 1 };
            // 等价比较
            bool b = std::is_permutation(
                std::begin(BigVector),
                std::end(BigVector),
                std::begin(SmallVector));
            if (b) {
                std::cout << "相等" << '\n';
            }
            // 自定谓词比较
            b = std::is_permutation(
                std::begin(BigVector),
                std::end(BigVector),
                std::begin(SmallVector),
                [](const int &m, const int &n) { return m == n; });
            if (b) {
                std::cout << "相等" << '\n';
            }
        }
    }
    int main()
    {
        ClassFoo::IsPermutation_2();
        return 0;
    }

    相等
    相等

  • 复杂度

    O(n^2)n 为 last first

    数据争用相关

    访问两个序列中的部份(或所有)元素,每个元素可能被访问多次。

    异常安全性相关

    如果元素比较(or pred) 或操作某个迭代器抛异常,该函数才会抛异常。

    注意 无效参数将导致未定义行为(Undefined behavior)