namespace std {
template <class BidirectionalIterator, class Predicate>
BidirectionalIterator
partition(BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred); // (1) C++03
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++03 :
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;
}