基本のソート(昇順)
std::sort()
std::vector<int> seq = {5, 2, 4, 1, 3};
std::sort(seq.begin(), seq.end());
for (int i = 0; i < seq.size(); i++) std::cout << seq[i] << " ";//1 2 3 4 5 ranges::sort()
std::vector<int> seq = {5, 2, 4, 1, 3};
//これはstd::sort(seq.begin(), seq.end())と同じ意味
std::ranges::sort(seq);
for (int i = 0; i < seq.size(); i++) std::cout << seq[i] << " ";//1 2 3 4 5 ranges::はC++20から対応しています。
ソート(降順)
std::sort()
std::vector<int> seq = {5, 2, 4, 1, 3};
std::sort(seq.begin(), seq.end(), std::greater<int>());
for (int i = 0; i < seq.size(); i++) std::cout << seq[i] << " ";//5 4 3 2 1 ranges::sort()
std::vector<int> seq = {5, 2, 4, 1, 3};
//これはstd::sort(seq.begin(), seq.end(), std::greater<int>())と同じ意味
std::ranges::sort(seq, std::greater());
for (int i = 0; i < seq.size(); i++) std::cout << seq[i] << " ";//5 4 3 2 1自作クラスのソート
自作クラスでソートをするには “何を基準にソートするか?” を定義する必要があるので
クラスの “比較演算子のオーバーロード” をすることで定義します
昇順なら<, 降順なら>をオーバーロードします(似てるので注意です!)
昇順ソート (クラス部分のコード)
class my_class {
public:
int id;
std::string name;
//idで昇順ソート
bool operator<(const my_class &other) const {
return id < other.id;
}
};降順ソート (クラス部分のコード)
class my_class {
public:
int id;
std::string name;
//idで降順ソート
bool operator>(const my_class &other) const {
return id > other.id;
}
};
/*
greater<>()の<>には、クラス名をいれてください
std::sort(seq.begin(), seq.end(), std::greater<my_class>());
*/
sort()の呼び出し時に、比較方法を与える(ラムダ式)
std::sort()の “三番目の引数にラムダ式を与える” 方法を紹介します
(std::ranges::sort()なら二番目の引数に与えればよいです)
T := 比較される型
//ラムダ式(戻り値がbool)
[](T 左側要素, T 右側要素)->bool {
/*ここに比較方法を書く*/
}std::vector<int> seq = {5, 2, 4, 1, 3};
/*
3で割った余りが小さいもの順にソート
(ただし、割った余りが同じ場合は数の大きさで昇順ソート)
*/
std::sort(seq.begin(), seq.end(), [](const int &left, const int &right)->bool {
int mod_left = left % 3;
int mod_right = right % 3;
if (mod_left == mod_right) return left < right;
else return mod_left < mod_right;
});
for (int i = 0; i < seq.size(); i++) std::cout << seq[i] << " ";//3 1 4 2 5priority_queueの優先順位を定義する
単なる昇順または降順に取り出される宣言
//大きいものの方が優先度が高くなる宣言
std::priority_queue<int> pq_1;
//小さいものの方が優先度が高くなる宣言
std::priority_queue<int, std::vector<int>, std::greater<int> > pq_2;自分で優先度の付け方を決める方法
/*
絶対値が大きいものほど優先順位が高いpriority_queueを宣言
(例として絶対値が大きいものにしただけで、自由に決めれます)
*/
std::priority_queue<int, std::vector<int>, decltype([](int left, int right)->bool {
return abs(left) < abs(right);
})> pq;
for (auto x : {-5, -2, 4, 1, 3}) pq.push(x);
while (!pq.empty()) {
std::cout << pq.top() << " ";//-5 4 3 -2 1
pq.pop();
}ほかにも色々ある!! ソート系関数
安定ソートをする → stable_sort()
ソートには安定ソートと不安定ソートがあり、これは安定ソートをするための関数です。
{安定・不安定}というのは“比較のための値で、同じ値が複数ある場合”にそれらをソートした際に
元の位置関係が保たれるかどうかのことです
例えば、先ほどこの記事で書いた”自作クラスで比較する場合”で考えてみましょう
std::vector<my_class> seq = {{4, "C"}, {1, "A"}, {3, "D"}, {2, "B"}, {3, "E"}};
/*
これは不安定ソート!!
3という値が2つあるため、これらの順番(位置関係)が保証されない。(うまくいくこともあるが...)
*/
std::sort(seq.begin(), seq.end());これらの元の位置関係を保証してくれるのがstablesort()です
std::vector<my_class> seq = {{4, "C"}, {1, "A"}, {3, "D"}, {2, "B"}, {3, "E"}};
std::stable_sort(seq.begin(), seq.end());ソート済みかを返す → is_sorted()
昇順ソートされているか?
std::vector<int> seq = {5, 2, 4, 1, 3};
std::cout << std::boolalpha << std::ranges::is_sorted(seq) << std::endl;//false
std::ranges::sort(seq);
std::cout << std::boolalpha << std::ranges::is_sorted(seq) << std::endl;//true降順ソートされているか?
std::vector<int> seq = {5, 2, 4, 1, 3};
std::cout << std::boolalpha << std::ranges::is_sorted(seq, std::greater<int>()) << std::endl;//false
std::ranges::sort(seq, std::greater<int>());
std::cout << std::boolalpha << std::ranges::is_sorted(seq, std::greater<int>()) << std::endl;//true
コメント