std:: stable_sort

From cppreference.net

定義先ヘッダ `<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 < (until C++20) std:: less { } (since 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 の型が 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

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

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

cppreference.net

Namespaces

Variants

std:: stable_sort

目次

パラメータ

計算量

例外

実装例

注記

例

関連項目