namespace std {
template <class RandomAccessIterator>
void stable_sort(RandomAccessIterator first,
RandomAccessIterator last); // (1) C++03
template <class RandomAccessIterator>
constexpr
void stable_sort(RandomAccessIterator first,
RandomAccessIterator last); // (1) C++26
template <class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first,
RandomAccessIterator last,
Compare comp); // (2) C++03
template <class RandomAccessIterator, class Compare>
constexpr
void stable_sort(RandomAccessIterator first,
RandomAccessIterator last,
Compare comp); // (2) C++26
template<class ExecutionPolicy, class RandomAccessIterator>
void stable_sort(ExecutionPolicy&& exec,
RandomAccessIterator first,
RandomAccessIterator last); // (3) C++17
template <class ExecutionPolicy, class RandomAccessIterator, class Compare>
void stable_sort(ExecutionPolicy&& exec,
RandomAccessIterator first,
RandomAccessIterator last,
Compare comp); // (4) C++17
}
概要
イテレータ範囲[first, last)
を安定ソートで並べ替える
テンプレートパラメータ制約
RandomAccessIterator
はValueSwappable
の要件を満たしていること*first
の型はMoveConstructible
とMoveAssignable
の要件を満たしていること
効果
[first,last)
の範囲をソートする
戻り値
なし
計算量
最大で N log^2(N) (N == last - first
)回の比較を行う。ただし、十分なメモリがあれば N log(N) になる。
備考
同じ値が複数あった場合に、ソート前の位置関係が保たれる、「安定ソート」を行う。 一般的なマージソートで実装される。
例
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
std::vector<int> v = {3, 1, 4, 2, 5};
// 並べ替える
std::stable_sort(v.begin(), v.end());
std::for_each(v.begin(), v.end(), [](int x) {
std::cout << x << std::endl;
});
}
xxxxxxxxxx
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
std::vector<int> v = {3, 1, 4, 2, 5};
// 並べ替える
std::stable_sort(v.begin(), v.end());
std::for_each(v.begin(), v.end(), [](int x) {
std::cout << x << std::endl;
});
}
出力
1
2
3
4
5
参照
- P2562R1
constexpr
Stable Sorting- C++26から
constexpr
に対応した
- C++26から