std::partition_point
定义于头文件 <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) |
检查范围是否已按升序排列 (函数模板) |
返回指向第一个不小于给定值的元素的迭代器 (函数模板) |