partition
partition (술어 기준 분할)
범위를 재배열해 술어가 참인 원소들이 앞에, 거짓인 원소들이 뒤에 오도록 분할하는 알고리즘이에요. <algorithm> 헤더에 있어요.
출처: cppreference
본문
partition은 [first, last)의 요소를 술어 p 기준으로 재배열해, p가 참인 원소들이 p가 거짓인 원소들보다 앞에 오도록 해요.
template< class ForwardIt, class UnaryPred >
ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPred p ); // (1)
- 반환 값: 첫 번째로
p가 거짓인 원소를 가리키는 반복자. 모두 참이면last. - 복잡도:
last - first에 선형.
std::vector<int> v{1, 2, 3, 4, 5, 6};
auto it = std::partition(v.begin(), v.end(),
[](int x){ return x % 2 == 0; });
// 짝수들이 앞, 홀수들이 뒤 (상대 순서 불보장)
partition은 각 그룹 내부의 상대 순서를 보장하지 않아요. 순서를 유지하면서 분할하려면 안정(stable) 버전 std::stable_partition을 써요.