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 を返す単項述語。 述語関数のシグネチャは以下と同等なものであるべきです。 bool pred(const Type &a); シグネチャが const& を持つ必要はありませんが、関数は渡されたオブジェクトを変更してはなりません。 |
| 型の要件 | ||
-ForwardIt は ForwardIterator の要件を満たさなければなりません。 | ||
-UnaryPredicate は Predicate の要件を満たさなければなりません。 | ||
[編集]戻り値
[first, last) 内の1つめの区画の終端を指すイテレータ、またはすべての要素が p を満たす場合は last。
[編集]計算量
N =std::distance(first, last) とすると、述語 p を O(log N) 回適用します。
ただし、 RandomAccessIterator でない場合は、イテレータのインクリメント回数は O(N) になります。
[編集]例
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) | 指定範囲が昇順にソートされているか調べます (関数テンプレート) |
| 指定された値より小さくない最初の要素を指すイテレータを返します (関数テンプレート) |
