std::stable_sort

ヘッダ `<algorithm>`
template< class RandomIt > void stable_sort( RandomIt first, RandomIt last );	で定義 (1)	(C++26 から constexpr)
template< class ExecutionPolicy, class RandomIt > void stable_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last );	(2)	(C++17 から)
template< class RandomIt, class Compare > void stable_sort( RandomIt first, RandomIt last, Compare comp );	(3)	(C++26 から constexpr)
template< class ExecutionPolicy, class RandomIt, class Compare > void stable_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp );	(4)	(C++17 から)

範囲 [first, last) 内の要素を非降順にソートします。同等の要素の順序は保持されることが保証されます。

1) 要素は sorted に関して比較されます（operator<(C++20まで)std::less{}(C++20から)）。

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

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

これらのオーバーロードは、次の式の値が true である場合にのみオーバーロード解決に参加します。

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(C++20まで)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(C++20から)

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

`*first` の型が Swappable でない。	(C++11まで)
`RandomIt` が ValueSwappable でない。 `first` の型が MoveConstructible でない。 `first` の型が MoveAssignable でない。	(C++11から)

パラメータ

first, last	-	ソートする要素の範囲を定義するイテレータのペア
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 の要件を満たさなければならない。

計算量

与えられた $\scriptsize N$ $N$ を last - first として：

1,2)

O(N\cdotlog(N))

回の比較（十分な追加メモリが利用可能な場合）、そうでない場合は

O(N\cdotlog 2 (N))

回の比較を使用して実行されます。

3,4)

O(N\cdotlog(N))

回の比較子 comp の適用（十分な追加メモリが利用可能な場合）、そうでない場合は

O(N\cdotlog 2 (N))

回の適用。

例外

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

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

実装例

実装については libstdc++ および libc++ も参照してください。

注記

この関数は、ソート対象のシーケンスと同等のサイズの一時バッファの割り当てを試みます。割り当てに失敗した場合、効率の低いアルゴリズムが選択されます。

機能テストマクロ	値	標準	機能
`__cpp_lib_constexpr_algorithms`	`202306L`	(C++26)	constexpr 安定ソート、オーバーロード ( 1 ) , ( 3 )

例

このコードを実行

#include <algorithm>
#include <array>
#include <iostream>
#include <string>
#include <vector>
struct Employee
{
    int age;
    std::string name; // 比較には関与しない
};
bool operator<(const Employee& lhs, const Employee& rhs)
{
    return lhs.age < rhs.age;
}
#if __cpp_lib_constexpr_algorithms >= 202306L
consteval auto get_sorted()
{
    auto v = std::array{3, 1, 4, 1, 5, 9};
    std::stable_sort(v.begin(), v.end());
    return v;
}
static_assert(std::ranges::is_sorted(get_sorted()));
#endif
int main()
{
    std::vector<Employee> v{{108, "Zaphod"}, {32, "Arthur"}, {108, "Ford"}};
    std::stable_sort(v.begin(), v.end());
    for (const Employee& e : v)
        std::cout << e.age << ", " << e.name << '\n';
}

出力:

32, Arthur
108, Zaphod
108, Ford

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

sort	範囲の要素をソートする（関数テンプレート & アルゴリズム関数オブジェクト）
ranges::sort （C++20）	範囲の要素をソートする（関数テンプレート & アルゴリズム関数オブジェクト）
partial_sort	範囲の最初のN個の要素をソートする（関数テンプレート & アルゴリズム関数オブジェクト）
ranges::partial_sort （C++20）	範囲の最初のN個の要素をソートする（関数テンプレート & アルゴリズム関数オブジェクト）
stable_partition	要素を2つのグループに分割し、各グループ内の相対的な順序を保持する（関数テンプレート & アルゴリズム関数オブジェクト）
ranges::stable_partition （C++20）
ranges::stable_sort （C++20）	等価な要素間の相対的な順序を保持しながら範囲の要素をソートする（アルゴリズム関数オブジェクト）

ja.cppreference.net

Namespaces

Variants

std::stable_sort

目次

パラメータ

計算量

例外

実装例

注記

例

関連項目