std::partition_point
提供: cppreference.com
| ヘッダ <algorithm> で定義
|
||
| (1) | ||
| 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) を調べ、その1つめの区画の終端、つまり、 p を満たさない最初の要素、またはすべての要素が p を満たす場合は last、 を探します。
目次 |
[編集] 引数
| first, last | - | 調べる分割された要素の範囲 |
| p | - | 範囲の先頭に見つかる要素に対して true を返す単項述語。 式 p(v) は |
| 型の要件 | ||
-ForwardIt は LegacyForwardIterator の要件を満たさなければなりません。
| ||
-UnaryPredicate は Predicate の要件を満たさなければなりません。
| ||
[編集] 戻り値
[first, last) 内の1つめの区画の終端を指すイテレータ、またはすべての要素が p を満たす場合は last。
[編集] 計算量
N = std::distance(first, last) とすると、述語 p を O(log N) 回適用します。
ただし、 LegacyRandomAccessIterator でない場合は、イテレータのインクリメント回数は O(N) になります。
[編集] ノート
このアルゴリズムは std::lower_bound のより一般的な形式です。 std::lower_bound は述語 [&](auto const& e) { return e < value; }); を用いた std::partition_point で表すことができます。
[編集] 例
Run this code
#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) |
指定範囲が昇順にソートされているか調べます (関数テンプレート) |
| 指定された値より小さくない最初の要素を指すイテレータを返します (関数テンプレート) |
