自分で定義した構造体data_tをvectorにつっこみ、STLのsort()関数でソートすることを考える。以下のように書いてコンパイルを試みると、読解不能な大量のエラーメッセージとともにコンパイルが失敗する。
#include <iostream> #include <string> #include <vector> using namespace std; struct data_t { int num; string str; } ; int main(){ vector<data_t> data_array(3); data_array[0].num = 15; data_array[0].str = "zzz"; data_array[1].num = 30; data_array[1].str = "aaa"; data_array[2].num = 15; data_array[2].str = "ccc"; sort(data_array.begin(), data_array.end()); return 0; }
コンパイルできない原因は、構造体data_tの順序付けの定義をプログラマが指定していないことである。以下では、構造体を
- 数字numが小さい順にソート
- もし数字numが同じなら、文字列strが若い順にソート
することを目標に、4種類のソート方法を順に見ていく。
方法1: 構造体内で比較演算子を定義する方法
以下のように、構造体内で<演算子を定義する。
struct data_t { int num; string str; // 最後のconstを忘れると"instantiated from here"というエラーが出てコンパイルできないので注意 bool operator<( const data_t& right ) const { return num == right.num ? str < right.str : num < right.num; } };
この定義があれば、以下のようにsort()関数が使える。
sort(data_array.begin(), data_array.end());
ソートの定義が一通りしかない場合はこの方法で用が足りる。
コードの全文はこちら。
方法2: 比較関数を定義する方法
構造体data_tの順序を、比較関数を使って定義する。
// 比較関数を定義 bool asc( const data_t& left, const data_t& right ) { return left.num == right.num ? left.str < right.str : left.num < right.num; }
ソートの第三引数に比較関数を追加する。
sort(data_array.begin(), data_array.end(), asc);
時と場合により構造体data_tのソートの定義を変える必要があるときに使える方法である。コードの全文はこちら。
2020/12/28追記:C++11以降の場合、関数ascの部分はラムダ関数に置き換えることが可能。具体例は以下。
// 並び替えの方法をラムダ関数で記述 sort(data_array.begin(), data_array.end(), [](const data_t& a, const data_t& b){return (a.num == b.num) ? (a.str < b.str) : (a.num < b.num);} );
詳しくは C++11のラムダ関数の簡単なまとめ - minus9d's diary を参照。
方法3: 関数オブジェクトを定義する方法
これもやってることは方法2とほとんど同じ。
// 関数オブジェクトを定義 class MY_LESS_DEFINITION{ public: bool operator() (const data_t& left, const data_t& right) const { return left.num == right.num ? left.str < right.str : left.num < right.num; } };
ソートは以下。比較関数と違って括弧が必要
sort(data_array.begin(), data_array.end(), MY_LESS_DEFINITION());
方法3に比べてタイプ数が多いので、方法2の方が簡単?
コードの全文はこちら。
方法4: 比較演算子をグローバル領域でオーバーロードする方法
比較演算子を、構造体の外のグローバル領域でオーバーロードする。
bool operator<( const data_t& left, const data_t& right ) { return left.num == right.num ? left.str < right.str : left.num < right.num; }
ソートするときには第三引数はいらない。
sort(data_array.begin(), data_array.end());
個人的には方法4を使うくらいなら方法1の方が良いのではないかと思う。
コードの全文はこちら。
おまけ: そもそも構造体を定義せずに済ます方法
もし構造体のメンバ変数の数が2個で固定で、かつソートの方法が単純に「1つ目のメンバの値でソート」→「1つ目のメンバの値が同じなら2つ目のメンバの値でソート」という単純なものであるならば、構造体を使わずにSTLのpair()で済ます方法がある。pair()では比較演算子が定義されているので、自分で比較演算子を定義する必要がない。
もちろん構造体を使う場合に比べて拡張性は明らかによくないが、タイプ数が少なく簡単に書ける。プログラミングコンテストではよく見る方法である。要素が3個以上にしたい場合も、例えば
pair<int, pair<string, char>>
などと書けば実現できるがおすすめできない。
コードの全文はこちら。