C++マニアック

このページでは STL のアルゴリズムである sort の使い方について解説します。

1. 基本的な使い方
2. 並べ替えの判断基準を変更する
3. 大小関係の比較について
4. プレディケートのバラエティ
5. 英文字文書を読んで、文字数の頻度順にソートする例
6. 身長や体重など複数の基準でソートする例
7. よりスマートなコーディング
8. アルゴリズム関連本

基本的な使い方 ページの先頭へ

sort は、いわゆる並べ替えを行うアルゴリズムです。並べ替えることが出来るのは、通常の配列や、vector などのランダムアクセスイテレータが使えるコンテナの中身と言うことになります。list などは、ランダムアクセスできないので、sort ではソートできませんが、list にはそれ自体に list::sort という関数が用意されています。

さて、sort を使う最も簡単な例は、int 型の配列をソートする、次のようなものでしょう。

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    int aiTable[5] = { 3, 2, 6, -2, 2 };    // 配列を用意する。
    sort(aiTable, aiTable + 5);             // ソートする。
    {for (int iIndex = 0; iIndex < 5; iIndex++) {
        cout << aiTable[iIndex] << ", ";    // 結果をプリントしてみる。
    }}
    return 0;
}

STL の sort はインプレイス(＝その場で)ソートが行われるので、元の配列の中身が並べ変わることになります。上記を実行すると、結果は、次のようになります。昇順にソートされるわけですね。

-2, 2, 2, 3, 6,

逆順にソートしたいという場合もあります。そのような場合には、sort の第 3 引数にプレディケート(＝pred、predicate)を指定する必要があります。プレディケートとは、「判断を行うもの」というような意味ですが、sort での判断基準とは、コンテナの要素の大小関係の判断を行う基準と言うことになります。実は、デフォルトでは sort のプレディケートは「より小さい」を表す演算子 < が使われたのと同じ動作になります。< と同じ動作をする less という名前のプレディケートも STL の <functional> ヘッダには用意されています。その逆の判断基準である greater も定義されています。逆順にソートするには、この greater を使います。

#include <algorithm>
#include <functional>
#include <iostream>
using namespace std;

int main() {
    int aiTable[5] = { 3, 2, 6, -2, 2 };            // 配列を用意する。
    sort(aiTable, aiTable + 5, greater<int>());  // プレディケート greater で逆順にソートする。
    {for (int iIndex = 0; iIndex < 5; iIndex++) {
        cout << aiTable[iIndex] << ", ";            // 結果をプリントしてみる。
    }}
    return 0;
}

プレディケートとして greater のオブジェクトを渡すためにコンストラクタを呼び出す必要があるので greater の後ろに () が必要です。また、greater はテンプレートクラスなので、比較するオブジェクトの変数型を決めるテンプレート引数を <> の中に書いて与える必要があります。上記を実行すると、結果は次のようになります。

6, 3, 2, 2, -2,

並べ替えの判断基準(＝プレディケート)を変更する ページの先頭へ

sort での並べ替えの判断基準を変更するには、「基本的な使い方」で greater を使ったようにプレディケートを使います。独自の並べ替えを行うには、独自のプレディケートを定義して sort の第 3 引数に渡せばよいわけです。そこで、プレディケートとは何か?、ということになりますが、これは、作る立場から見れば、端的には比較演算子の機能を持ったクラスオブジェクト(＝関数オブジェクト)と考えて問題ありません。

例えば、int 型を比較する演算子 < について考えてみると、これは < の左右にある int 型の引数を比較して bool 型の結果を返す関数と考えることができます。これと同じ機能を持つクラス LessInt を記述して見ましょう。これは、int 用の < の機能を実現するプレディケートなわけですね。

class LessInt {
public:
    bool operator()(const int& riLeft, const int& riRight) const {
        return riLeft < riRight; // ここでは、元の < の意味に合わせてあるが、異なる判断も可能。
    }
};

上記プレディケート LessInt の使い方は、ほぼ次のようになります。

    sort(aiTable, aiTable + 5, LessInt());

簡単ですね。

上記 LessInt を参考にすれば、int 型の比較だけでなく、どのような型の引数を比較することも可能であるし、その判断基準もプログラミングしだいで「何でもありなのだ」ということが分かるでしょうか。

ただし、次のセクションで解説する制限があります。

大小関係の比較について ページの先頭へ

sort で使うプレディケートを作成する上で、知っておくべきことは、プレディケートは「より小さい」ということを表すようにしなければならないということです。「A < B」は、「A は B よりも小さい」ということを表しますが、このような意味を持つプレディケートを sort に渡すということは、sort は同値であることをどのように判断するのでしょうか。答えは、A と B が同じであるという判断は、!(A < B) && !(B < A) で行われます。従って、プレディケートは、比較している要素同士が同値である場合には false を返すようにする必要があります。

上記のようにプレディケートに「より小さい」という意味をコーディングすることにより、その意味で「昇順」にソートが行われることになります。

逆に「降順」にソートしたければ、プレディケートに「より大きい」という意味をコーディングすれば良いわけで、less の代わりに greater を使う等ということで実現可能というわけです。自作のプレディケートの場合も推して知るべしなわけです。

プレディケートのバラエティ ページの先頭へ

上では、プレディケートは端的にはクラスオブジェクトであるという限定的な書き方をしましたが、本当はプレディケートは基本的には < 演算子と同様の機能を果たすものならば何でも良いので、バラエティとしては次のような実装方法が考えられます。

1. < という名前の演算子をグローバル領域に定義する。
   bool operator<(const CElement& relementLeft, const CElement& relementRight) { ... }
2. < 以外の名前の関数をグローバル領域に定義する。
   bool LessElement(const CElement& relementLeft, const CElement& relementRight) { ... }
3. 関数オブジェクトをクラスとして定義する。
   struct LessElement { bool operator()(const CElement& relementLeft, const CElement& relementRight) { ... } };
4. クラスのメンバ関数として < という名前の演算子を定義する。
   struct SomeClass { bool operator<(const SomeClass& rsome) { ... } };

いつものように、同じことを実現するための方法は、一つではない、ということですね。

英文字文書を読んで、文字数の頻度順にソートする例 ページの先頭へ

ここではより具体的に sort を使用して、表題のように英文字列(012...89abc...xyzABC...XYZ など)で構成されたファイルを読み込んで、含まれる文字の頻度(個数)を数えて、頻度順にソートして出力するプログラムを考えてみましょう。ソートを行うには、文字の値とその数をセットにしたデータ構造(CCodeCount)を用意し、その配列(acodecount)を作成します。後は、データ構造中の空白(0x20)からチルダの次(0x7f)を範囲としてソートするだけです。ソート時に大小関係の演算子としては CCodeCount に実装した < 演算子が使われる、というストーリーです。

#pragma warning(disable: 4786)
#include <cstdio>
#include <algorithm>
using namespace std;

class CCodeCount {
private:
    int m_iCode;    // 文字コード
    int m_iCount;   // その数
public:
    CCodeCount(int iCode = 0) { Set(iCode, 0); }
    void Set(int iCode, int iCount = 0) {
        m_iCode  = iCode;
        m_iCount = iCount;
    }
    void operator++(int) { m_iCount++; }            // カウントアップ用後置き ++ 演算子
    bool operator <(const CCodeCount& rcharcount) { // 大小比較用 less 演算子
        return m_iCount < rcharcount.m_iCount;
    }
    int GetiCode () { return m_iCode ; }
    int GetiCount() { return m_iCount; }
};

int main(int argc, char* argv[]) {
    argc--, argv++;
    if (argc == 0) { return 0; }
    FILE* pfile = fopen(argv[0], "r");
    if (pfile == 0) { return 0; }
    CCodeCount acodecount[256];
    {for (int iCode = 0; iCode < 256; iCode++) {
        acodecount[iCode].Set(iCode);
    }}
    {for (int iCode = 0; (iCode = fgetc(pfile)) != EOF; ) {
        printf("%c", char(iCode));
        acodecount[char(iCode)]++;
    }}
    sort(&acodecount[0x20], &acodecount[0x7f]); // 空白(0x20)〜チルダの次(0x7f)を範囲としてソートする。
    {for (int iIndex = 0x20; iIndex < 0x7f; iIndex++) {
        printf("%d, %c\n", acodecount[iIndex].GetiCount, char(acodecount[iIndex].GetiCode()));
    }}
    return 0;
}

身長や体重など複数の基準でソートする例 ページの先頭へ

大小関係の判断基準が一つしか無い場合には、上記のようにプレディケートを作成しないで、データ構造そのものに大小関係を決定する < 演算子を定義してしまうのが簡単でよいでしょう。しかし、もし、例えば、一つのクラスに所属する生徒の身長と体重でそれぞれソートするというような場合には、次のように身長用と体重用のプレディケートを定義し、使い分ければよいというわけです。

#pragma warning(disable: 4786)
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

struct CHeightWeight {
    string m_strName;
    double m_dHeight;
    double m_dWeight;
};

bool LessHeight(const CHeightWeight& rLeft, const CHeightWeight& rRight) { return rLeft.m_dHeight < rRight.m_dHeight; }
bool LessWeight(const CHeightWeight& rLeft, const CHeightWeight& rRight) { return rLeft.m_dWeight < rRight.m_dWeight; }

int main(int argc, char* argv[]) {
    vector<CHeightWeight> vheightweight;
    // ここで vecheightweight にデータを追加する。
    sort(vheightweight.begin(), vheightweight.end(), LessHeight);       // 身長でソートする。
    sort(vheightweight.begin(), vheightweight.end(), LessWeight);       // 体重でソートする。
    return 0;
}

プレディケートがグローバル関数じゃヤダという人は、クラス(または構造体)を使って、次のようにすれば良いでしょう。

struct LessHeight { bool operator()(const CHeightWeight& rLeft, const CHeightWeight& rRight) const { return rLeft.m_dHeight < rRight.m_dHeight; } };  // 構造体で実装した。
struct LessWeight { bool operator()(const CHeightWeight& rLeft, const CHeightWeight& rRight) const { return rLeft.m_dWeight < rRight.m_dWeight; } };  // 構造体で実装した。

int main(int argc, char* argv[]) {
    vector<CHeightWeight> vheightweight;
    // ここで vecheightweight にデータを追加する。
    sort(vheightweight.begin(), vheightweight.end(), LessHeight());     // 身長でソートする。
    sort(vheightweight.begin(), vheightweight.end(), LessWeight());     // 体重でソートする。
    return 0;
}

この場合、プレディケートは構造体なので、上記のように sort にはコンストラクタを渡すことになりますね。

よりスマートなコーディング ページの先頭へ

上記の例ではプレディケートをクラス CHeightWeight の外側で定義しましたが、クラスの一貫性という意味では、CHeightWeight で使用するプレディケートは CHeightWeight の中で定義出来ればよりスマートでしょう。

というわけで、次のようにクラスの static なメンバ関数としてプレディケートを定義すると、上記目的が達成されます。

struct CHeightWeight {
    string m_strName;
    double m_dHeight;
    double m_dWeight;
    static bool LessHeight(const CHeightWeight& rLeft, const CHeightWeight& rRight) { return rLeft.m_dHeight < rRight.m_dHeight; }
    static bool LessWeight(const CHeightWeight& rLeft, const CHeightWeight& rRight) { return rLeft.m_dWeight < rRight.m_dWeight; }
};

int main(int argc, char* argv[]) {
    vector<CHeightWeight> vheightweight;
    // ここで vecheightweight にデータを追加する。
    sort(vheightweight.begin(), vheightweight.end(), CHeightWeight::LessHeight);       // 身長でソートする。
    sort(vheightweight.begin(), vheightweight.end(), CHeightWeight::LessWeight);       // 体重でソートする。
    return 0;
}

ナオ ： このページのサンプルコードは、ちょっと長すぎませんか?
店主 ： うん、そうだね。分かりにくかったかな。ちょっと反省。