2008年5月14日水曜日

C++: vector<vector<int> >などの入れ子のSTLコンテナをソートする

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

vectorクラスやlistクラスなどの入れ子になったSTLコンテナ(vector<vector<int> >など)をソートするやり方。algorithmのsortで可能。ここでは、普通の昇順と降順、和、積、二乗の和の昇順についてソースを示す。基本的には比較関数さえ用意すればどんなソートにでも対応できる。

#include <iostream> #include <vector> #include <algorithm> #include <numeric> #include <functional> using namespace std; // 入れ子のコンテナの表示関数. void print_list(const vector<vector<int> >& v_list) { for (vector<vector<int> >::const_iterator p = v_list.begin(); p != v_list.end(); ++p) { for (vector<int>::const_iterator q = p->begin(); q != p->end(); ++q) cout << *q << " "; cout << endl; } } // 和の比較関数. template<class T> bool less_summation(const vector<T>& a, const vector<T>& b) { return accumulate(a.begin(), a.end(), 0) < accumulate(b.begin(), b.end(), 0); } // 積の比較関数. template<class T> bool less_product(const vector<T>& a, const vector<T>& b) { return accumulate(a.begin(), a.end(), 1, multiplies<T>()) < accumulate(b.begin(), b.end(), 1, multiplies<T>()); } // 二乗の和の関数オブジェクト. template<class T> class add_square : public binary_function<T, T, T> { public: result_type operator()(first_argument_type a, second_argument_type b) { return a + b * b; } }; // 二乗の和の比較関数. template<class T> bool less_add_square(const vector<T>& a, const vector<T>& b) { return accumulate(a.begin(), a.end(), 0, add_square<T>()) < accumulate(b.begin(), b.end(), 0, add_square<T>()); } int main() { vector<int> v; vector<vector<int> > v_list; // 10個の数値の入ったコンテナ(v)を5つ含むコンテナを作成(v_list). for (int i = 0; i < 5; i++) { v.clear(); for (int j = i; j < i + 10; j++) v.push_back(j % 2 == 0 ? j : -j); // 交互に正と負とする. v_list.push_back(v); } cout << "昇順" << endl; sort(v_list.begin(), v_list.end()); print_list(v_list); cout << "降順" << endl; sort(v_list.begin(), v_list.end(), greater<vector<int> >()); print_list(v_list); cout << "和の昇順" << endl; sort(v_list.begin(), v_list.end(), less_summation<int>); print_list(v_list); cout << "積の昇順" << endl; sort(v_list.begin(), v_list.end(), less_product<int>); print_list(v_list); cout << "二乗の和の昇順" << endl; sort(v_list.begin(), v_list.end(), less_add_square<int>); print_list(v_list); return 0; }

以下のように表示される

昇順 -3 4 -5 6 -7 8 -9 10 -11 12 -1 2 -3 4 -5 6 -7 8 -9 10 0 -1 2 -3 4 -5 6 -7 8 -9 2 -3 4 -5 6 -7 8 -9 10 -11 4 -5 6 -7 8 -9 10 -11 12 -13 降順 4 -5 6 -7 8 -9 10 -11 12 -13 2 -3 4 -5 6 -7 8 -9 10 -11 0 -1 2 -3 4 -5 6 -7 8 -9 -1 2 -3 4 -5 6 -7 8 -9 10 -3 4 -5 6 -7 8 -9 10 -11 12 和の昇順 4 -5 6 -7 8 -9 10 -11 12 -13 2 -3 4 -5 6 -7 8 -9 10 -11 0 -1 2 -3 4 -5 6 -7 8 -9 -1 2 -3 4 -5 6 -7 8 -9 10 -3 4 -5 6 -7 8 -9 10 -11 12 積の昇順 4 -5 6 -7 8 -9 10 -11 12 -13 -3 4 -5 6 -7 8 -9 10 -11 12 2 -3 4 -5 6 -7 8 -9 10 -11 -1 2 -3 4 -5 6 -7 8 -9 10 0 -1 2 -3 4 -5 6 -7 8 -9 二乗の和の昇順 0 -1 2 -3 4 -5 6 -7 8 -9 -1 2 -3 4 -5 6 -7 8 -9 10 2 -3 4 -5 6 -7 8 -9 10 -11 -3 4 -5 6 -7 8 -9 10 -11 12 4 -5 6 -7 8 -9 10 -11 12 -13

二乗の和の比較は以下のように変更しても同じ結果となる。

return inner_product(a.begin(), a.end(), a.begin(), 0) < inner_product(b.begin(), b.end(), b.begin(), 0);

0 コメント: