関数ポインタをどう使うか

初めて、Cで関数ポインタを勉強したとき、

「は？？何これ？どこで使うの？」って感じでした。

今日、SRMで関数ポインタを使えそうな問題を見つけました。。

個人的な見解としては、関数ポインタを使うのは、配列などのコンテナに対して一括して処理を反映させたいときだと思います。

考えてみると、関数型言語の第一級関数を使ってやっていることを思い出せば良い気がします。

map、filter、reduceなど。

まー、何はともあれ例題を見てみましょう。以下のようなことをしたいとします。

view plainprint?

1. int ck1(int a, int b) {  
2.   return a;  
3. }  
4.   
5. int ck2 (int a, int b) {  
6.   return b;  
7. }  
8.   
9. int ck3(int a, int b) {  
10.   return a<b?a:b;  
11. }  
12.   
13. int ck4(int a, int b) {  
14.   return a<b?b:a;  
15. }  
16.   
17. int main() {  
18.   vector<int>A, B, wanted;  
19.   
20.   A.push_back(1);  
21.   A.push_back(2);  
22.   A.push_back(3);  
23.   A.push_back(4);  
24.   
25.   B.push_back(4);  
26.   B.push_back(3);  
27.   B.push_back(2);  
28.   B.push_back(1);  
29.   
30.   wanted.push_back(1);  
31.   wanted.push_back(2);  
32.   wanted.push_back(2);  
33.   wanted.push_back(1);  
34.   
35.   bool ck = true;  
36.   int sz = A.size();  
37.   
38.   // func1  
39.   REP(i, sz)  
40.       if (ck1(A[i], B[i]) != wanted[i])  
41.           ck = false;  
42.   if (ck)  
43.       cout << "ck1 holds" << endl;  
44.   
45.   // func2  
46.   ck = true;  
47.   REP(i, sz)  
48.       if (ck2(A[i], B[i]) != wanted[i])  
49.           ck = false;  
50.   if (ck)  
51.       cout << "ck2 holds" << endl;  
52.   
53.   // func3  
54.   ck = true;  
55.   REP(i, sz)  
56.       if (ck3(A[i], B[i]) != wanted[i])  
57.           ck = false;  
58.   if (ck)  
59.       cout << "ck3 holds" << endl;  
60.   
61.   // func4  
62.   ck = true;  
63.   REP(i, sz)  
64.       if (ck4(A[i], B[i]) != wanted[i])  
65.           ck = false;  
66.   if (ck)  
67.       cout << "ck3 holds" << endl;  
68. }  

int ck1(int a, int b) {
  return a;
}

int ck2 (int a, int b) {
  return b;
}

int ck3(int a, int b) {
  return a<b?a:b;
}

int ck4(int a, int b) {
  return a<b?b:a;
}

int main() {
  vector<int>A, B, wanted;

  A.push_back(1);
  A.push_back(2);
  A.push_back(3);
  A.push_back(4);

  B.push_back(4);
  B.push_back(3);
  B.push_back(2);
  B.push_back(1);

  wanted.push_back(1);
  wanted.push_back(2);
  wanted.push_back(2);
  wanted.push_back(1);

  bool ck = true;
  int sz = A.size();

  // func1
  REP(i, sz)
      if (ck1(A[i], B[i]) != wanted[i])
          ck = false;
  if (ck)
      cout << "ck1 holds" << endl;

  // func2
  ck = true;
  REP(i, sz)
      if (ck2(A[i], B[i]) != wanted[i])
          ck = false;
  if (ck)
      cout << "ck2 holds" << endl;

  // func3
  ck = true;
  REP(i, sz)
      if (ck3(A[i], B[i]) != wanted[i])
          ck = false;
  if (ck)
      cout << "ck3 holds" << endl;

  // func4
  ck = true;
  REP(i, sz)
      if (ck4(A[i], B[i]) != wanted[i])
          ck = false;
  if (ck)
      cout << "ck3 holds" << endl;
}

vector A, B, wantedのすべての要素が与えられた関数に対して条件を満たしているかどうかをしらべています。でも上のソースコードは明らかに冗長です。SRMのときは時間勝負だったので上のような実装をしました（汗）

関数ポインタを使って書き直してみます。

view plainprint?

1. bool check(vector<int>A, vector<int>B, vector<int>wanted, int (*func)(int, int)) {  
2.    int sz = A.size();  
3.   
4.    REP(i, sz)  
5.        if (func(A[i], B[i]) != wanted[i])  
6.            return false;  
7.   
8.    return true;  
9. }  
10.   
11. int main() {  
12.    vector<int>A, B, wanted;  
13.   
14.    A.push_back(1);  
15.    A.push_back(2);  
16.    A.push_back(3);  
17.    A.push_back(4);  
18.   
19.    B.push_back(4);  
20.    B.push_back(3);  
21.    B.push_back(2);  
22.    B.push_back(1);  
23.   
24.    wanted.push_back(1);  
25.    wanted.push_back(2);  
26.    wanted.push_back(2);  
27.    wanted.push_back(1);  
28.   
29.    if (check(A, B, wanted, ck1))  
30.        cout << "ck1 holds" << endl;  
31.    if (check(A, B, wanted, ck2))  
32.        cout << "ck2 holds" << endl;  
33.    if (check(A, B, wanted, ck3))  
34.        cout << "ck3 holds" << endl;  
35.    if (check(A, B, wanted, ck4))  
36.        cout << "ck4 holds" << endl;  
37. }  

bool check(vector<int>A, vector<int>B, vector<int>wanted, int (*func)(int, int)) {
   int sz = A.size();

   REP(i, sz)
       if (func(A[i], B[i]) != wanted[i])
           return false;

   return true;
}

int main() {
   vector<int>A, B, wanted;

   A.push_back(1);
   A.push_back(2);
   A.push_back(3);
   A.push_back(4);

   B.push_back(4);
   B.push_back(3);
   B.push_back(2);
   B.push_back(1);

   wanted.push_back(1);
   wanted.push_back(2);
   wanted.push_back(2);
   wanted.push_back(1);

   if (check(A, B, wanted, ck1))
       cout << "ck1 holds" << endl;
   if (check(A, B, wanted, ck2))
       cout << "ck2 holds" << endl;
   if (check(A, B, wanted, ck3))
       cout << "ck3 holds" << endl;
   if (check(A, B, wanted, ck4))
       cout << "ck4 holds" << endl;
}

だいぶすっきりしました。

関数4つまわしているのがちょっとカッコ悪いので、配列にしてみます。

関数ポインタも配列に格納することができます。

view plainprint?

1. int main() {  
2.     vector<int>A, B, wanted;  
3.   
4.     A.push_back(1);  
5.     A.push_back(2);  
6.     A.push_back(3);  
7.     A.push_back(4);  
8.   
9.     B.push_back(4);  
10.     B.push_back(3);  
11.     B.push_back(2);  
12.     B.push_back(1);  
13.   
14.     wanted.push_back(1);  
15.     wanted.push_back(2);  
16.     wanted.push_back(2);  
17.     wanted.push_back(1);  
18.   
19.     int (*funcs[4])(int, int) = {ck1, ck2, ck3, ck4};  
20.     string funcName[] = {"ck1", "ck2", "ck3", "ck4"};  
21.   
22.     REP(i, SIZE(funcs)) {  
23.         if (check(A, B, wanted, funcs[i]))  
24.             cout << funcName[i] << " holds" << endl;  
25.     }  
26.   
27. }  

int main() {
    vector<int>A, B, wanted;

    A.push_back(1);
    A.push_back(2);
    A.push_back(3);
    A.push_back(4);

    B.push_back(4);
    B.push_back(3);
    B.push_back(2);
    B.push_back(1);

    wanted.push_back(1);
    wanted.push_back(2);
    wanted.push_back(2);
    wanted.push_back(1);

    int (*funcs[4])(int, int) = {ck1, ck2, ck3, ck4};
    string funcName[] = {"ck1", "ck2", "ck3", "ck4"};

    REP(i, SIZE(funcs)) {
        if (check(A, B, wanted, funcs[i]))
            cout << funcName[i] << " holds" << endl;
    }

}

おー、結構きれいになりましたね。。

アルゴリズム競技のコンテストで、実装の勉強ができるなんて思ってませんでした。恐るべしTopCoder。。