std::is_partitioned() 算法

自 C++20 起

// (1)
template< class InputIt, class UnaryPredicate >
constexpr bool is_partitioned( InputIt first, InputIt last, UnaryPredicate p );

// (2)
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
bool is_partitioned( ExecutionPolicy&& policy,
                     ForwardIt first, ForwardIt last, UnaryPredicate p );

自 C++17 起

// (1)
template< class InputIt, class UnaryPredicate >
bool is_partitioned( InputIt first, InputIt last, UnaryPredicate p );

// (2)
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
bool is_partitioned( ExecutionPolicy&& policy,
                     ForwardIt first, ForwardIt last, UnaryPredicate p );

自 C++11 起

// (1)
template< class InputIt, class UnaryPredicate >
bool is_partitioned( InputIt first, InputIt last, UnaryPredicate p );

• (1) 如果范围 [first; last) 中所有满足谓词 p 的元素都出现在所有不满足谓词的元素之前，则返回 true。

  如果 [first; last) 为空，也返回 true。

• (2) 与 (1) 相同，但根据 policy 执行。

  重载决议

  这些重载仅在 std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>  (直到 C++20) std::is_execution_policy_v<std::is_partitioned_cvref_t<ExecutionPolicy>>  (C++20 起) 为 true 时参与重载决议。

参数

first last	要检查的元素范围。
policy	要使用的执行策略。有关详细信息，请参阅执行策略。
p	一元谓词，如果元素值应该被替换，则返回 true。 对于类型为 (可能是 const) VT 的每个参数 v，表达式 p(v) 必须可转换为 bool，其中 VT 是 InputIt 的值类型，无论值类别如何，并且不得修改 v。因此，不允许使用参数类型 VT& ，也不允许使用 VT，除非对于 VT，移动等同于复制。 (C++11 起)。

类型要求

InputIt	LegacyInputIterator
ForwardIt	LegacyForwardIterator
UnaryPredicate	Predicate

ForwardIt::value_type 必须可转换为 UnaryPredicate 的参数类型。

返回值

如果范围为空或由 p 分区 - true。
否则为 false。

复杂度

最多 std::distance(first, last) 次 p 的应用。

异常

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

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

可能的实现

is_partitioned (1)

template<class InputIt, class UnaryPredicate>
bool is_partitioned(InputIt first, InputIt last, UnaryPredicate p)
{
    for (; first != last; ++first)
        if (!p(*first))
            break;
    for (; first != last; ++first)
        if (p(*first))
            return false;
    return true;
}

示例

Main.cpp

#include <algorithm>
#include <array>
#include <iostream>

int main()
{
    std::array<int, 9> v {1, 2, 3, 4, 5, 6, 7, 8, 9};

    auto is_even = [](int i) { return i % 2 == 0; };
    std::cout.setf(std::ios_base::boolalpha);
    std::cout << std::is_partitioned(v.begin(), v.end(), is_even) << ' ';

    std::partition(v.begin(), v.end(), is_even);
    std::cout << std::is_partitioned(v.begin(), v.end(), is_even) << ' ';

    std::reverse(v.begin(), v.end());
    std::cout << std::is_partitioned(v.cbegin(), v.cend(), is_even) << ' ';
    std::cout << std::is_partitioned(v.crbegin(), v.crend(), is_even) << '\n';
}

输出

false true false true