C++の関数オブジェクト

前から気になっていたのですが、C++にgreater<int>というものがあります。例えば、vector<int> xsを降順にソートしたい場合に

view plainprint?

1. sort(xs.begin(), xs.end(), greater<int>());  

sort(xs.begin(), xs.end(), greater<int>());

のようにして使います。また、priority_queue<int>のデータ構造でtopに最小のものがくるようにしたい場合、

view plainprint?

1. priority_queue<int, vector<int>, greater<int> >que;  

priority_queue<int, vector<int>, greater<int> >que;

のようにします。

　ここで気になることがあります。sort()の場合は、greater<int>()と括弧つきで使用して、priority_queueの場合は括弧なしで使用しています。この違いは一体・・？そもそもこれは関数なのか、関数ポインタなのか？

ということで調べてみました。

http://www.geocities.jp/ky_webid/cpp/library/015.html

　これは、関数オブジェクト（ファンクタ）と呼ばれるらしいです。operator()がオーバーロードされていてオブジェクトを通常の関数と同様の方法で呼び出し可能にする仕組みらしいです。ということでgreater<int>()は以下のように使うことができます。

view plainprint?

1. cout << greater<int>()(3,1) << endl;        // true  
2. cout << greater<int>()(1,2) << endl;        // false  
3. cout << greater<int>()(-1,-1) << endl;      // false  

cout << greater<int>()(3,1) << endl;        // true
cout << greater<int>()(1,2) << endl;        // false
cout << greater<int>()(-1,-1) << endl;      // false

または、こんなかんじ。こっちの書き方がオブジェクトを関数のように使ってるというのが分かりやすいかも。

view plainprint?

1. greater<int> g;  
2.   
3. cout << g(3,1) << endl;        // true  
4. cout << g(1,2) << endl;        // false  
5. cout << g(-1,-1) << endl;      // false  

greater<int> g;

cout << g(3,1) << endl;        // true
cout << g(1,2) << endl;        // false
cout << g(-1,-1) << endl;      // false

　でも何だかもやもやしています。これって何が嬉しいんだろう。関数ポインタと一緒じゃ。。ということでまた調べてみました。

http://d.hatena.ne.jp/pknight/20090818/1250584515#c

　関数ポインタと比べたときの関数オブジェクトの利点は以下の2つだそうです。

• コンパイラがインライン展開しやすい
• メンバ変数を持てるので状態を持った関数を作れる

　なるほど。。2つ目の利点が面白そうで、これってクロージャとかジェネレータとかがつくれるってことなんじゃ？と思って書いてみました。

　まず、クロージャ的なやつ（実行時に入力された数値によって挙動の異なる関数を生成したように見せかける）。

view plainprint?

1. template <typename T>  
2. class Closure {  
3.     T pw;  
4.   
5. public:  
6.     T operator() (T x) {  
7.         T ret = 1;  
8.         for (int i = 0; i < pw; i++)  
9.             ret *= x;  
10.   
11.         return ret;  
12.     }  
13.   
14.     Closure(T pw) {  
15.         this->pw = pw;  
16.     }  
17. };  
18.   
19. int main() {  
20.     int n, m;  
21.   
22.     cin >> n >> m;  
23.     Closure<int> f(n), g(m);  
24.   
25.     cout << f(10) << endl;           // 10^n  
26.     cout << g(10) << endl;           // 10^m  
27.   
28.     return 0;  
29. }  

template <typename T>
class Closure {
    T pw;

public:
    T operator() (T x) {
        T ret = 1;
        for (int i = 0; i < pw; i++)
            ret *= x;

        return ret;
    }

    Closure(T pw) {
        this->pw = pw;
    }
};

int main() {
    int n, m;

    cin >> n >> m;
    Closure<int> f(n), g(m);

    cout << f(10) << endl;           // 10^n
    cout << g(10) << endl;           // 10^m

    return 0;
}

　次に、ジェネレータ的なやつ（フィボナッチ数列生成器）。

view plainprint?

1. class Gen {  
2.     int a, b;  
3.   
4. public:  
5.     int operator() () {  
6.         int tmp = a;  
7.   
8.         a = b;  
9.         b += tmp;  
10.   
11.         return tmp;  
12.     }  
13.   
14.     Gen() {  
15.         a = 1;  
16.         b = 1;  
17.     }  
18. };  
19.   
20. int main() {  
21.     Gen gen;  
22.   
23.     for (int i = 0; i < 30; i++)  
24.         cout << gen() << endl;  
25.   
26.     return 0;  
27. }  

class Gen {
    int a, b;

public:
    int operator() () {
        int tmp = a;

        a = b;
        b += tmp;

        return tmp;
    }

    Gen() {
        a = 1;
        b = 1;
    }
};

int main() {
    Gen gen;

    for (int i = 0; i < 30; i++)
        cout << gen() << endl;

    return 0;
}

なんかここまでくると、関数型言語みたいなことができそうじゃなイカ！？と思ってfunction composition的なものを書いてみます。最初templateをプレースホルダーのように使って書いてみました。

view plainprint?

1. template <typename _T, typename _OuterFunction, typename _InnerFunction>  
2. class Composite {  
3. public:  
4.     _T operator() (_T __x) {  
5.         _OuterFunction __g = _OuterFunction();  
6.         _InnerFunction __f = _InnerFunction();  
7.         return __g(__f(__x));  
8.     }  
9. };  
10.   
11. template <typename _T>  
12. class dbl {  
13. public:  
14.     _T operator() (_T __x) {  
15.         return 2*__x;  
16.     }  
17. };  
18.   
19. template <typename _T>  
20. class succ {  
21. public:  
22.     _T operator() (_T __x) {  
23.         return __x + 1;  
24.     }  
25. };  
26.   
27. int main() {  
28.     Composite<int, succ<int>, dbl<int> > comp1;  
29.     Composite<int, dbl<int>, succ<int> > comp2;  
30.   
31.     cout << comp1(10) << endl;     // ((+1).(*2)) 10  
32.     cout << comp2(10) << endl;     // ((*2).(+1)) 10  
33.   
34.     return 0;  
35. }  

template <typename _T, typename _OuterFunction, typename _InnerFunction>
class Composite {
public:
    _T operator() (_T __x) {
        _OuterFunction __g = _OuterFunction();
        _InnerFunction __f = _InnerFunction();
        return __g(__f(__x));
    }
};

template <typename _T>
class dbl {
public:
    _T operator() (_T __x) {
        return 2*__x;
    }
};

template <typename _T>
class succ {
public:
    _T operator() (_T __x) {
        return __x + 1;
    }
};

int main() {
    Composite<int, succ<int>, dbl<int> > comp1;
    Composite<int, dbl<int>, succ<int> > comp2;

    cout << comp1(10) << endl;     // ((+1).(*2)) 10
    cout << comp2(10) << endl;     // ((*2).(+1)) 10

    return 0;
}

そのあと、動的に渡すような形で書けないかなーと試行錯誤して以下のようなものを書きました。

view plainprint?

1. template <typename _T, typename _OuterFunction, typename _InnerFunction>  
2. _T composite(_OuterFunction __f, _InnerFunction __g, _T __x) {  
3.     return __f(__g(__x));  
4. }  
5.   
6. template <typename _T>  
7. class dbl {  
8. public:  
9.     _T operator() (_T __x) {  
10.         return 2*__x;  
11.     }  
12. };  
13.   
14. template <typename _T>  
15. class succ {  
16. public:  
17.     _T operator() (_T __x) {  
18.         return __x + 1;  
19.     }  
20. };  
21.   
22. int main() {  
23.     cout << composite(succ<int>(), dbl<int>(), 10) << endl;    // ((+1).(*2)) 10  
24.     cout << composite(dbl<int>(), succ<int>(), 10) << endl;    // ((*2).(+1)) 10  
25.   
26.     return 0;  
27. }  

template <typename _T, typename _OuterFunction, typename _InnerFunction>
_T composite(_OuterFunction __f, _InnerFunction __g, _T __x) {
    return __f(__g(__x));
}

template <typename _T>
class dbl {
public:
    _T operator() (_T __x) {
        return 2*__x;
    }
};

template <typename _T>
class succ {
public:
    _T operator() (_T __x) {
        return __x + 1;
    }
};

int main() {
    cout << composite(succ<int>(), dbl<int>(), 10) << endl;    // ((+1).(*2)) 10
    cout << composite(dbl<int>(), succ<int>(), 10) << endl;    // ((*2).(+1)) 10

    return 0;
}

　書いた後、気付いたのですが、compositionの上のバージョンはpriority_queueと同様、下のバージョンはsort()と同様の書き方になっていました。こうやって見ると、priority_queueの場合は関数オブジェクトのクラスを、sort()の場合は関数オブジェクトのインスタンスを渡しているということに気付きます。たしかに、priority_queue<>の<>内で指定するものは"型"、sort()の引数で渡すのは実体を持った"値、または、インスタンス"であることを考えると、どっちに括弧付けないどっちに付けないのかってのは納得できます。実際にSTLのライブラリのソースを読んでみると、priority_queueの場合、第三引数で渡す_Compare（greater<int>に対応するもの）は"型"として使われていて、こういう使い方は関数ポインタだと書きづらいのかなと思いました。