GeezerVison is showing cpprefjp.github.io — std::partition - cpprefjp C++日本語リファレンス
最終更新日時:
2026年08月26日 16時18分05秒 (JST)
Akira Takahashi
が更新
function template
<algorithm>
std:: partition
namespace std {
template < class BidirectionalIterator , class Predicate >
BidirectionalIterator
partition ( BidirectionalIterator first ,
BidirectionalIterator last ,
Predicate pred ); // (1) C++98
template < class ForwardIterator , class Predicate >
ForwardIterator
partition ( ForwardIterator first ,
ForwardIterator last ,
Predicate pred ); // (1) C++11
template < class ForwardIterator , class Predicate >
constexpr ForwardIterator
partition ( ForwardIterator first ,
ForwardIterator last ,
Predicate pred ); // (1) C++20
template < class ExecutionPolicy , class ForwardIterator , class Predicate >
ForwardIterator
partition ( ExecutionPolicy && exec ,
ForwardIterator first ,
ForwardIterator last ,
Predicate pred ); // (2) C++17
}
概要
イテレータ範囲[first, last)を条件によって区分化 する。
要件
C++98 : BidirectionalIterator は ValueSwappable の要件を満たしている必要がある。
C++11 : ForwardIterator は ValueSwappable の要件を満たしている必要がある。
効果
[first,last) 内にある pred を満たす全ての要素を、pred を満たさない全ての要素より前に移動させる。
戻り値
[first,i) 内にあるイテレータ j について pred(*j) != false を満たし、[i,last) 内にあるイテレータ k について pred(*k) == false を満たすような、イテレータ i を返す。つまり、区分化 された境界を指すイテレータを返す。
計算量
N = last - firstとして
(1) : ForwardIterator が BidirectionalIterator の要求を満たしている場合、最大で N / 2 回 swap され、そうでない場合、最大で N 回 swap される。それに加えて、正確に N 回だけ述語が適用される
(2) : O(NlogN) 回の swap に加え、述語が O(N) 回適用される
例
#include <iostream>
#include <vector>
#include <algorithm>
int main ()
{
std::vector < int > v = { 1 , 2 , 3 , 4 , 5 };
// 偶数グループと奇数グループに分ける
auto pos = std::partition ( v.begin() , v.end() , []( int x ) { return x % 2 == 0 ; });
// 条件x % 2 == 0を満たす要素
std::for_each ( v.begin() , pos , []( int x ) {
std::cout << x << std::endl ;
});
// それ以外の要素
std::cout << "----" << std::endl ;
std::for_each ( pos , v.end() , []( int x ) {
std::cout << x << std::endl ;
});
}
出力
4
2
----
3
1
5
実装例
template < class ForwardIterator , class Predicate >
ForwardIterator partition ( ForwardIterator first , ForwardIterator last , Predicate pred )
{
first = std::find_if_not ( first , last , pred );
auto it = std::find_if ( first , last , pred );
while ( it != last ) {
std::iter_swap ( first , it );
first = std::find_if_not ( first , last , pred );
it = std::find_if ( it , last , pred );
}
return first ;
}
関連項目
参照