【C++】複数要素のソートがしたいのでstable_sortを使ってみた

stable_sortって？

 stable_sort - cpprefjp C++日本語リファレンス

「安定ソート」を行う。一般的なマージソートで実装される。そのため、メモリを消費している。

と言っても、上のリファレンスだけだといまいちわからない…

まず、安定ソートってなんだ？

ということで不安定なソートと安定ソートを出してくれている以下のサイトを参考にする。

C++のsortとstable_sortの違い - Qiita

確かにsortで二回やると異なった結果が出力されるけどstable_sortだと同じ結果が出力されるようだ。それを「安定」ということなのかも。

では、本題の複数要素とは

sort - cpprefjp C++日本語リファレンス

stable_sortではなく、sortのリファレンスにある「ユーザー定義型の配列を並び替える（C++11）」を見てみよう。

その中では

struct PersonLess { // 大小比較用の関数オブジェクトを定義することもできる
  bool operator()(const Person& a, const Person& b) const noexcept {
    // キーとして比較したい要素を列挙する
    return std::tie(a.id, a.age, a.name) < std::tie(b.id, b.age, b.name);
  }
};

を参考として複数要素のソートを行われている。

でも、参考にしづらいし、なにより全てが昇順の場合となっており、複雑に絡み合ったパターンを全部作った場合、それだけ必要になり、さらには要素が増えたり優先度が変わるたびに新しく定義する必要が出てしまう。

もっと少ない数で済ませたーい

ということで、安定したstable_sort君と昇順降順のみの定義だけで行えるようにしてみました。

enum Type
{
	Human,
	Enemy,
	MAX
};

struct Card
{
	int id;
	int sort_id;
	Type type;
};

struct UpId {
	bool operator()(const Card& a, const Card& b) {
		return a.id < b.id;
	}
};
struct DownId {
	bool operator()(const Card& a, const Card& b) {
		return a.id > b.id;
	}
};
struct UpType {
	bool operator()(const Card& a, const Card& b) {
		return a.type < b.type;
	}
};
struct UpSortId {
	bool operator()(const Card& a, const Card& b) {
		return a.sort_id < b.sort_id;
	}
};

struct Up {
	bool operator()(const Card& a, const Card& b) {
		return std::tie(a.type, a.id, a.sort_id) < std::tie(b.type, b.id, b.sort_id);
	}
};

int main()
{
	std::vector mv_card;
	mv_card.push_back({ 1, 1, Type::Human });
	mv_card.push_back({ 5, 2, Type::Human });
	mv_card.push_back({ 2, 3, Type::Enemy });
	mv_card.push_back({ 7, 4, Type::Human });
	mv_card.push_back({ 4, 5, Type::Enemy });
	std::vector mv_card_copy;
	mv_card_copy = mv_card;
	std::vector mv_card_copy_copy;
	mv_card_copy_copy = mv_card;

	// 優先度は上からType→Id→SortId
	std::stable_sort(mv_card.begin(), mv_card.end(), UpSortId{});
	std::stable_sort(mv_card.begin(), mv_card.end(), UpId{});
	std::stable_sort(mv_card.begin(), mv_card.end(), UpType{});

	// 優先度は上からId→Type→SortId
	std::stable_sort(mv_card_copy.begin(), mv_card_copy.end(), UpSortId{});
	std::stable_sort(mv_card_copy.begin(), mv_card_copy.end(), UpType{});
	std::stable_sort(mv_card_copy.begin(), mv_card_copy.end(), UpId{});

	std::stable_sort(mv_card_copy_copy.begin(), mv_card_copy_copy.end(), Up{});

	for (auto& card : mv_card)
	{
		std::cout << card.id << ", " << card.sort_id << ", " << card.type << std::endl;
	}

	std::cout << std::endl;

	for (auto& card : mv_card_copy)
	{
		std::cout << card.id << ", " << card.sort_id << ", " << card.type << std::endl;
	}

	std::cout << std::endl;

	for (auto& card : mv_card_copy_copy)
	{
		std::cout << card.id << ", " << card.sort_id << ", " << card.type << std::endl;
	}

	// Idを降順にする
	std::stable_sort(mv_card_copy.begin(), mv_card_copy.end(), UpSortId{});
	std::stable_sort(mv_card_copy.begin(), mv_card_copy.end(), UpType{});
	std::stable_sort(mv_card_copy.begin(), mv_card_copy.end(), DownId{});

	std::cout << std::endl;

	for (auto& card : mv_card_copy)
	{
		std::cout << card.id << ", " << card.sort_id << ", " << card.type << std::endl;
	}

	// Idを昇順に戻す
	std::stable_sort(mv_card_copy.begin(), mv_card_copy.end(), UpSortId{});
	std::stable_sort(mv_card_copy.begin(), mv_card_copy.end(), UpType{});
	std::stable_sort(mv_card_copy.begin(), mv_card_copy.end(), UpId{});

	std::cout << std::endl;

	for (auto& card : mv_card_copy)
	{
		std::cout << card.id << ", " << card.sort_id << ", " << card.type << std::endl;
	}

	return 0;
}

1, 1, 0
5, 2, 0
7, 4, 0
2, 3, 1
4, 5, 1

1, 1, 0
2, 3, 1
4, 5, 1
5, 2, 0
7, 4, 0

1, 1, 0
5, 2, 0
7, 4, 0
2, 3, 1
4, 5, 1

7, 4, 0
5, 2, 0
4, 5, 1
2, 3, 1
1, 1, 0

1, 1, 0
2, 3, 1
4, 5, 1
5, 2, 0
7, 4, 0

という感じでね、やりたいことはできたんじゃないかと。

 いやいや、これも昇順と降順の数だけ定義してるやないか～～～～いって。

もっといいやり方あると思うんだよなぁ…どこぉ……

正直本人もよくわかんなくなっちゃっためう…

一旦現状の備忘録として、ね。