4. partition

最終更新日時(UTC):
が更新

履歴 編集

function template
<algorithm>

std::partition

namespace std {
  template <class BidirectionalIterator, class Predicate>
  BidirectionalIterator
    partition(BidirectionalIterator first,
              BidirectionalIterator last,
              Predicate pred);              // (1) C++03

  template <class ForwardIterator, class Predicate>
  ForwardIterator
    partition(ForwardIterator first,
              ForwardIterator last,
              Predicate pred);              // (1) C++11

  template <class ForwardIterator, class Predicate>
  constexpr ForwardIterator
    partition(ForwardIterator first,
              ForwardIterator last,
              Predicate pred);              // (1) C++20

  template <class ExecutionPolicy, class ForwardIterator, class Predicate>
  ForwardIterator
    partition(ExecutionPolicy&& exec,
              ForwardIterator first,
              ForwardIterator last,
              Predicate pred);              // (2) C++17
}

概要

イテレータ範囲[first, last)を条件によって区分化する。

要件

  • C++03 : BidirectionalIterator は ValueSwappable の要件を満たしている必要がある。
  • C++11 : ForwardIterator は ValueSwappable の要件を満たしている必要がある。

効果

[first,last) 内にある pred を満たす全ての要素を、pred を満たさない全ての要素より前に移動させる。

戻り値

[first,i) 内にあるイテレータ j について pred(*j) != false を満たし、[i,last) 内にあるイテレータ k について pred(*k) == false を満たすような、イテレータ i を返す。つまり、区分化された境界を指すイテレータを返す。

計算量

N = last - firstとして

  • (1) : ForwardIterator が BidirectionalIterator の要求を満たしている場合、最大で N / 2 回 swap され、そうでない場合、最大で N 回 swap される。それに加えて、正確に N 回だけ述語が適用される
  • (2) : O(NlogN) 回の swap に加え、述語が O(N) 回適用される

例

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
  std::vector<int> v = {1, 2, 3, 4, 5};

  // 偶数グループと奇数グループに分ける
  auto pos = std::partition(v.begin(), v.end(), [](int x) { return x % 2 == 0; });

  // 条件x % 2 == 0を満たす要素
  std::for_each(v.begin(), pos, [](int x) {
   std::cout << x << std::endl;
  });

  // それ以外の要素
  std::cout << "----" << std::endl;
  std::for_each(pos, v.end(), [](int x) {
   std::cout << x << std::endl;
  });
}

出力

4
2
----
3
1
5

実装例

template <class ForwardIterator, class Predicate>
ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred)
{
  first = std::find_if_not(first, last, pred);
  auto it = std::find_if(first, last, pred);
  while (it != last) {
    std::iter_swap(first, it);
    first = std::find_if_not(first, last, pred);
    it = std::find_if(it, last, pred);
  }
  return first;
}

参照