C++20 比較関数と任意の型のソート
はじめに
想定読者は過去の私である。 なぜこう教えてくれなかったのだ。 次なる私よ、あなたのために。
主題のとおり、C++20を前提に書いている。
もしC++20をコンパイルできない古いgccを使用しているならば、
新しいgccをsudo apt install g++-13だとか12だとか11だとか10をして、installできると思う。
詳細は己の師にくわしく聞くといい。
キーワード:
比較関数
ここにint型オブジェクトa、bがあって、いくつかの二項演算ができる:
int a{}, b{}; bool less = a < b; // OK bool greater = a > b; // OK bool equal_to = a == b; // OK bool not_equal_to = a != b; // OK bool less_equal = a <= b; // OK bool greater_equal = a >= b; // OK
ここに任意のT型オブジェクトa、bがあって、いくつかの二項演算ができるかもしれない:
T a{}, b{};
bool less = a < b; // ?
bool greater = a > b; // ?
bool equal_to = a == b; // ?
bool not_equal_to = a != b; // ?
bool less_equal = a <= b; // ?
bool greater_equal = a >= b; // ?
これらの二項演算を可能とするには、それぞれの演算の定義が必要:
struct T { value_type value; bool operator< (const T& rhs) const { return this->value < rhs.value; } bool operator> (const T& rhs) const { return this->value > rhs.value; } bool operator==(const T& rhs) const { return this->value == rhs.value; } bool operator!=(const T& rhs) const { return this->value != rhs.value; } bool operator<=(const T& rhs) const { return this->value <= rhs.value; } bool operator>=(const T& rhs) const { return this->value >= rhs.value; } }; T a{}, b{}; bool less = a < b; // OK bool greater = a > b; // OK bool equal_to = a == b; // OK bool not_equal_to = a != b; // OK bool less_equal = a <= b; // OK bool greater_equal = a >= b; // OK
これらの二項演算は#include <compare>してoperator<=>を利用することで一挙に定義できる。
また、friend指定することでグローバルに利用できる:
#include <compare> // 必要 struct T { value_type value; // これが一番かんたんに実装できる // しかし、非静的メンバ変数が(大量に)ある場合、そのメンバの数だけ(大量に)比較関数を導出するので注意 friend auto operator<=>(const T&, const T&) = default; }; T a{}, b{}; bool less = a < b; // OK bool greater = a > b; // OK bool equal_to = a == b; // OK bool not_equal_to = a != b; // OK bool less_equal = a <= b; // OK bool greater_equal = a >= b; // OK
個別に指定できる:
#include <compare> // 必要 struct T { value_type value; value_type value1; value_type value2; value_type array[1000000]; bool operator==(const T& rhs) const { return this->value == rhs.value; } // おまじない auto operator<=>(const T& rhs) const { return this->value <=> rhs.value; } };
他にも何通りかの実装方法がある:
#include <compare> // 必要 struct T { value_type value; auto operator<=>(const T& rhs) const = default; };
#include <compare> // 必要 struct T { value_type value; friend bool operator==(const T& lhs, const T& rhs) { return lhs.value == rhs.value; } // おまじない friend auto operator<=>(const T& lhs, const T& rhs) { return lhs.value <=> rhs.value; } };
ところで、operator()を定義すると、そのインスタンスは関数を呼び出すような振る舞いができる:
struct F { void operator()(/* 引数リスト */) const { return; } }; F f{}; f(); // invokable F{}(); // インスタンス F{} に対する関数呼び出し ()
二つの引数を受け取って大小比較するoperator()も定義できる:
struct T { value_type value; friend auto operator<=>(const T&, const T&) = default; }; struct Less { bool operator()(const T& lhs, const T& rhs) const { return lhs < rhs; // T型のまま比較 } }; struct Greater { bool operator()(const T& lhs, const T& rhs) const { return lhs > rhs; // T型のまま比較 } }; T a{}, b{}; bool less = Less {}(a, b); // a < b bool greater = Greater{}(a, b); // a > b
任意の型Tのinner classとしても定義できる。
inner classなのでprivateなメンバであっても参照・比較できる:
struct T { // 説明のため未定義 // friend auto operator<=>(const T&, const T&) = default; // 下に定義したT::Less、T::Graterをもとに比較する // operator<=>で定義してしまえばinner classのアクセス制限の緩和の恩恵なんてないけれども struct Less { bool operator()(const T& lhs, const T& rhs) const { return lhs.value < rhs.value; } }; struct Greater { bool operator()(const T& lhs, const T& rhs) const { return lhs.value > rhs.value; } }; private: value_type value; }; T a{}, b{}; // bool less = a < b; operator<は未定義 // bool greater = a > b; operator>は未定義 bool less = T::Less {}(a, b); bool greater = T::Greater{}(a, b);
上記のstruct Less、struct Greaterは、よりイケてる形で標準ライブラリにある:
#include <functional> struct T { value_type value; friend auto operator<=>(const T&, const T&) = default; }; T a{}, b{}; bool less = std::less {}(a, b); // a < b bool greater = std::greater {}(a, b); // a > b bool equal_to = std::equal_to {}(a, b); // a == b bool not_equal_to = std::not_equal_to {}(a, b); // a != b bool less_equal = std::less_equal {}(a, b); // a <= b bool greater_equal = std::greater_equal{}(a, b); // a >= b
任意の型のソート
ソーティングの結果には2通りある:
- 昇順
- 降順
比較によりこの結果が決定づけられる:
a < bのとき昇順a > bのとき降順
関数sort()に引数として<や>を与えることは出来ない:
sort(data, <); // NG sort(data, >); // NG sort(data, '<'); // OK? sort(data, '>'); // OK?
インスタンスであれば、関数sort()に引数を与えられる:
std::less less{}; sort(data, less); // OK sort(data, std::greater{}); // OK
以上より、任意の型Tのソートはこのようにする:
#include <compare> struct T { using value_type = int; // お好みの型 value_type value; friend auto operator<=>(const T&, const T&) = default; }; #include <vector> #include <list> #include <set> #include <algorithm> #include <functional> int main() { // 比較関数の指定を省略すれば、operator<で比較する // すなわち、デフォルトで昇順ソート // std::array<T, N>でも同様 std::vector<T> vec = {/* 略 */}; std::sort(vec.begin(), vec.end()); // 昇順 std::sort(vec.begin(), vec.end(), std::less{}); // 昇順 std::sort(vec.begin(), vec.end(), std::greater{}); // 降順 std::sort(vec.begin(), vec.end(), [](const T& lhs, const T& rhs) { return lhs.value < rhs.value; }); // 昇順 std::sort(vec.begin(), vec.end(), [](const T& lhs, const T& rhs) { return lhs.value > rhs.value; }); // 降順 std::ranges::sort(vec); // 昇順 std::ranges::sort(vec, std::less{}); // 昇順 std::ranges::sort(vec, std::greater{}); // 降順 std::ranges::sort(vec, [](const T& lhs, const T& rhs) { return lhs.value < rhs.value; }); // 昇順 std::ranges::sort(vec, [](const T& lhs, const T& rhs) { return lhs.value > rhs.value; }); // 降順 std::ranges::sort(vec, {}, &T::value); // 昇順 std::ranges::sort(vec, std::less{}, &T::value); // 昇順 std::ranges::sort(vec, std::greater{}, &T::value); // 降順 // std::listはランダムアクセスイテレーターを満たさないため、std::ranges::sort()を使えない // メンバ関数を使う std::list<T> list = {/* 略 */}; list.sort(); // 昇順 list.sort(std::less{}); // 昇順 list.sort(std::greater{}); // 降順 list.sort([](const T& lhs, const T& rhs) { return lhs.value < rhs.value; }); // 昇順 list.sort([](const T& lhs, const T& rhs) { return lhs.value > rhs.value; }); // 降順 // std::setは常にstd::is_sorted()を満たすように、型に比較関数を指定する std::set<T> set1 = {/* 略 */}; // 昇順 std::set<T, std::less<T>> set2 = {/* 略 */}; // 昇順; ここは"<T>"が必要らしい std::set<T, std::greater<T>> set3 = {/* 略 */}; // 降順; ここは"<T>"が必要らしい }
おまけ黒魔術:
struct T { using value_type = int; value_type value; operator int() const { return this->value; } }; T a{}, b{}; bool less = a < b; // 暗黙の型変換でint型として比較
謝辞
この文書は、少なくとも以下を参照して書かれた。
