std::ranges::partition_point

检验已划分（如同用 ranges::partition ）范围 [first, last) 或 r 并定位第一划分的结尾，即不满足 pred 的被投影元素，或若所有投影后元素均满足 pred 则为 last 。

此页面上描述的仿函数实体是 niebloid ，即：

• 调用它们中的任何一者时不可指定显式模板实参。
• 它们无一对实参依赖查找可见。
• 在通常无限定查找寻找函数调用运算符左侧的名称找到它们之一时，它禁止实参依赖查找。

实际上，它们能以函数对象，或以某些特殊编译器扩展实现。

参数

返回值

[first, last) 内第一划分的尾后位置迭代器，或若所有投影后元素均满足 pred 则为等于 last 的迭代器。

复杂度

给定 N = ranges::distance(first, last) ，应用 O(log N) 次谓词 pred 与投影 proj 。

然而，若哨位不实现 std::sized_sentinel_for<I> ，则迭代器自增次数为 O(N) 。

注解

此算法是 ranges::lower_bound 的更通用的形式，能用 ranges::partition_point 用 [&](auto const& e) { return std::invoke(pred, e, value); }); 为谓词表达它。

示例

#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>
 
int main()
{
    std::array v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 
    namespace ranges = std::ranges;
    auto is_even = [](int i){ return i % 2 == 0; };
    ranges::partition(v, is_even);
 
    auto p = ranges::partition_point(v.begin(), v.end(), is_even);
 
    std::cout << "Before partition:\n    ";
    ranges::copy(v.begin(), p, std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\nAfter partition:\n    ";
    ranges::copy(p, v.end(), std::ostream_iterator<int>(std::cout, " "));
}

Before partition:
    8 2 6 4 
After partition:
    5 3 7 1 9

参阅