C++の sort は、要素を並べ替えるための代表的な機能です。
数値を小さい順に並べるだけでなく、比較関数を使えば、より複雑なルールで自由にソートできます。
たとえば、
- 大きい順に並べる
- 文字列の長さ順に並べる
- 構造体の中の特定のメンバで並べる
- 複数条件で並べる
といったことが可能になります。
C++のソートをしっかり理解するうえで大切なのは、比較関数が何を意味しているのかを正しくつかむことです。
sort の基本的な考え方
sort は、並べ替えたい範囲を指定して使います。
比較関数を渡さない場合は、要素型にとっての標準的な順序で並びます。
整数なら通常は小さい順、文字列なら通常は辞書順に近い形で並びます。
つまり、比較関数を使わない sort は、まず「普通の昇順ソート」と考えておけば問題ありません。
一方で、標準の順序ではなく独自のルールで並べたいときに使うのが比較関数です。
比較関数とは何か
比較関数は、2つの値を受け取って、その2つのうちどちらを前に置くべきかを判断するためのものです。
いちばん大切な理解はこれです。
比較関数は、「左側の値を右側の値より前に置きたいなら真を返す」
この1文で、ほとんどの混乱は解消できます。
つまり比較関数は、「どちらが大きいか」を直接答えるためのものというより、並び順のルールを表現するためのものです。
昇順と降順の考え方
小さいものを前に置きたいなら昇順になります。
大きいものを前に置きたいなら降順になります。
このとき重要なのは、比較関数が「前に置くべきかどうか」を返しているということです。
そのため、昇順では「小さいなら前」、降順では「大きいなら前」という発想になります。
ここでつまずきやすいのは、比較関数を「大小比較そのもの」と誤解してしまうことです。
実際には、比較関数が表しているのは順番の優先関係です。
比較関数の意味を直感的に理解する
たとえば、ある値と別の値を比べたときに「こちらを先に並べたい」と判断したら、比較関数は真になります。
逆に、「こちらを先にする必要はない」と判断したら偽になります。
この判断をたくさんの要素に対して繰り返すことで、最終的な並び順が決まります。
つまり、比較関数は「順番を決めるためのルールブック」のようなものです。
比較関数が特に役立つ場面
比較関数が本当に便利になるのは、単純な数値の昇順以外の並び替えです。
代表的な例としては、次のようなものがあります。
- 数値を大きい順に並べたい
- 文字列を長さ順に並べたい
- 学生データを点数順に並べたい
- 商品データを価格順に並べたい
- 点数が同じなら名前順にする、といった複数条件を付けたい
こうした処理は、比較関数を使うことで自然に表現できます。
構造体やクラスのソート
比較関数が重要になる代表例が、構造体やクラスのソートです。
たとえば、名前や点数を持つ学生の一覧があるとします。
このとき、点数順に並べたいなら、「どの学生を先に置くべきか」を点数で判断する比較関数を書きます。
さらに、点数が同じ場合には名前順にする、といった細かい条件も加えられます。
このように、比較関数を使うと、データの一部分だけを見て順番を決めることができます。
複数条件で並べる考え方
実務でも学習でもとても重要なのが、複数条件のソートです。
考え方はシンプルです。
- まず最優先の条件で比較する
- その条件で差がつくなら、それで順序を決める
- 差がつかないなら、次の条件で比較する
たとえば、
- まず点数が高い順
- 点数が同じなら名前が辞書順
という場合は、最初に点数を見るべきです。
点数が違えば、それだけで順番が決まります。
点数が同じときだけ、名前を見ることになります。
このように、比較関数では条件に優先順位を持たせるのが基本です。
比較関数を書くときのコツ
比較関数を書こうとすると混乱しやすい人は、いきなり実装を考えるのではなく、まず日本語で条件を言い換えると整理しやすくなります。
たとえば、
- 年齢が小さい人を前にする
- 年齢が同じなら名前順で前にする
と文章で書けたら、その内容をそのまま順番に比較関数へ落とし込めます。
比較関数が難しく感じる原因の多くは、条件が頭の中で曖昧なままだからです。
先に日本語で「何を優先して並べたいのか」をはっきりさせると、かなりわかりやすくなります。
同じ扱いになる要素について
比較関数では、すべての要素の間に必ず明確な優先順位を付けなければならないわけではありません。
ある条件だけで並べたい場合、その条件で同じ扱いになるものは「同順位」とみなしてよいことがあります。
たとえば、数値を「1の位」でだけ並べたい場合、1の位が同じものどうしの順番までは決めないという設計も可能です。
これは誤りではありません。
その条件だけで順番を決めたいなら、それで十分です。
ただし、「同じ1の位の中でも数そのものが小さい順にしたい」など、さらに順番を細かく決めたいなら、第2条件を追加する必要があります。
ここは非常に重要です。
第2条件がないから比較関数として間違い、というわけではない
第2条件は、同順位の中まで順番を決めたいときに必要になる
この理解は、比較関数を正しく使ううえで大切です。
比較関数で守るべきルール
比較関数は、ただ適当に真偽を返せばよいわけではありません。
順番のルールとして矛盾がないことが必要です。
実用上は、次の点を意識すれば十分です。
まず、自分自身を自分より前に置くことはできないので、同じものどうしを比べたときは前に置く判定になってはいけません。
次に、ある要素を別の要素より前に置くと決めたなら、逆方向でも前に置くという判定になってはいけません。
両方が同時に前だと判定されると、順序が壊れます。
さらに、順番に一貫性が必要です。
あるものを別のものより前、その別のものをさらに別のものより前とするなら、最初のものも最後のものより前であるべきです。
要するに、比較関数は筋の通った並び順のルールでなければなりません。
よくある間違い
比較関数で特に多い間違いのひとつが、「同じ値も前に置いてよい」と考えてしまうことです。
たとえば、「小さいか同じなら前」といった感覚で条件を作ると、順序が壊れやすくなります。
比較関数では、同じもの同士は「前に置くべき」と判定しないことが基本です。
また、比較関数の条件が曖昧で、「この場合は前」「あの場合も前」と矛盾してしまうこともあります。
そうなると、ソート結果は不安定になります。
さらに、「比較関数は単に大小を比べるだけのもの」と思い込むのもよくある誤解です。
実際には、「どちらを前に置きたいか」を表現するものです。
stable_sort との違い
sort と似たものに stable_sort があります。
違いは、同じ順位とみなされた要素の元の順番を保つかどうかです。
通常の sort では、比較関数から見て同順位の要素の相対順は保証されません。
一方で stable_sort では、その元の順番が保たれます。
たとえば、点数だけで学生を並べるとき、同じ点数の学生が複数いる場合、通常の sort ではその同点グループの順番は変わる可能性があります。
stable_sort なら、元々並んでいた順番を保ったまま並べ替えられます。
同順位の順番まで意味を持たせたい場面では、stable_sort が役立ちます。
operator< との関係
比較関数を毎回用意しなくても、その型に標準的な並び順を定義しておく方法もあります。
それが operator< を定義する考え方です。
これは、「この型は通常こういう順序で並ぶ」という基準を型そのものに持たせる方法です。
そのため、ある型に対して自然な並び順が1つ決まっているなら便利です。
ただし、実際には用途ごとに並び順を変えたいことが多くあります。
その場合は、外部の比較関数やラムダ式で都度ルールを与えるほうが柔軟です。
つまり、
- その型の基本的な順序を定義したいなら
operator< - 場面ごとに並べ方を変えたいなら比較関数
という使い分けになります。
比較関数で参照や const が使われる理由
比較関数では、特に大きなデータ型を扱うとき、値そのものをコピーするより参照で受け取るのが普通です。
これは無駄なコピーを避けるためです。
また、比較はあくまで順番を判断するだけなので、比較対象を書き換えるべきではありません。
そのため、変更しないことを明示する形で扱うのが自然です。
この考え方は、構造体や文字列などを比較するときに特に重要です。
比較関数を覚えるコツ
比較関数は最初かなり混乱しやすいですが、次の一文だけ覚えると整理しやすくなります。
左の値を右の値より前に置きたいなら真
この理解があると、
- 昇順は「小さいものを前にする」
- 降順は「大きいものを前にする」
- 複数条件は「まず優先条件で前後を決める」
という発想に自然につながります。
比較関数は難しい特殊な機能というより、並び順を言葉で決めて、それをルール化する仕組みと考えると理解しやすくなります。
まとめ
C++の sort における比較関数は、独自の並び替えルールを作るための仕組みです。
重要なのは、「比較関数は大小そのものではなく、どちらを前に置くかを返す」という点です。
理解のポイントを整理すると、次のようになります。
- 比較関数は、「左の要素を右の要素より前に置くなら真」を返します。
- 昇順なら小さいものを前に置き、降順なら大きいものを前に置きます。
- 複数条件のソートでは、優先順位の高い条件から順に比較します。
- 同順位の中まで順番を決めたいときだけ、第2条件や第3条件を追加します。
- 同順位の元の順番を保ちたいなら
stable_sortを使います。 - そして、比較関数には順序として矛盾がないことが求められます。
この考え方が身につくと、C++のソートはかなり自在に使えるようになります。
以上、C++の比較関数を使ったsortについてでした。
最後までお読みいただき、ありがとうございました。
