質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

5回答

3427閲覧

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

yui-chan

総合スコア18

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

1クリップ

投稿2022/01/02 22:50

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

この動画の1:16:51あたりで、

c++

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

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

例えば、引数として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にはどんな意味があるのでしょうか?

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

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

c++

1struct frac { 2 ll a, b; 3 frac(ll _a=0, ll _b=1): a(_a), b(_b) { 4 if (b == 0 ) { a = 1; return; } 5 if (b < 0 ) a = -a, b = -b; 6 ll g = gcd(abs(a),b); 7 a /= g; b /= g; 8 } 9 bool operator<(const frac& x) const { 10 return a*x.b < b*x.a; 11 } 12};

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答5

0

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でない正の整数)

イメージ説明

投稿2022/01/03 01:56

編集2022/01/03 01:58
wsb

総合スコア194

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

えーっと、今回は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< をオーバーロードしているのです。

投稿2022/01/03 02:40

BeatStar

総合スコア4958

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

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

投稿2022/01/03 02:15

yaito3014

総合スコア176

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ベストアンサー

C++

1#include <iostream> 2#include <numeric> // gcd (-std=c++17) 3using namespace std; 4typedef long long ll; 5 6struct frac { 7 ll a, b; 8 frac(ll _a=0, ll _b=1): a(_a), b(_b) { 9 if (b == 0 ) { a = 1; return; } 10 if (b < 0 ) a = -a, b = -b; 11 ll g = gcd(abs(a),b); 12 a /= g; b /= g; 13 } 14 bool operator<(const frac& x) const { 15 return a*x.b < b*x.a; 16 } 17}; 18 19int main() 20{ 21 frac p(4, 6), q(4, 5); 22 cout << "p.a = " << p.a << ", p.b = " << p.b 23 << ", q.a = " << q.a << ", q.b = " << q.b << endl; 24 if (p < q) cout << "4/6 < 4/5\n"; 25 else cout << "4/6 >= 4/5\n"; 26}

実行結果

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 より小さいかどうかを判定します。

投稿2022/01/03 01:36

kazuma-s

総合スコア8224

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

yui-chan

2022/01/03 04:03

視覚的な説明ありがとうございます!???? 一つ疑問があります。 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

2022/01/03 04:17 編集

「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 です。
guest

0

bool operator<(const frac& x) const

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

投稿2022/01/02 23:12

episteme

総合スコア16614

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

yui-chan

2022/01/02 23:42

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

2022/01/02 23:45

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

2022/01/03 00:47

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問