2010年1月22日金曜日

C++0x: 構造体を格納したSTLコンテナに対してソート・探索・削除などのアルゴリズムを適用する

このブログ記事をはてなブックマークに追加

先日、構造体を格納したコンテナに対してSTLのアルゴリズムを適用する方法について記したが、今回はそれをC++0xで書き直してみた。C++0xの規格はまだきちんと定まっていないが、草案ではかなりのところまでつめられてきており、また対応するC++コンパイラも出てきていることから今のうちにC++0xに慣れておいた方が良いと思う。今回のプログラムで行う内容については前回と全く同じだが、C++0xを使うことによりかなりすっきり書くことができた。因みに現時点の最新の規格(草案)はN3000 (PDF)になる。日本語での資料はC++0xの言語拡張まとめ (Faith and Brave - C++で遊ぼう)本の虫が詳しい。余談だが、2010年になっても0xから1xに変わることはないようだ。C++の生みの親であるBjarne Stroustrupによれば、0xのxは16進数と考えて欲しいとのこと。

C++0xでは多くの便利な機能が追加されているが、今回はラムダ式、auto型指定子、初期化子リストを使用した。使用したコンパイラはVisual Studio 2010 beta2 (VS2010)GCC 4.5 (snapshot 20100114)Intel Compiler 11.1だが、残念ながらVS2010とIntel Compiler 11.1では初期化子リストの機能が実装されていないので、それらを使用する場合、今回示したコードのうち素数を格納する静的メンバコンテナの初期化部分は変更しなくてはならない。また、GCCについては最新リリース版である4.4.2でラムダ式が使えないので、ここでは開発版の4.5を使用している。その他のコンパイラも含めてC++0xへの対応はC++0xCompilerSupportで確認できる。

初期化子リストを使用しない:

static int init_primes[] = { 2, 3, 5, 7 }; vector<int> IsPrime::primes(init_primes, init_primes + 4);

初期化子リストを使用する:

vector<int> IsPrime::primes = { 2, 3, 5, 7 };

今回のコードでは関数オブジェクトを多用していたのでラムダ式が非常に有効だった。ラムダ式を使えば関数オブジェクトを用意しなくてもその場ですぐに記述できるからだ。

以下のコードは関数オブジェクトを用意してsort関数を使用した例だ。

class LessAn { public: bool operator()(const A& a, const A& b) { return a.n < b.n; } }; sort(A_list.begin(), A_list.end(), LessAn());

これに対しラムダ式を使えば、以下のように一行で済ませることができる。

sort(A_list.begin(), A_list.end(), [](const A& a, const A& b) { return a.n < b.n; });

このように、C++0xは機能の一部を使うだけでもとても便利だ。規格が新しくなるたびに新たに覚えなくてはならないことが増えるので、それを面倒と見る向きもあるかもしれないが、そのコストに見合うだけの価値がC++0xにはあると思う。

最後にC++0xで書き換えたソースコードを示す。クラスによる関数オブジェクトがごっそり無くなっていることに気付くだろう。前回からの変更部分は赤で示している。変更前のコードや実行時の出力結果については前回の記事を参考にして欲しい。

#include <iostream> #include <iomanip> #include <vector> #include <algorithm> #include <numeric> #include <cstdlib> using namespace std; const int num_A = 10; // A_listコンテナ内の構造体Aの数. const int max_n = 30; // 構造体A内の配列の最大数. // 構造体A : 要素数n, 要素の配列pを持つ. struct A { int n; int *p; A(int n_, int *p_) : n(n_), p(p_) { for (int i = 0; i < n; i++) p[i] = rand() % max_n; } }; // 構造体Aの表示. void print(const A& a) { cout << setw(3) << a.n << " :"; for (int i = 0; i < a.n; i++) cout << " " << a.p[i]; cout << endl; } // A_listコンテナの表示. void print(const vector<A>& a_list) { cout << " n : p[]" << endl; for (auto p = a_list.begin(); p != a_list.end(); ++p) print(*p); cout << endl; } // 任意の数値を素数判定する関数オブジェクト. class IsPrime { private: static vector<int> primes; int i, j; public: bool operator()(int n) { if (n < 2) return false; if (binary_search(primes.begin(), primes.end(), n)) return true; for (auto p = primes.begin(); p != primes.end(); ++p) { if (n < (*p) * (*p)) return true; if (n % *p == 0) return false; } for (i = *(primes.end() - 1) + 2; i * i <= n; i += 2) { for (j = 0; i > primes[j] * primes[j] && i % primes[j] != 0; j++); if (i < primes[j] * primes[j]) { primes.push_back(i); if (n % i == 0) return false; } } return true; } }; // 素数を格納する静的メンバコンテナ. vector<int> IsPrime::primes = { 2, 3, 5, 7 }; int main() { vector<A> A_list; // 構造体Aのvectorコンテナ A_list. // A_listを乱数で初期化. for (int i = 0; i < num_A; i++) { int n = rand() % max_n + 1; A_list.push_back(A(n, new int[n])); } cout << "初期化した構造体Aのコンテナ(A_list):" << endl; print(A_list); cout << "構造体Aの配列(A.p)をソートして重複データを削除:" << endl; for_each(A_list.begin(), A_list.end(), [](A& a) { sort(a.p, a.p + a.n); a.n = unique(a.p, a.p + a.n) - a.p; }); print(A_list); cout << "構造体Aの配列(A.p)の要素数(A.n)でA_listをソート:" << endl; sort(A_list.begin(), A_list.end(), [](const A& a, const A& b) { return a.n < b.n; }); print(A_list); cout << "構造体Aの配列(A.p)を素数のみにする:" << endl; for_each(A_list.begin(), A_list.end(), [](A& a) { a.n = stable_partition(a.p, a.p + a.n, IsPrime()) - a.p; }); print(A_list); cout << "構造体Aの配列要素の和が偶数ならA_listから削除:" << endl; A_list.erase(remove_if(A_list.begin(), A_list.end(), [](const A& a) { return accumulate(a.p, a.p + a.n, 0) % 2 == 0; }), A_list.end()); print(A_list); cout << "再び構造体Aの配列(A.p)の要素数(A.n)でA_listをソート:" << endl; sort(A_list.begin(), A_list.end(), [](const A& a, const A& b) { return a.n < b.n; }); print(A_list); cout << "構造体Aの配列(A.p)内で指定した数値と一致する要素を持つ構造体Aを探す:" << endl; for (int i = 0; i < 10; i++) { auto p = find_if(A_list.begin(), A_list.end(), [i](const A& a) { return find(a.p, a.p + a.n, i) != a.p + a.n; }); cout << setw(3) << i << " : "; if (p != A_list.end()) print(*p); else cout << "指定の数値を要素として持つ構造体Aは見つかりませんでした." << endl; } return 0; }

0 コメント: