ストラウストラップのプログラミング入門(36) 21章「アルゴリズムとマップ」21.4まで

C++

『ストラウストラップのプログラミング入門』を読む。200時間ほどユクモ村に出張していて前回から間があきました。

今日は21章の21.4まで。この章では、関数オブジェクトが登場します。

（p.676）21.2「最も単純なアルゴリズム：find()」

21.2では、標準ライブラリのfind関数を例に挙げて、その汎用性と柔軟性が語られます。

find関数は、

  • STLスタイルのあらゆるシーケンス
  • あらゆる要素型

…の2つに対して使用できるという点で、汎用的です。

（p.678）21.2 TRY THIS

21.2の「TRY THIS」は、次の2つのコードが同等であることを論理的に説明せよという内容です。

template<class In, class T>
In find(In first, In last, const T& val)
    // [first,last)の範囲内でvalに等しい最初の要素を検索する
{
    while (first != last && *first != val) ++first;
    return first;
}

template<class In, class T>
In find1(In first, In last, const T& val)
    // [first,last)の範囲内でvalに等しい最初の要素を検索する
{
    for(In p = first; p != last; ++p){
        if(*p == val) return p;
    }
    return last;
}

というわけで、ちょっと考えてみましょう。

それぞれのコードで、ループの前に"不変な表明"があると考えることができます。

template<class In, class T>
In find(In first, In last, const T& val)
    // [first,last)の範囲内でvalに等しい最初の要素を検索する
{
    // 不変な表明: 調査中のポインタはfirst
    while (first != last && *first != val) ++first;
    return first; // ☆★
}

template<class In, class T>
In find1(In first, In last, const T& val)
    // [first,last)の範囲内でvalに等しい最初の要素を検索する
{
    // 不変な表明: 調査中のポインタはp
    for(In p = first; p != last; ++p){
        if(*p == val) return p;  // ☆★
    }
    return last;
}
valが見つかったとき
valを指したポインタ（while文のコードではfirst、for文のコードではp）が、それぞれのコードの☆の箇所から、呼び出し元へ返されます。
valが見つからなかったとき
lastのポインタ（while文のコードではlastの位置までインクリメントされたfirst、for文のコードではlastそのもの）が、それぞれのコードの★の箇所から、呼び出し元へ返されます。

論理的な説明かどうか自信がないですが、これで両者は同等ですねと言いたいです……ダメ？ ;)

# 「不変な表明」については、c.f.『Accelerated C++』2章 ですね。

（p.679）21.3「一般的な検索：find_if()」

続いて、find_if関数が紹介されます。

find_if関数では、引数を1つだけ取る述語（＝真偽を返す関数）を第三引数に渡して、検索条件にすることができます。ここでの引数とは、find_ifを適用するシーケンス内の要素と比較可能な型の値です。

しかし、比較方法が一様でないときは、「引数を1つだけ取る述語」をいくつも定義しなければならないのでしょうか。

この問題を解決するために、関数オブジェクトが登場します。

（p.681）21.4「関数オブジェクト」

関数オブジェクトは、基本的には次のように作ります。

  • クラスを定義する
  • コンストラクタの引数に渡した値を、クラスの状態に設定する
    • 引数の数は1つでも複数でもよい
  • operator(S x)を定義する
    • Sは述語の適用対象であるシーケンスの値の型

このほかに、オブジェクトの外に状態を公開したり、外から状態をリセットしたりする関数を定義することもあります。

本文には、「小さく単純な（たとえば数値同士の比較などの）」関数オブジェクトは、関数呼び出しよりもパフォーマンス的に優れているそうです。十分な型情報があると、最適化したコードをコンパイラが生成しやすい、と書かれていました。なるほど（といってもこのあたりの詳しい話はまだよく知らない）。

分からなかったこと（未解決）

本文では、上の続きでsort関数が紹介されます。sort関数は、デフォルトで演算子<を使って値同士を比較しますが、ほかの条件を使いたい場合に、第三引数に判定用の関数を渡すことができます。

関数呼出しでは引数を渡せない → 渡せるように関数オブジェクトを使おう、という話の流れだったのに、判定関数には引数を渡さずに使っています。どうして! この点が腑に落ちなくて悩みました。

疑問の箇所

具体的にはこんな感じです。これは、21.4.2（p.p.683-684）のコードを元に改変したものです。

struct Record {
    string name;
    char addr[24];
};

struct Cmp_by_name {
    bool operator()(const Record& a, const Record& b) const
    {
		return a.name < b.name;
	}
};

int main()
{
    vector<Record> vr;
    Record r1;
    r1.name = "cat_hoge";
    r1.addr[0] = 'h';
    r1.addr[1] = 'o';
    r1.addr[2] = 'g';
    r1.addr[3] = 'e';
    Record r2;
    r2.name = "ant_moga";
    r2.addr[0] = 'm';
    r2.addr[1] = 'o';
    r2.addr[2] = 'g';
    r2.addr[3] = 'a';
    Record r3;
    r3.name = "dog_piyo";
    r3.addr[0] = 'p';
    r3.addr[1] = 'i';
    r3.addr[2] = 'y';
    r3.addr[3] = 'o';
    vr.push_back(r1);
    vr.push_back(r2);
    vr.push_back(r3);

    sort(vr.begin(), vr.end(), Cmp_by_name());    // ☆
    
    // 結果の確認
    for(vector<Record>::iterator p = vr.begin(); p < vr.end(); ++p){
        Record r = *p;
        cout << r.name << endl;
        /*
            出力: 
            recant_moga
            reccat_hoge
            recdog_piyo
        */
    }
}

☆の箇所ではCmp_by_nameのコンストラクタを呼び出しています。引数はありません。

本文の流れから、関数オブジェクトを使うモチベーションはコンストラクタ引数を使えることなのかと思っていたのですが、そうでもないようです。次の2つの疑問を持ちました。

  • 疑問1: Cmp_by_nameに状態をセットしなくてよいのか？
  • 疑問2: sort関数内でのoperator()呼出しはどうなっているのか？
sort関数の中身？

どうやら分からないのはsort関数の動きのようなので、実装を見てみます。手元のalgorithm.hを見ると、「TEMPLATE FUNCTION sort WITH PRED」というコメントがついた関数がありました。

		// TEMPLATE FUNCTION sort WITH PRED
template<class _BidIt,
	class _Pr,
	class _Ty> inline
	void _Insertion_sort1(_BidIt _First, _BidIt _Last, _Pr _Pred, _Ty *)
	{	// insertion sort [_First, _Last), using _Pred
	if (_First != _Last)
		for (_BidIt _Next = _First; ++_Next != _Last; )
			{	// order next element
			_BidIt _Next1 = _Next;
			_Ty _Val = _Move(*_Next);

			if (_DEBUG_LT_PRED(_Pred, _Val, *_First))
				{	// found new earliest element, move to front
				_Move_backward(_First, _Next, ++_Next1);
				*_First = _Move(_Val);
				}
			else
				{	// look for insertion point after first
				for (_BidIt _First1 = _Next1;
					_DEBUG_LT_PRED(_Pred, _Val, *--_First1);
					_Next1 = _First1)
					*_Next1 = _Move(*_First1);	// move hole down
				*_Next1 = _Move(_Val);	// insert element in hole
				}
			}
	}

これは……。あまり長時間眺めたくない感じですが……。主にこのあたりが分かりません。

  • Cmp_by_nameのoperator()が呼び出されるのは結局どこ？
  • _Tyって何？
  • _Move_backwardのあたりで何をやっているのか（シーケンス内のポイントする位置を指定の箇所まで遡ってる？）

うぅ。

もらったヒント

というわけで、ここまでについて身内に話してみたところ、次のようなヒントを頂きました。

  • （疑問1に対して）Comparator（=判定関数、サンプルコードではCmp_by_name）の内部で状態を持ったり、外から状態を参照させたりはしないのが定石

sort関数は、実行中にその場でデータ構造の順番を入れ替えます。そのような時にComparatorに状態を持たせると、色々と厄介なため、
Cmp_by_nameがメンバ変数を持たず、したがって値をセットするためのコンストラクタ引数がないのは、振る舞いとして妥当だそうです。

  • （疑問2に対して）algorithm.hのsort関数では、さまざまなソートアルゴリズムの共通部分のみを抽象化してあると思われるため、Predを呼び出している具体的な箇所を特定するのは困難。

Cmp_by_nameのoperator()が呼び出される場所は、もう少し具体的な振る舞いを持つ関数を眺める必要があるようです。（ホント？？）

どうもモヤモヤしますが、敗北してひとまず先に進むことにします。21章の続きは次回です。