stable_partition
stable_partition (안정 분할)
범위를 술어 기준으로 참/거짓 그룹으로 분할하되, 그룹 내 상대 순서를 유지하는 안정 분할이에요. <algorithm> 헤더에 있어요.
출처: cppreference
본문
stable_partition은 범위를 술어 p 기준으로 분할하면서, 각 그룹 내부의 원래 순서를 보존해요.
template< class BidirIt, class UnaryPred >
BidirIt stable_partition( BidirIt first, BidirIt last, UnaryPred p );
- 반환 값: 첫 번째로
p가 거짓인 원소를 가리키는 반복자. 모두 참이면last. partition이 순서를 보장하지 않는 데 비해, 이 버전은 안정적이에요.- 복잡도: 충분한 임시 메모리가 있으면
N·log²N번의 비교·이동.
std::vector<int> v{1, 2, 3, 4, 5, 6};
auto it = std::stable_partition(v.begin(), v.end(),
[](int x){ return x % 2 == 0; });
// 짝수들이 원래 순서대로 앞으로
순서를 유지하며 분할해야 할 때 쓰는 함수예요. partition보다 비싸지만 안정적이에요.