std::ranges::stable_sort
| ヘッダ <algorithm>
|
||
| 呼び出しシグネチャ |
||
template< std::random_access_iterator I, std::sentinel_for<I> S,
class Comp = ranges::less, class Proj = std::identity >
requires std::sortable<I, Comp, Proj>
I stable_sort( I first, S last, Comp comp = {}, Proj proj = {} );
|
(1) | (C++20 から) (constexpr C++26 から) |
template< ranges::random_access_range R, class Comp = ranges::less,
class Proj = std::identity >
requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
ranges::borrowed_iterator_t<R>
stable_sort( R&& r, Comp comp = {}, Proj proj = {} );
|
(2) | (C++20 から) (constexpr C++26 から) |
範囲 [first, last) の要素を非降順にソートします。等価な要素の順序は 安定 (stable)、つまり保持されることが保証されます。
シーケンスは、コンパレータ comp に関して、任意のイテレータ it がシーケンスを指し、任意の非負整数 n について、it + n がシーケンスの要素を指す有効なイテレータであるとき、std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it) が false と評価される場合にソートされているとみなされます。
comp を使用して比較されます。
r を範囲として使用します。これは、ranges::begin(r) を first として、ranges::end(r) を last として使用するのと同様です。
このページで説明されている関数のようなエンティティは、アルゴリズム関数オブジェクト (非公式に niebloids として知られています)、つまり:
- それらのいずれかを呼び出す際に、明示的なテンプレート引数リストを指定することはできません。
- それらは ADL では見えません。
- 関数呼び出し演算子の左側の名前として 通常の非修飾名前検索 によってそれらのいずれかが見つかった場合、ADL は抑制されます。
パラメータ
| first, last | - | ソートする要素の 範囲 を定義するイテレータ-センチネルペア |
| r | - | ソートする範囲 |
| comp | - | 投影された要素に適用する比較関数 |
| proj | - | 要素に適用する投影関数 |
戻り値
last に等しいイテレータ。
計算量
N·log(N) 回の比較（追加メモリが利用可能な場合）。ここで N は ranges:: distance ( first, last ) である。 N·log²(N) 回の比較（それ以外の場合）。いずれの場合も、比較回数の2倍の射影操作が行われる。
注記
| 機能テスト マクロ | 値 | 標準 | 機能 |
|---|---|---|---|
__cpp_lib_constexpr_algorithms
|
202306L
|
(C++26) | constexpr 安定ソート |
実装例
この実装は、追加のメモリが利用できない場合に使用される低速なアルゴリズムのみを示しています。また、 MSVC STL および libstdc++ の実装も参照してください。
struct stable_sort_fn { template<std::random_access_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity> requires std::sortable<I, Comp, Proj> constexpr //< C++26以降 I operator()(I first, S last, Comp comp = {}, Proj proj = {}) const { auto count = ranges::distance(first, last); auto mid = first + count / 2; auto last_it = first + count; if (count <= 1) return last_it; (*this)(first, mid, std::ref(comp), std::ref(proj)); (*this)(mid, last_it, std::ref(comp), std::ref(proj)); ranges::inplace_merge(first, mid, last_it); return last_it; } template<ranges::random_access_range R, class Comp = ranges::less, class Proj = std::identity> requires std::sortable<ranges::iterator_t<R>, Comp, Proj> constexpr //< C++26以降 ranges::borrowed_iterator_t<R> operator()(R&& r, Comp comp = {}, Proj proj = {}) const { return (*this)(ranges::begin(r), ranges::end(r), std::move(comp), std::move(proj)); } }; inline constexpr stable_sort_fn stable_sort{}; |
例
#include <algorithm> #include <array> #include <functional> #include <iomanip> #include <iostream> void print(const auto& seq) { for (const auto& elem : seq) std::cout << elem << ' '; std::cout << '\n'; } struct Particle { std::string name; double mass; // MeV friend std::ostream& operator<<(std::ostream& os, const Particle& p) { return os << '\n' << std::left << std::setw(8) << p.name << " : " << p.mass; } }; int main() { std::array s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3}; // デフォルトのoperator<を使用してソート std::ranges::stable_sort(s); print(s); // 標準ライブラリの比較関数オブジェクトを使用してソート std::ranges::stable_sort(s, std::ranges::greater()); print(s); // カスタム関数オブジェクトを使用してソート struct { bool operator()(int a, int b) const { return a < b; } } customLess; std::ranges::stable_sort(s.begin(), s.end(), customLess); print(s); // ラムダ式を使用してソート std::ranges::stable_sort(s, [](int a, int b) { return a > b; }); print(s); // 射影を使用したソート Particle particles[] { {"Electron", 0.511}, {"Muon", 105.66}, {"Tau", 1776.86}, {"Positron", 0.511}, {"Proton", 938.27}, {"Neutron", 939.57} }; print(particles); std::ranges::stable_sort(particles, {}, &Particle::name); //< 名前でソート print(particles); std::ranges::stable_sort(particles, {}, &Particle::mass); //< 質量でソート print(particles); }
出力:
0 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 0 Electron : 0.511 Muon : 105.66 Tau : 1776.86 Positron : 0.511 Proton : 938.27 Neutron : 939.57 Electron : 0.511 Muon : 105.66 Neutron : 939.57 Positron : 0.511 Proton : 938.27 Tau : 1776.86 Electron : 0.511 Positron : 0.511 Muon : 105.66 Proton : 938.27 Neutron : 939.57 Tau : 1776.86
関連項目
(C++20) |
範囲の要素をソートする (アルゴリズム関数オブジェクト) |
(C++20) |
範囲の最初のN個の要素をソートする (アルゴリズム関数オブジェクト) |
(C++20) |
要素を2つのグループに分割し、各グループ内での相対順序を保持する (アルゴリズム関数オブジェクト) |
| 同等な要素間の相対順序を保持しながら範囲の要素をソートする (関数テンプレート) |