[39] - Partition

Partitioning Operations

이번에 공부할 것은 주로 std::partition에 관련한 내용일 것입니다. 설명은 어떤 격납고[container, 컨테이너 등등]를 두 개로 나눌 수 있다고 되어 있습니다. 해당 함수의 Parameter와 return value를 좀 살펴보면 어떤 컨테이너의 범위[range]를 받고 그룹이 두 개로 나뉘는 지점에 해당하는 iterator를 반환한다고 합니다. Unary Predicate를 기준으로 false/true를 나누어서 그룹을 나눌 수 있도록 설계되어 있는 듯 합니다.

간단하게 작성을 해봤습니다.

애초에 컨테이너가 정렬이 되는 것 같습니다. 컨테이너 전체를 출력하면 다음과 같은 결과를 얻습니다.

보면 5와 Funf를 기준으로 Pred의 기준에 부합 여부가 달라집니다. std::partition은 잘 보면 격납된 컨테이너 내부의 요소들의 순서를 뒤섞습니다. 추측하기로는 아마 내부적인 문제로 인해서 정렬을 하지 않고 튀어나오는 것 같습니다. 그래도 Standard Library에는 순서를 유지해 주는 함수도 존재합니다. 그것은 std::stable_partition입니다.

보는 것처럼 더 이상 순서가 엉망으로 섞이지 않습니다. However, there is no free lunch. stable버전의 함수는 그렇지 않은 버전보다 느리게 동작합니다. std::is_partitioned는 어떤 범위에 격납된 컨테이너 내의 요소들이 partition이 되어 있는지 아닌지 확인합니다. 직관적이기 때문에 한 번 해보면 될 것 같습니다. 이 다음에 볼 std::partition_copy는 흥미로운 점이 있습니다.

std::partition_copy

개인적으로 생긴 것부터 심상치 않다고 생각합니다.

?

기본적으로 하나의 input에 두 개의 컨테이너를 std::pair형태로 반환합니다. 잘 살펴보면 OutputIt1, OutputIt2로 되어 있습니다. 그리고 True/False 즉 나누는 기준인 UnaryPredicate는 똑같이 하나 존재합니다. 정리하면 하나의 범위를 주면 pred에 따라서 false와 true로 나뉜 두 개의 컨테이너를 받을 수 있습니다. 예제 코드를 짜보기 전에 다른 것부터 얼른 공부하고 오겠습니다. std::partition_point라는 함수입니다.

이 함수는 partition이 된 컨테이너에 대해서 Unary Predicate의 변곡 지점을 가리키는 iterator를 반환해줍니다. 즉, Predicate의 참/거짓 값이 다른 두 번째 컨테이너의 첫 iterator를 반환하는 함수입니다. 이걸 묶어서 그냥 Partition point라고 합니다. 참고로 이 함수의 Time Complexity는 O(log(n))으로 이진탐색을 합니다. 이제 partition에 대한 종합적인 실험적 코드를 작성해보도록 합니다. 해결하고 싶은 문제를 정리하면 다음과 같습니다.

1. integer와 string을 포함하는 임의의 데이터 타입(ItemType)을 정의합니다.

2. 결과를 보기 쉽게 해당 데이터 타입에 대해 output stream을 overload 합니다.

3. ItemType을 갖는 벡터 (std::vector<ItemType>)을 두 개(a, b) 정의하되, a에는 두 개 이상의 ItemType을 갖고 있는 상태, b는 아무것도 없는 상태로 만듭니다.

4. a와 b에 대해 SplitPartition이라는 함수를 적용할 것이며 이 함수는 (InputIter, OutputIter, Unary Predicate)의 paramter list를 갖습니다.

5-1. predicate 는 ItemType의 integer가 4보다 클 때 true를 반환하고 그 외의 모든 경우는 false를 반환합니다.

5-2. predicate에서 false 판정을 받은 요소는 a에서 제거되고 b로 이동합니다.

-> SplitPartition을 구현해봅시다.

함수를 만드는 논리는 가이드라인 그대로 입니다. 개인적으로 자잘한 오류 때문에 너무 고생했습니다. 특히, 함수 호출의 람다 식을 다음과 같이 만들면 오류를 얻는데 해결하는게 너무 힘들었습니다.

auto& _x로 쓰면 다음과 같은 오류를 얻습니다.

이걸 조금 꼼꼼하게 읽어보니 람다 식에 문제가 있는 것 같았습니다.

그래서 auto& 를 const auto&&로 해주니 되긴 합니다. 왜 그랬는지 아직 모름.