Page List

Search on the blog

2011年4月26日火曜日

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

初めて、Cで関数ポインタを勉強したとき、
「は??何これ?どこで使うの?」って感じでした。

今日、SRMで関数ポインタを使えそうな問題を見つけました。。
個人的な見解としては、関数ポインタを使うのは、配列などのコンテナに対して一括して処理を反映させたいときだと思います。
考えてみると、関数型言語の第一級関数を使ってやっていることを思い出せば良い気がします。
map、filter、reduceなど。

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

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のときは時間勝負だったので上のような実装をしました(汗)

関数ポインタを使って書き直してみます。
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つまわしているのがちょっとカッコ悪いので、配列にしてみます。
関数ポインタも配列に格納することができます。
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。。

0 件のコメント:

コメントを投稿