std::partition_point() 算法

自 C++20 起

template< class ForwardIt, class UnaryPredicate >
constexpr ForwardIt partition_point( ForwardIt first, ForwardIt last, UnaryPredicate p );

自 C++11 起

// (1)
template< class ForwardIt, class UnaryPredicate >
ForwardIt partition_point( ForwardIt first, ForwardIt last, UnaryPredicate p );

检查已分区（如同通过 std::partition）的范围 [first; last)，并定位第一个分区的末尾，即第一个不满足 p 的元素，如果所有元素都满足 p 则为 last。

参数

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

类型要求

ForwardIt	LegacyForwardIterator
一元谓词	谓词

返回值

在 [first; last) 中第一个分区末尾的迭代器，如果所有元素都满足 p 则为 last。

复杂度

给定 N 为 std::distance(first, last)

执行谓词 p 的 O(log(N)) 次应用。

但是，对于非 LegacyRandomAccessIterators，迭代器增量的数量为 O(N)。

异常

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

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

可能的实现

partition_point (1)

template<class ForwardIt, class UnaryPredicate>
constexpr //< since C++20
ForwardIt partition_point(ForwardIt first, ForwardIt last, UnaryPredicate p)
{
    for (auto length = std::distance(first, last); 0 < length; )
    {
        auto half = length / 2;
        auto middle = std::next(first, half);
        if (p(*middle))
        {
            first = std::next(middle);
            length -= (half + 1);
        }
        else
            length = half;
    }

    return first;
}

备注

此算法是 std::lower_bound 的更通用形式，后者可以使用谓词 [&](auto const& e) { return e < value; }); 以 std::partition_point 的形式表示。

示例

Main.cpp

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

auto print_seq = [](auto rem, auto first, auto last)
{
    for (std::cout << rem; first != last; std::cout << *first++ << ' ') {}
    std::cout << '\n';
};

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

    auto is_even = [](int i) { return i % 2 == 0; };

    std::partition(v.begin(), v.end(), is_even);
    print_seq("After partitioning, v: ", v.cbegin(), v.cend());

    const auto pp = std::partition_point(v.cbegin(), v.cend(), is_even);
    const auto i = std::distance(v.cbegin(), pp);
    std::cout << "Partition point is at " << i << "; v[" << i << "] = " << *pp << '\n';

    print_seq("First partition (all even elements): ", v.cbegin(), pp);
    print_seq("Second partition (all odd elements): ", pp, v.cend());
}

输出

After partitioning, v: 8 2 6 4 5 3 7 1 9
Partition point is at 4; v[4] = 5
First partition (all even elements): 8 2 6 4
Second partition (all odd elements): 5 3 7 1 9