4. partial_sort_copy

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

履歴 編集

function template
<algorithm>

std::partial_sort_copy

namespace std {
  template <class InputIterator, class RandomAccessIterator>
  RandomAccessIterator
    partial_sort_copy(InputIterator first,
                      InputIterator last,
                      RandomAccessIterator result_first,
                      RandomAccessIterator result_last); // (1) C++03

  template <class InputIterator, class RandomAccessIterator>
  constexpr RandomAccessIterator
    partial_sort_copy(InputIterator first,
                      InputIterator last,
                      RandomAccessIterator result_first,
                      RandomAccessIterator result_last); // (1) C++20

  template <class InputIterator, class RandomAccessIterator, class Compare>
  RandomAccessIterator
    partial_sort_copy(InputIterator first,
                      InputIterator last,
                      RandomAccessIterator result_first,
                      RandomAccessIterator result_last,
                      Compare comp);                     // (2) C++03

  template <class InputIterator, class RandomAccessIterator, class Compare>
  constexpr RandomAccessIterator
    partial_sort_copy(InputIterator first,
                      InputIterator last,
                      RandomAccessIterator result_first,
                      RandomAccessIterator result_last,
                      Compare comp);                     // (2) C++20

  template <class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator>
  RandomAccessIterator
    partial_sort_copy(ExecutionPolicy&& exec,
                      ForwardIterator first,
                      ForwardIterator last,
                      RandomAccessIterator result_first,
                      RandomAccessIterator result_last); // (3) C++17

  template <class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator,
            class Compare>
  RandomAccessIterator
    partial_sort_copy(ExecutionPolicy&& exec,
                      ForwardIterator first,
                      ForwardIterator last,
                      RandomAccessIterator result_first,
                      RandomAccessIterator result_last,
                      Compare comp);                     // (4) C++17
}

概要

イテレータ範囲[first, last)を部分的にソートした結果を他の範囲[result_first, result_last)にコピーする。

テンプレートパラメータ制約

  • RandomAccessIterator は ValueSwappable の要件を満たしている必要がある。*result_first の型は MoveConstructible と MoveAssignable の要件を満たしていること

効果

イテレータ範囲[first,last) にある要素の中から、min(last - first, result_last - result_first) 個の要素をソート済みの状態で [result_first,result_first + min(last - first, result_last - result_first)) に配置する。

戻り値

result_last と result_first + (last - first) で小さい方が返される

計算量

ほぼ (last - first) * log(min(last - first, result_last - result_- first)) 回の比較を行う

例

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

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

  // vから小さい順に2要素取り出す
  std::vector<int> result(2);
  std::partial_sort_copy(v.begin(), v.end(), result.begin(), result.end());

  std::for_each(result.begin(), result.end(), [](int x) {
    std::cout << x << std::endl;
  });
}

出力

1
2

参照