----------------
title : C++ 레퍼런스 - partition 함수 (<algorithm>)
cat_title : partition
ref_title : partition, std::partition
path : /C++ Reference/algorithm
publish_date : 2019-04-13
----------------

##@ cpp-ref-start

#@ partition

`<algorithm>` 에 정의됨

```cpp-formatted
template <class ForwardIt, class UnaryPredicate>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p);

template <class ExecutionPolicy, class ForwardIt, class UnaryPredicate>
ForwardIt partition(ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                    UnaryPredicate p);
```

범위 (`first` 부터 `last` 전 까지) 내의 원소들에 대해 `p` 가 참인 원소들이 `p` 가 거짓인 원소들 앞에 올 수 있도록 재배치 합니다. 원소들 사이의 상대적 순서는 바뀔 수 있습니다.

`policy` 를 인자를 받는 경우, 어떠한 방식으로 실행할지 지정할 수 있습니다. 해당 함수가 오버로드 되기 위해서는 `std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>` 가 참이어야 합니다.

### 인자들

* `first, last`	: 작업을 수행할 원소들의 범위를 가리키는 반복자
* `policy`	-	어떠한 방식으로 실행 시킬지. `ExecutionPolicy` 참조.
* `p`	- 원소를 하나만 받는 함수로, 해당 원소가 다른 원소들 보다 앞에 와야 한다면 참을 리턴해야 한다.  `p(v)` 의 리턴값은 반드시 `bool` 로 변환가능어야만 하며 `v` 를 수정하면 안됩니다.

### 실행 예제

```cpp-formatted
#include <algorithm>
#include <forward_list>
#include <iostream>
#include <iterator>
#include <vector>

template <class ForwardIt>
void quicksort(ForwardIt first, ForwardIt last) {
  if (first == last) return;
  auto pivot = *std::next(first, std::distance(first, last) / 2);
  ForwardIt middle1 =
    std::partition(first, last, [pivot](const auto& em) { return em < pivot; });
  ForwardIt middle2 = std::partition(
    middle1, last, [pivot](const auto& em) { return !(pivot < em); });
  quicksort(first, middle1);
  quicksort(middle2, last);
}

int main() {
  std::vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  std::cout << "벡터 초기 모습:\n    ";
  for (int elem : v) std::cout << elem << ' ';

  auto it =
    std::partition(v.begin(), v.end(), [](int i) { return i % 2 == 0; });

  std::cout << "\n파티션 된 벡터:\n    ";
  std::copy(std::begin(v), it, std::ostream_iterator<int>(std::cout, " "));
  std::cout << " * ";
  std::copy(it, std::end(v), std::ostream_iterator<int>(std::cout, " "));

  std::forward_list<int> fl = {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92};
  std::cout << "\n정렬되지 않은 리스트:\n    ";
  for (int n : fl) std::cout << n << ' ';
  std::cout << '\n';

  quicksort(std::begin(fl), std::end(fl));
  std::cout << "퀵소트를 이용해 정렬함:\n    ";
  for (int fi : fl) std::cout << fi << ' ';
  std::cout << '\n';
}
```

```exec
벡터 초기 모습:
    0 1 2 3 4 5 6 7 8 9 
파티션 된 벡터:
    0 8 2 6 4  *  5 3 7 1 9 
정렬되지 않은 리스트:
    1 30 -4 3 5 -4 1 6 -8 2 -5 64 1 92 
퀵소트를 이용해 정렬함:
    -8 -5 -4 -4 1 1 1 2 3 5 6 30 64 92
```

### 구현 예시

```cpp-formatted
template <class ForwardIt, class UnaryPredicate>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p) {
  first = std::find_if_not(first, last, p);
  if (first == last) return first;

  for (ForwardIt i = std::next(first); i != last; ++i) {
    if (p(*i)) {
      std::iter_swap(i, first);
      ++first;
    }
  }
  return first;
}
```

### 참고 자료

* `is_partitioned` : 특정 범위의 원소들이 파티션 되어 있는지 확인한다.
* `stable_partition` : 특정 범위의 원소들를 파티션한다. 이 때 원소들의 상대적 순서는 바꾸지 않는다.