std::partition_point
来自cppreference.com
| 定义于头文件 <algorithm>
|
||
| template< class ForwardIt, class UnaryPredicate > ForwardIt partition_point( ForwardIt first, ForwardIt last, UnaryPredicate p ); |
(C++11 起) (C++20 前) |
|
| template< class ForwardIt, class UnaryPredicate > constexpr ForwardIt partition_point( ForwardIt first, ForwardIt last, UnaryPredicate p ); |
(C++20 起) | |
检验（如同用 std::partition 的）划分范围 [first, last) ，并定位第一划分的结尾，即首个不满足 p 的元素，或若所有元素满足 p 则为 last 。
参数
| first, last | - | 要检验的元素被划分范围 |
| p | - | 对于在范围起始找到的元素则返回 true 的一元谓词。 对每个（可为 const 的） |
| 类型要求 | ||
-ForwardIt 必须满足遗留向前迭代器 (LegacyForwardIterator) 的要求。
| ||
-UnaryPredicate 必须满足谓词 (Predicate) 的要求。
| ||
返回值
[first, last) 内第一划分结尾后的迭代器，或若所有元素满足 p 则为 last 。
复杂度
给定 N = std::distance(first, last) ，应用 O(log N) 次谓词 p 。
然而，对于非遗留随机访问迭代器 (LegacyRandomAccessIterator) ，迭代器自增次数为 O(N) 。
注解
此算法是 std::lower_bound 的更通用化的形式，能用 std::partition_point 以 [&](auto const& e) { return e < value; } 为谓词表达它。
示例
运行此代码
#include <algorithm> #include <array> #include <iostream> #include <iterator> 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::partition(v.begin(), v.end(), is_even); auto p = std::partition_point(v.begin(), v.end(), is_even); std::cout << "Before partition:\n "; std::copy(v.begin(), p, std::ostream_iterator<int>(std::cout, " ")); std::cout << "\nAfter partition:\n "; std::copy(p, v.end(), std::ostream_iterator<int>(std::cout, " ")); }
输出：
Before partition:
8 2 6 4
After partition:
5 3 7 1 9参阅
| (C++11) |
检查范围是否已按升序排列 (函数模板) |
| 返回指向第一个不小于给定值的元素的迭代器 (函数模板) |
