partition

<algorithm> 에 정의됨

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 를 수정하면 안됩니다.

실행 예제

#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';
}

실행 결과

벡터 초기 모습:
    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

구현 예시

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 : 특정 범위의 원소들를 파티션한다. 이 때 원소들의 상대적 순서는 바꾸지 않는다.

첫 댓글을 달아주세요!

강좌에 관련 없이 궁금한 내용은 여기를 사용해주세요

다음으로 로그인

Sign in with GoogleSign in with Google

또는 직접 입력하세요 (댓글 수정시 비밀번호가 필요합니다)

댓글 달기

댓글을 불러오는 중입니다..