読者です 読者をやめる 読者になる 読者になる

C++で構造体をソートする4つの方法(おまけあり)


このエントリーをはてなブックマークに追加

自分で定義した構造体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のソートの定義を変える必要があるときに使える方法である。

(2015/03/08追記:C++11の場合、関数ascの部分をラムダ関数に置き換えることが可能です。詳しくは[C++11のラムダ関数の簡単なまとめ - minus9d's diary](http://minus9d.hatenablog.com/entry/2015/03/08/232143))

コードの全文はこちら


方法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>>

などと書けば実現できるがおすすめできない。

コードの全文はこちら