std::partial_sort

ヘッダー `<algorithm>` で定義
template< class RandomIt > void partial_sort( RandomIt first, RandomIt middle, RandomIt last );	(1)	(C++20 以降 constexpr)
template< class ExecutionPolicy, class RandomIt > void partial_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt middle, RandomIt last );	(2)	(C++17以降)
template< class RandomIt, class Compare > void partial_sort( RandomIt first, RandomIt middle, RandomIt last, Compare comp );	(3)	(C++20 以降 constexpr)
template< class ExecutionPolicy, class RandomIt, class Compare > void partial_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt middle, RandomIt last, Compare comp );	(4)	(C++17以降)

範囲 [first, middle) に、範囲 [first, last) 内の要素のうち、昇順にソートされた middle − first 個の最小の要素を配置し直します。

等しい要素の順序は保持される保証はありません。範囲 [middle, last) 内の残りの要素の順序は未指定です。

1) 要素は sorted で、operator<(C++20まで)std::less{}(C++20以降) を使用します。

3) 要素は comp に従ってソートされます。

2,4) (1,3)と同じだが、policyに従って実行される。

これらのオーバーロードは、以下のすべての条件が満たされた場合にのみオーバーロード解決に参加する。

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> が true である。	(C++20まで)
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> は true です。	(C++20以降)

次のいずれかの条件が満たされる場合、動作は未定義です。

[first, middle) または [middle, last) が有効な範囲ではありません。

*first の型は Swappable ではありません。	(C++11まで)
`RandomIt` は ValueSwappable ではありません。 first の型は MoveConstructible ではありません。 first の型が MoveAssignable ではありません。	(C++11以降)

first, last	-	再配置する要素の範囲を定義するイテレータのペア
middle	-	範囲 `[`first`,` middle`)` にはソートされた要素が含まれます。
policy	-	使用する実行ポリシー
comp	-	比較関数オブジェクト（つまり、Compare の要件を満たすオブジェクト）。最初の引数が2番目の引数より小さい（つまり、前に順序付けられる）場合に true を返します。比較関数のシグネチャは、以下と同等でなければならない。 bool cmp(const Type1& a, const Type2& b); シグネチャは const& を持つ必要はありませんが、関数は渡されたオブジェクトを変更してはならず、値カテゴリに関係なく、(おそらく const の) `Type1` と `Type2` のすべての値を受け入れられる必要があります (したがって、`Type1&` は許可されません。また、`Type1` のムーブがコピーと同等でない限り、`Type1` も許可されません(C++11以降))。 Type1 および Type2 は、RandomIt 型のオブジェクトを逆参照してから、それらの両方に暗黙的に変換できる必要があります。
型要件
- `RandomIt`はLegacyRandomAccessIteratorの要件を満たす必要がある。
- `Compare`はCompareの要件を満たす必要がある。

[edit] 計算量

$\scriptsize M$ $M$ を middle - first、$\scriptsize N$ $N$ を last - first とすると

1,2)

N\cdotlog(M)

回の比較（operator<(until C++20)std::less{}(since C++20)）。

3,4)

N\cdotlog(M)

回のコンパレータ comp の適用。

[edit] 例外

ExecutionPolicy というテンプレートパラメータを持つオーバーロードは、次のようにエラーを報告します。

アルゴリズムの一部として呼び出された関数の実行が例外をスローし、ExecutionPolicy が標準ポリシーのいずれかである場合、std::terminate が呼び出されます。その他の ExecutionPolicy の場合、動作は実装定義です。
アルゴリズムがメモリの割り当てに失敗した場合、std::bad_alloc がスローされます。

[edit] 可能な実装

libstdc++ および libc++ の実装を参照してください。

partial_sort (1)

template<typename RandomIt>
constexpr //< since C++20
void partial_sort(RandomIt first, RandomIt middle, RandomIt last)
{
    typedef typename std::iterator_traits<RandomIt>::value_type VT;
    std::partial_sort(first, middle, last, std::less<VT>());
}

partial_sort (3)

namespace impl
{
    template<typename RandomIt, typename Compare>
    constexpr //< since C++20
    void sift_down(RandomIt first, RandomIt last, const Compare& comp)
    {
        // sift down element at “first”
        const auto length = static_cast<std::size_t>(last - first);
        std::size_t current = 0;
        std::size_t next = 2;
        while (next < length)
        {
            if (comp(*(first + next), *(first + (next - 1))))
                --next;
            if (!comp(*(first + current), *(first + next)))
                return;
            std::iter_swap(first + current, first + next);
            current = next;
            next = 2 * current + 2;
        }
        --next;
        if (next < length && comp(*(first + current), *(first + next)))
            std::iter_swap(first + current, first + next);
    }
 
    template<typename RandomIt, typename Compare>
    constexpr //< since C++20
    void heap_select(RandomIt first, RandomIt middle, RandomIt last, const Compare& comp)
    {
        std::make_heap(first, middle, comp);
        for (auto i = middle; i != last; ++i)
        {
            if (comp(*i, *first))
            {
                std::iter_swap(first, i);
                sift_down(first, middle, comp);
            }
        }
    }
} // namespace impl
 
template<typename RandomIt, typename Compare>
constexpr //< since C++20
void partial_sort(RandomIt first, RandomIt middle, RandomIt last, Compare comp)
{
    impl::heap_select(first, middle, last, comp);
    std::sort_heap(first, middle, comp);
}

[edit] 注釈

[edit] アルゴリズム

一般的に使用されるアルゴリズムは、最小の要素を選択するための *heap select* と、選択された要素をヒープ内で昇順にソートするための *heap sort* です。

要素の選択にはヒープが使用されます（heap を参照）。たとえば、比較関数として operator< を使用する場合、middle − first 個の最小の要素を選択するために *max-heap* が使用されます。

選択後、[first, middle) の選択された要素をソートするために Heap sort が使用されます（std::sort_heap を参照）。

[edit] 意図された使用方法

std::partial_sort アルゴリズムは、[first, middle) の選択された要素が *少数定数個* の場合に、それらをソートするために使用することを意図しています。

[edit] 例

このコードを実行

#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
 
void print(const auto& s, int middle)
{
    for (int a : s)
        std::cout << a << ' ';
    std::cout << '\n';
    if (middle > 0)
    {
        while (middle-- > 0)
            std::cout << "--";
        std::cout << '^';
    }
    else if (middle < 0)
    {
        for (auto i = s.size() + middle; --i; std::cout << "  ")
        {}
 
        for (std::cout << '^'; middle++ < 0; std::cout << "--")
        {}
    }
    std::cout << '\n';
};
 
int main()
{
    std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
    print(s, 0);
    std::partial_sort(s.begin(), s.begin() + 3, s.end());
    print(s, 3);
    std::partial_sort(s.rbegin(), s.rbegin() + 4, s.rend());
    print(s, -4);
    std::partial_sort(s.rbegin(), s.rbegin() + 5, s.rend(), std::greater{});
    print(s, -5);
}

実行結果の例

5 7 4 2 8 6 1 9 0 3
 
0 1 2 7 8 6 5 9 4 3
------^
4 5 6 7 8 9 3 2 1 0
          ^--------
4 3 2 1 0 5 6 7 8 9
        ^----------

[edit] 不具合報告

以下の動作変更を伴う欠陥報告が、以前に公開されたC++標準に遡って適用されました。

DR	適用対象	公開された動作	正しい動作
P0896R4	C++98	`[`first`,` middle`)` および `[`middle`,` last`)` 有効な範囲であることが要求されていませんでした。	未定義の動作それらのいずれかが無効な場合

[edit] 関連項目

nth_element	与えられた範囲を部分的にソートし、指定された要素によってパーティション化されるようにする (関数テンプレート) [編集]
partial_sort_copy	要素の範囲をコピーして部分的にソートする (関数テンプレート) [編集]
stable_sort	等しい要素間の順序を維持しながら要素の範囲をソートする (関数テンプレート) [編集]
sort	範囲を昇順にソートする (関数テンプレート) [編集]
ranges::partial_sort (C++20)	範囲の最初のN個の要素をソートする (アルゴリズム関数オブジェクト)[編集]

コンパイラサポート
フリースタンディングとホスト
言語
標準ライブラリ
標準ライブラリヘッダー
名前付き要件
機能テストマクロ (C++20)
言語サポートライブラリ
コンセプトライブラリ (C++20)
診断ライブラリ
メモリ管理ライブラリ
メタプログラミングライブラリ (C++11)
汎用ユーティリティライブラリ
コンテナライブラリ
イテレータライブラリ
Rangesライブラリ (C++20)
アルゴリズムライブラリ
文字列ライブラリ
テキスト処理ライブラリ
数値ライブラリ
日付と時刻ライブラリ
入出力ライブラリ
ファイルシステムライブラリ (C++17)
並行サポートライブラリ (C++11)
実行制御ライブラリ (C++26)
Technical specifications (技術仕様)
シンボルインデックス
外部ライブラリ

cppreference.com

名前空間

変種

表示

操作