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

C++に慣れている人にとっては当たり前のことかもしれないけど、あまりC++に親しんでいない場合、構造体を格納したSTLコンテナに対してアルゴリズム<algorithm>を有効に活用していないかもしれない。そこで、構造体を格納したvectorなどのSTLコンテナでソートや探索、削除などのアルゴリズムの利用方法を書いておく。

struct A { int n; int* p; };

上記のような構造体はよく見かける形だと思う。構造体Aに整数型変数のnとポインタ型変数のpがあり、例えばnに配列の要素数、pにその配列を確保したりする。こういった構造体を以下のようにvectorなどのSTLコンテナを使って格納することは多々ある。

vector<A> A_list;

これで構造体Aをコンテナに格納できるわけだ。ところで、STLコンテナを使用する一つの理由として便利なアルゴリズムが利用できることが挙げられるだろう。sortやfindなどの定番のアルゴリズムは、それほどC++を利用していない人でもSTLを使ったことがあるのであれば知っていると思う。これらはとても便利だが、上記の構造体を入れたコンテナに対して以下のようには利用できない。

sort(A_list.begin(), A_list.end());

当たり前のことだが、どのような基準でソートするのかコンパイラには分からないからだ。なので、どのような基準でソートさせるのかを関数オブジェクトを使って教えればいい。因みに関数オブジェクトとは、operator()が定義されているクラスのことだ。

例えば構造体Aのメンバ変数であるnを基準に昇順にソートさせたいとする。その場合は以下のような関数オブジェクトを作って、sortアルゴリズムの第3引数に渡せばいい。

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

sort(A_list.begin(), A_list.end(), LessAn());

たったこれだけだ。

他のアルゴリズムに対しても基本的には同じように関数オブジェクトを使えばいい。探索(find_if)や削除(remove_if)、繰り返し処理(for_each)などを使ったアルゴリズムの利用例を以下に挙げておく。

1から30までのランダムな要素数nと0から29までのランダムな要素の配列pを持つの構造体Aを10個作成してvectorコンテナA_listに格納した。それに対し複数のアルゴリズムを適用した出力結果を以下に示している。

初期化した構造体Aのコンテナ(A_list): n : p[] 12 : 17 4 10 29 4 18 18 22 14 5 5 1 28 : 1 11 25 2 27 6 21 24 2 3 22 22 21 26 8 5 17 6 11 18 9 22 17 19 25 24 23 21 3 : 3 3 14 22 : 1 23 28 17 14 22 27 27 19 23 21 19 28 16 5 20 12 18 16 10 2 4 29 : 26 15 20 9 10 20 6 21 3 8 9 23 24 4 6 20 16 26 11 28 24 9 26 13 17 28 8 12 9 12 : 3 5 19 18 24 0 27 26 23 6 11 5 15 : 22 0 9 17 3 27 12 16 0 11 6 5 17 15 4 12 : 22 20 10 21 4 16 10 27 11 7 27 7 18 : 3 3 5 29 19 8 11 18 2 16 26 10 3 8 0 11 12 5 11 : 29 24 17 8 3 25 21 2 20 1 26 構造体Aの配列(A.p)をソートして重複データを削除: n : p[] 9 : 1 4 5 10 14 17 18 22 29 18 : 1 2 3 5 6 8 9 11 17 18 19 21 22 23 24 25 26 27 2 : 3 14 17 : 1 2 4 5 10 12 14 16 17 18 19 20 21 22 23 27 28 18 : 3 4 6 8 9 10 11 12 13 15 16 17 20 21 23 24 26 28 11 : 0 3 5 6 11 18 19 23 24 26 27 13 : 0 3 4 5 6 9 11 12 15 16 17 22 27 9 : 4 7 10 11 16 20 21 22 27 13 : 0 2 3 5 8 10 11 12 16 18 19 26 29 11 : 1 2 3 8 17 20 21 24 25 26 29 構造体Aの配列(A.p)の要素数(A.n)でA_listをソート: n : p[] 2 : 3 14 9 : 1 4 5 10 14 17 18 22 29 9 : 4 7 10 11 16 20 21 22 27 11 : 0 3 5 6 11 18 19 23 24 26 27 11 : 1 2 3 8 17 20 21 24 25 26 29 13 : 0 3 4 5 6 9 11 12 15 16 17 22 27 13 : 0 2 3 5 8 10 11 12 16 18 19 26 29 17 : 1 2 4 5 10 12 14 16 17 18 19 20 21 22 23 27 28 18 : 1 2 3 5 6 8 9 11 17 18 19 21 22 23 24 25 26 27 18 : 3 4 6 8 9 10 11 12 13 15 16 17 20 21 23 24 26 28 構造体Aの配列(A.p)を素数のみにする: n : p[] 1 : 3 3 : 5 17 29 2 : 7 11 5 : 3 5 11 19 23 4 : 2 3 17 29 4 : 3 5 11 17 6 : 2 3 5 11 19 29 5 : 2 5 17 19 23 7 : 2 3 5 11 17 19 23 5 : 3 11 13 17 23 構造体Aの配列要素の和が偶数ならA_listから削除: n : p[] 1 : 3 3 : 5 17 29 5 : 3 5 11 19 23 4 : 2 3 17 29 6 : 2 3 5 11 19 29 5 : 3 11 13 17 23 再び構造体Aの配列(A.p)の要素数(A.n)でA_listをソート: n : p[] 1 : 3 3 : 5 17 29 4 : 2 3 17 29 5 : 3 5 11 19 23 5 : 3 11 13 17 23 6 : 2 3 5 11 19 29 構造体Aの配列(A.p)内で指定した数値と一致する要素を持つ構造体Aを探す: 0 : 指定の数値を要素として持つ構造体Aは見つかりませんでした. 1 : 指定の数値を要素として持つ構造体Aは見つかりませんでした. 2 : 4 : 2 3 17 29 3 : 1 : 3 4 : 指定の数値を要素として持つ構造体Aは見つかりませんでした. 5 : 3 : 5 17 29 6 : 指定の数値を要素として持つ構造体Aは見つかりませんでした. 7 : 指定の数値を要素として持つ構造体Aは見つかりませんでした. 8 : 指定の数値を要素として持つ構造体Aは見つかりませんでした. 9 : 指定の数値を要素として持つ構造体Aは見つかりませんでした.

以下、ソースコード。

#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 (vector<A>::const_iterator p = a_list.begin(); p != a_list.end(); ++p) print(*p); cout << endl; } // A_listコンテナを構造体Aの配列要素数でソートするための関数オブジェクト. class LessAn { public: bool operator()(const A& a, const A& b) { return a.n < b.n; // 昇順. } }; // 構造体Aの配列の重複を削除するための関数オブジェクト. class UniqueAp { public: void operator()(A& a) { sort(a.p, a.p + a.n); // 配列内をソート. a.n = unique(a.p, a.p + a.n) - a.p; // 重複を削除. } }; // 任意の数値を素数判定する関数オブジェクト. 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 (vector<int>::iterator 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; } }; // 素数を格納する静的メンバコンテナ. static int init_primes[] = { 2, 3, 5, 7 }; vector<int> IsPrime::primes(init_primes, init_primes + 4); // 構造体Aの配列の要素を素数のみにするための関数オブジェクト. class PrimeAp { public: void operator()(A& a) { // 素数のみを区分けする. // 順番を保持したいのでpartitionではなくstable_partitionを使用. a.n = stable_partition(a.p, a.p + a.n, IsPrime()) - a.p; } }; // 構造体Aの配列の要素の和が偶数がどうか判定する関数オブジェクト. class SumAp_even { public: bool operator()(const A& a) { // 配列内の要素の和を2で割った余りが0か? return accumulate(a.p, a.p + a.n, 0) % 2 == 0; } }; // 構造体Aの配列に指定の数値を含むか判定する関数オブジェクト. class FindAp { private: int n; public: FindAp(int n_) : n(n_) { } bool operator()(const A& a) { // 配列から指定の数値をfindで探索. // 因みにアルゴリズムはSTLコンテナだけではなくポインタでも利用できる. return find(a.p, a.p + a.n, n) != a.p + a.n; } }; int main() { vector<A> A_list; // 構造体Aのvectorコンテナ. // A_listを初期化. for (int i = 0; i < num_A; i++) { // 構造体Aの配列の要素数を乱数で決定. 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(), UniqueAp()); print(A_list); cout << "構造体Aの配列(A.p)の要素数(A.n)でA_listをソート:" << endl; sort(A_list.begin(), A_list.end(), LessAn()); print(A_list); cout << "構造体Aの配列(A.p)を素数のみにする:" << endl; for_each(A_list.begin(), A_list.end(), PrimeAp()); print(A_list); cout << "構造体Aの配列要素の和が偶数ならA_listから削除:" << endl; A_list.erase(remove_if(A_list.begin(), A_list.end(), SumAp_even()), A_list.end()); print(A_list); cout << "再び構造体Aの配列(A.p)の要素数(A.n)でA_listをソート:" << endl; sort(A_list.begin(), A_list.end(), LessAn()); print(A_list); cout << "構造体Aの配列(A.p)内で指定した数値と一致する要素を持つ構造体Aを探す:" << endl; vector<A>::iterator p; for (int i = 0; i < 10; i++) { p = find_if(A_list.begin(), A_list.end(), FindAp(i)); cout << setw(3) << i << " : "; if (p != A_list.end()) print(*p); else cout << "指定の数値を要素として持つ構造体Aは見つかりませんでした." << endl; } return 0; }