std::is_permutation() 算法

自 C++20 起

// (1)
template< class ForwardIt1, class ForwardIt2 >
constexpr bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2 );

// (2)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
constexpr bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, BinaryPredicate p );

// (3)
template< class ForwardIt1, class ForwardIt2 >
constexpr bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );

// (4)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
constexpr bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                               ForwardIt2 first2, ForwardIt2 last2, BinaryPredicate p );

自 C++14 起

// (1)
template< class ForwardIt1, class ForwardIt2 >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2 );

// (2)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, BinaryPredicate p );

// (3)
template< class ForwardIt1, class ForwardIt2 >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );

// (4)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, BinaryPredicate p );

自 C++11 起

// (1)
template< class ForwardIt1, class ForwardIt2 >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2 );

// (2)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, BinaryPredicate p );

如果存在范围 [first1; last1) 中元素的排列，使得该范围等于范围 [first2; last2)，则返回 true，其中 last2 表示 first2 + (last1 - first1)（如果未给出）。

• (1, 3) 元素使用 operator== 进行比较。
• (2, 4) 元素使用给定的二元谓词 p 进行比较。

未定义行为

行为未定义

如果它不是等价关系。

参数

first1 last1	要比较的元素范围。
first1 last1	要比较的第二个范围。
p	一元谓词，如果元素值应该被替换，则返回 true。 类型应为 ForwardIt1 和 ForwardIt2 的值类型。 签名不需要包含 const&，但函数不得修改传递给它的对象。

类型要求

ForwardIt1 ForwardIt2	LegacyForwardIterator
ForwardIt1 ForwardIt2	必须具有相同的值类型。

返回值

如果范围 [first1; last1) 是范围 [first2; last2) 的排列，则返回 true。

复杂度

给定 N 为 std::distance(first1, last1)

谓词最多应用 O(N2) 次，如果序列已经相等，则恰好应用 N 次，其中 N 是。

但是，如果 ForwardIt1 和 ForwardIt2 满足 LegacyRandomAccessIterator 的要求，并且 std::distance(first1, last1) != std::distance(first2, last2)，则不应用谓词。

异常

带有模板参数 ExecutionPolicy 的重载报告错误如下

• 如果作为算法一部分调用的函数执行时抛出异常且 ExecutionPolicy 是标准策略之一，则调用std::terminate。对于任何其他 ExecutionPolicy，行为是实现定义的.
• 如果算法未能分配内存，则抛出 std::bad_alloc。

可能的实现

is_permutation (1)

template<class ForwardIt1, class ForwardIt2>
bool is_permutation(ForwardIt1 first, ForwardIt1 last,
                    ForwardIt2 d_first)
{
    // skip common prefix
    std::tie(first, d_first) = std::mismatch(first, last, d_first);
    // iterate over the rest, counting how many times each element
    // from [first, last) appears in [d_first, d_last)
    if (first != last)
    {
        ForwardIt2 d_last = std::next(d_first, std::distance(first, last));
        for (ForwardIt1 i = first; i != last; ++i)
        {
            if (i != std::find(first, i, *i))
                continue; // this *i has been checked

            auto m = std::count(d_first, d_last, *i);
            if (m == 0 || std::count(i, last, *i) != m)
                return false;
        }
    }
    return true;
}

备注

std::is_permutation 可用于测试，即检查重排算法（例如排序、洗牌、分区）的正确性。

如果 x 是原始范围，而 y 是排列范围，则 std::is_permutation(x, y) == true 意味着 y 包含“相同”的元素，可能位于不同的位置。

示例

Main.cpp

#include <algorithm>
#include <iostream>

template<typename Os, typename V>
Os& operator<<(Os& os, V const& v)
{
    os << "{ ";
    for (auto const& e : v)
        os << e << ' ';
    return os << '}';
}

int main()
{
    static constexpr auto v1 = {1, 2, 3, 4, 5};
    static constexpr auto v2 = {3, 5, 4, 1, 2};
    static constexpr auto v3 = {3, 5, 4, 1, 1};

    std::cout << v2 << " is a permutation of " << v1 << ": " << std::boolalpha
              << std::is_permutation(v1.begin(), v1.end(), v2.begin()) << '\n'
              << v3 << " is a permutation of " << v1 << ": "
              << std::is_permutation(v1.begin(), v1.end(), v3.begin()) << '\n';
}

输出

{ 3 5 4 1 2 } is a permutation of { 1 2 3 4 5 }: true
{ 3 5 4 1 1 } is a permutation of { 1 2 3 4 5 }: false