algorithm_stable_partition
algorithm_stable_partition (안정적 파티셔닝)
std::stable_partition는 대상 범위를 술어 p를 기준으로 파티셔닝하면서, 각 그룹 내 요소들의 상대적 순서를 보존해요. std::partition과 달리 안정적이에요.
출처: cppreference
본문
std::stable_partition는 대상 범위 [first, last)의 요소 e를 표현식 bool(p(e))에 대해 파티셔닝해요: p를 만족하는 모든 요소가 그렇지 않은 모든 요소보다 앞에 와요. 두 그룹 모두에서 요소들의 상대적 순서가 보존돼요. <algorithm> 헤더에 정의되어 있어요.
template< class BidirIt, class UnaryPred >
BidirIt stable_partition( BidirIt first, BidirIt last, UnaryPred p );
병렬 실행 정책을 받는 오버로드도 있어요.
반환값 (Return value)
파티션 지점을 가리키는 반복자예요. 즉 첫 번째 부분 범위의 끝(past-the-end)으로, p를 만족하지 않는 첫 번째 요소를 가리켜요.
복잡도 (Complexity)
N을 std::distance(first, last)라고 하면 적절한 추가 메모리가 있으면 𝓞(N)번의 스왑과 N번의 p 적용이 필요해요. 추가 메모리가 없으면 𝓞(N·log N)번의 스왑이 필요해요.
예제 (Example)
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9};
auto it = std::stable_partition(v.begin(), v.end(),
[](int x) { return x % 2 == 0; });
for (auto e = v.begin(); e != it; ++e) std::cout << *e << ' ';
std::cout << "| ";
for (auto e = it; e != v.end(); ++e) std::cout << *e << ' ';
std::cout << '\n';
}
출력:
2 4 6 8 | 1 3 5 7 9