setの型を自作の構造体で定義するときのoperator<の表す意味を教えて下さい！

Question

【AtCoder】ABC226のD問題の公式解説をYoutubeでみました。そこで解説されてるかたが書かれたコードで意味がわからないのがあったので質問させていただきます！

この動画の１：１６：５１あたりで、

bool operator<(const frac& x) const {
    return a * x.b < x.a * b
}

という部分があると思うんですけど、これが何を表しているのかちょっとよくわからないです????

例えば、引数としてfrac(4,6)を入れたとすると、gcd(4, 6) = 2なので、a=4, b=6, x.a = 2, x.b = 3となり、operator<関数が返すのは return 4 * 3 < 2 * 6 となってfalseとなるのでしょうか？だとしたらそのfalseにはどんな意味があるのでしょうか？

どなたかこのコードに対するわかりやすい解説をよろしくおねがいします????

###解説に使われていたコード（構造体の部分）↓

struct frac {
    ll a, b;
    frac(ll _a=0, ll _b=1): a(_a), b(_b) {
        if (b == 0 ) { a = 1; return; }
        if (b < 0 ) a = -a, b = -b;
        ll g = gcd(abs(a),b);
        a /= g; b /= g;
    }
    bool operator<(const frac& x) const {
        return a*x.b < b*x.a;
    }
};

Answer 1

bool operator<(x rhs)では、演算子のオーバーロードをしています。今回は、自作クラスfracにoperator<が定義されていないので、frac同士の大小を比較するには、そのために演算子を用意しないといけません。（オーバーロードについて詳しくは調べてみてください。）

---

operator<に期待する挙動は、下のようでしょうか。（普通の分数同士の比較演算ですね。）

frac( 1, 3) < frac( 2, 3)    // true
frac( 2, 3) < frac( 2, 3)    // false
frac( 3, 3) < frac( 2, 3)    // false
frac(-2, 3) < frac(-1, 3)    // true

質問のソースコードのoperator<の定義は下の数式に従ったものです。（分母のb_1, b_2は0でない正の整数）

Answer 2

えーっと、今回はSetを作りたいのではなく、std::setとしての型( std::set<frac> )としてやりたいんですよね? (最初、frac構造体を frac fracs; のように使うのかなと思った…)

まず、今回の質問をやる前にstd::setとはなんぞやということを学びましょう。

cppreferenceには、

std::set is an associative container that contains a sorted set of unique objects of type Key.

とあります。

手を動かしてさくさく理解する
C++ 順序付集合 std::set 入門には

C++ の std::set とは順序付けされたデータを複数保持することができる順序付集合のコンテナクラスだぞ。

データを順不同に順序付集合に追加すると、その値をキーにし自動的にソートして内部に格納してくれるぞ。
つまり、要素が常にソートされた状態の配列のようなものだ。

とあります。

まず、単純に「ソート済み」とは何でしょうか? そう、{ 3, 4, 1, 0, 9 } となっているものを
{ 0, 1, 3, 4, 9 } (降順でもいいけど)になっている状態ですよね。

では、このソート対象が 人名だったり、英語・スペイン語・フランス語・中国語…といろんな外国語の単語だったりした場合、どうでしょうか?

人名の場合は大体はアルファベット順またはあいうえお順ですが、もしかしたら年齢順かもしれません。もしかしたら好きな人ランキングかもしれません。場合によりますよね。

外国語の単語の場合だと、欧米系の言語 -> アジア系の言語 ... のようにある基準があるのかもしれません。仮にそうだとしても「どっちが上とかねーーーよ!!!」と言う人もいます。

では、ソート対象が構造体みたいに複数のデータで構成されているやつでやる場合どうでしょうか?
たとえば { 学籍番号, 名前, 学年, 性別, ... } とかで構成されているPerson構造体をソートするとか。場合によっては学籍番号でソートしたいですし、場合によっては名前でソートしたいです。

さらに人名の場合でも漢字ではどうでしょうか?

……と考えていくと、単にソートするだけでも面倒な定義が必要なはずです。

整数同士であればよっぽど特殊な条件(大富豪のAはKより強いとか)が付かない限り、そのまま比較すればいいだけですよね。でもそれ以外(構造体や文字列)だと比較する条件が曖昧になります。

そのため、「これとこれを比較した場合、必ずこれを先にする」というような定義が必要です。

std::setでは追加時とかに「ソート済みになるように位置を計算して格納」しているはずです。
そのため、「比較時の定義」をする必要があります。

よって、std::setを使う場合は、templateで束縛する型は < で比較できるようにしておけ…という前提があるのです。それを実装さえしてしまえば使えるってことです。

fracという名前から恐らく 3/4 とかみたいな分数として使いたいのだと思います。(問題文は読んでいません)

そのためにoperator< をオーバーロードしているのです。

Answer 3

まず std::set というのは要素同士の大小関係を利用することで効率的な操作を行うためのコンテナです。
特に指定されなければ二つの要素 x, y について x < y の結果が利用されるため、要素にする型について x < y のような式が有効である必要があります。
ここで、 x < y のような式が有効であるためには x.operator<(y) または operator<(x, y) のような式が有効である必要があるので、分数を表す frac にメンバ関数として operator< を定義することで x < y のような比較ができ、 std::set の要素にすることができます。

Answer 4

#include <iostream>
#include <numeric>   // gcd (-std=c++17)
using namespace std;
typedef long long ll;

struct frac {
    ll a, b;
    frac(ll _a=0, ll _b=1): a(_a), b(_b) {
        if (b == 0 ) { a = 1; return; }
        if (b < 0 ) a = -a, b = -b;
        ll g = gcd(abs(a),b);
        a /= g; b /= g;
    }
    bool operator<(const frac& x) const {
        return a*x.b < b*x.a;
    }
};

int main()
{
	frac p(4, 6), q(4, 5);
	cout << "p.a = " << p.a << ", p.b = " << p.b
	     << ",  q.a = " << q.a << ", q.b = " << q.b << endl;
	if (p < q) cout << "4/6 < 4/5\n";
	else cout << "4/6 >= 4/5\n";
}

実行結果

p.a = 2, p.b = 3,  q.a = 4, q.b = 5
4/6 < 4/5

2/3 が 4/5 より小さいことは、25 < 34 で判定します。

operator<(const frac& x) は、2つの frac の比較で、
frac自身が右辺の frac x より小さいかどうかを判定します。

Comments

[yui-chan]

視覚的な説明ありがとうございます！????

一つ疑問があります。
a*x.b < b*x.aを変形すると、(a/b) < (x.a/x.b)となることがわかったのですが、
それぞれ右側の(a/b)と左側の(x.a/x.b)はどう違うんですかね。。

今の所、
a,bが新しく追加するデータで、x.a, x.bが既存のデータの象徴で、setに追加するときにoperator<関数が呼び出されながら新しく追加されるa, bが順序的に良いところに配置されるのかなぁ、と思いました????

しつこくて申し訳ないですが回答お願いいたします！！????‍♀️

[kazuma-s]

「p < q」は「p.operator<(q)」に読み替えられて、frac のメンバ関数 operator< が呼び出されます。
その関数の中で、p は *this、q は x です。
a*x.b < b*x.a は、p.a*q.b < p.b*q.a です。

Answer 5

bool operator<(const frac& x) const

「*this < x なら trueを返す」それだけです。
fracどうしの比較演算ですね、これがないとsetの要素になれませんから。

Comments

[yui-chan]

回答ありがとうございます！

「*this < x なら trueを返す」という条件はコードにどこにも書かれていないように思えますけども、どこのことを指しておっしゃっているのでしょうか？

[episteme]

set内の要素は大小関係に基づいて(内部的に)配置されます。
「大小関係の定義できないものはsetの要素になれない」がsetのもつ条件です。

[episteme]

// *this < x なら trueを返す
bool operator<(const frac& x) const {
return a*x.b < b*x.a;
}