StablePartition

범위 내의 요소들을 두 개의 분리 집합으로 분류합니다. 여기서 단일 술어를 만족시키는 요소들은 만족시키지 못하는 요소들보다 앞서고 동일한 요소들의 상대적 순서는 유지됩니다.

template <class Bi, class Pred>
Bi StablePartition (
    Bi                  first,
    Bi                  last,
    Pred                pred
);

Template 파라미터

Bi

양방향 반복자입니다.

Pred

단항 술어(Unary predicate)입니다.

파라미터

first

분할될 범위의 1번째 요소의 위치를 설명하는 양방향 반복자입니다.

last

분할될 범위의 마지막 직전 요소의 위치를 설명하는 양방향 반복자입니다.

pred

요소를 분류할 경우 충족되는 조건을 정의하는 사용자 정의 술어 함수 객체입니다. 술어는 1개의 인자를 취하며 true 또는 false를 리턴합니다.

리턴 값

술어 조건을 만족하지 않는 범위에서 1번째 요소의 위치를 설명하는 양방향 반복자입니다.

설명

StablePartition은 Partition와 많이 비슷합니다: 이것은 술어 pred를 기반으로 범위 [first, last)의 요소들을 재정렬합니다. 이때 pred를 만족하는 요소들 전부는 그것을 만족시키지 못한 다른 요소들 앞에 나타납니다. 후조건은 다음과 같습니다. 범위 [first, last)의 일부 반복자 mid가 있다고 하면 범위 [first, mid)의 모든 반복자 i에 대해서 pred (*i)는 true이고 범위 [mid, last)의 모든 반복자 i에 대해서 pred (*i)는 false입니다. StablePartition의 리턴 값은 mid입니다. StablePartition은 상대적인 순서 보존을 보장한다는 점에서 Partition과 다릅니다. 즉, pred(x) == pred(y)의 조건을 만족하는 x와 y가 [first, last)의 요소들이라면 x가 y보다 앞설 경우, StablePartition을 호출한 후에도 여전히 x가 y보다 앞선다는 것이 맞습니다.

참고사항

알고리즘