|
C++言語解説:STL基礎(3)アルゴリズム
2003-08-18 |
| [C++ Index Top] [Prev] [Next] |
|
[概要] アルゴリズムはコンテナに対して複雑な処理を行います。ここではアルゴリズム の種類と、代表的アルゴリズムの使用方法を学習します。 [構成]・アルゴリズムの概要 * アルゴリズムとは * アルゴリズムの種類 ・sort, reverseアルゴリズム * sortアルゴリズム * reverseアルゴリズム * 反復子の機能包含 * アルゴリズム使用例 ●アルゴリズムの概要 ◆アルゴリズムとは ・アルゴリズムとはコンテナを対象にソートなどの複雑な処理を行う関数テンプレー トの集まりです。STLのアルゴリズムを使用するには <algorithm> をインクルード する必要があります。 ・簡単な処理、又はコンテナ特有の処理についてはコンテナのメンバ関数で用意され ていますが、汎用的かつ複雑な処理はアルゴリズムで用意されています。 ◆アルゴリズムの種類 ・かなり数が多いのですが、ここでは「感触をつかむ」ために、大分類とアルゴリズ ムの名前を列挙します。各アルゴリズムの詳細についてはコンパイラに付属するマ ニュアルを参照して下さい。 [List1.アルゴリズムの種類] ┌────────────────────────────────────┐ コピー系 要素の置換/削除 シーケンスの変換/生成 +-------------+ +---------------+ +----------+ |copy | |remove | |generate | |copy_backward| |remove_if | |generate_n| |iter_swap | |remove_copy | |transform | |fill | |remove_copy_if | +----------+ |fill_n | |replace | |swap | |replace_if | |swap_ranges | |replace_copy_if| |search | |unique | |search_n | |unique_copy | +-------------+ +---------------+ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 未ソートシーケンス ソート済シーケンス ソート の検索 の検索 +-----------------+ +-------------+ +-------------+ |nth_element | |adjacent_find| |binary_search| |sort | |equal | |lower_bound | |stable_sort | |find | |upper_bound | |partial_sort | |find_end | |equal_range | |partial_sort_copy| |find_if | +-------------+ +-----------------+ |find_first_of| |mismatch | +-------------+ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ソート済みシーケンス シーケンス順変更 のマージ 集合演算 +----------------+ +-------------+ +------------------------+ |rotate | |merge | |includes | |rotate_copy | |inplace_merge| |set_difference | |random_shuffle | +-------------+ |set_intersection | |partition | |set_symmetric_difference| |stable_partition| |set_union | |reverse | +------------------------+ |reverse_copy | +----------------+ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ヒープ演算 最小値/最大値 順列 +---------+ +-----------+ +----------------+ |make_heap| |max | |next_permutation| |push_heap| |max_element| |prev_permutation| |pop_heap | |min | +----------------+ |sort_heap| |min_element| +---------+ +-----------+ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - その他 +-----------------------+ |count | |count_if | |for_each | |lexicographical_compare| +-----------------------+ └────────────────────────────────────┘ ・このリストから一般的なアルゴリズム揃っていることがわかると思います。今回は 代表例としてsortとreverseアルゴリズムを見ていくことにします。 ●sort, reverseアルゴリズム ◆sortアルゴリズム ・sortアルゴリズムは、コンテナ要素(シーケンス)のソートを行う関数テンプレート です。シーケンスの範囲が指定できるので、部分的なソートも可能です。 ┌────────────────────────────────────┐ (1)template <class RandomIter> void sort(RandomIter start, RandomIter end); (2)template <class RandomIter, class Comp> void sort(RandomIter start, RandomIter end, Comp comp); └────────────────────────────────────┘ ・sortアルゴリズムはランダムアクセス型の反復子を使用します。このタイプの反復 子を適用できるアルゴリズムは vector や deque です。 ・尚、ランダムアクセスタイプの反復子を持たないコンテナでは、類似機能が実装さ れています。 ◆reverseアルゴリズム ・reverseアルゴリズムは、コンテナ内要素の順番を反転します。 ┌────────────────────────────────────┐ template <class BidirIter> void reverse(BidirIter start, BidirIter end); └────────────────────────────────────┘ ◆反復子の機能包含 ・reverseアルゴリズムは双方向反復子を使用します。ここで、反復子には上位と下 位の関係があります。 ┌────────────────────────────────────┐ 上位↑ (1)ランダムアクセス反復子 ↑ (2)双方向反復子 ↑ (3)前方反復子 ↑ (4)入力反復子 下位↑ (5)出力反復子 └────────────────────────────────────┘ ・上位の反復子は下位の機能を包含します。例えば上位であるランダムアクセス反復 子は、下位の双方子反復子以下全ての反復子の機能を包含しています。 ・従ってランダムアクセス反復子をサポートするvectorやdequeコンテナには当然 reverseアルゴリズムを適用することができます。 ◆アルゴリズム使用例 ・sortとreverseによるアルゴリズムの使用例を見ることにします。コードをList2に 示します。 ・sortとreverseの動作を文字列に対して行っていますが、それは実質2行だけで、他 はほとんどデータの入力と出力のみです。 [List2.アルゴリズムの使用例] ┌────────────────────────────────────┐ #include <iostream> #include <vector> #include <algorithm> using namespace std; void DataOut(vector<string>& strVector); int main() { vector<string> strVector; strVector.push_back("dynastar:0"); //0 strVector.push_back("ogasaka :1"); //1 strVector.push_back("salomon :2"); //2 strVector.push_back("raichel :3"); //3 strVector.push_back("hart :4"); //4 strVector.push_back("kneissl :5"); //5 cout << "==== オリジナル ====" << endl; DataOut(strVector); cout << "==== sort後 ====" << endl; sort(strVector.begin(), strVector.end()); DataOut(strVector); cout << "==== reverse後 ====" << endl; reverse(strVector.begin(), strVector.end()); DataOut(strVector); return 0; } void DataOut(vector<string>& strVector) { vector<string>::iterator iteStr; iteStr = strVector.begin(); while(iteStr != strVector.end()){ cout << *iteStr << endl; iteStr++; } cout << endl; return; } └────────────────────────────────────┘ ┌────────────────────────────────────┐ [出力結果] ==== オリジナル === dynastar:0 ogasaka :1 salomon :2 raichel :3 hart :4 kneissl :5 ==== sort後 ==== dynastar:0 hart :4 kneissl :5 ogasaka :1 raichel :3 salomon :2 ==== reverse後 ==== salomon :2 raichel :3 ogasaka :1 kneissl :5 hart :4 dynastar:0 └────────────────────────────────────┘ ・出力結果を見ると、結果がソートされていることがわかります。List2の例ではば らばらの文字列をsort()で整えた後、reverse()で反転させています。 ・今回はvectorコンテナ要素にstringクラスを使用しています。stringはSTLではあ りませんが、標準C++に組み込まれた文字列クラスです。その使用方法はSTLと互換 性があり、コンテナとして動作します。またCの文字列(\0で終わる)もサポートし ています。 ・stringクラスの詳細は別の場で扱いますが、今は上記コードにおけるstringの役割 として「複数文字列のメモリ確保を自動で行わせている」と理解して下さい。 ・そろそろSTLを使用することで、簡潔かつ正確にコードを記述できると思えるよう になってきたでしょうか。次回はSTL基礎編の最後として、transform()アルゴリズ ムと関数オブジェクトを扱いたいと思います。 [Revision Table] |Revision |Date |Comments |----------|-----------|----------------------------------------------------- |1.00 |2003-08-18 |初版 |1.01 |2003-08-25 |リンク追加 |1.02 |2003-09-06 |リンク間違い修正 [end] |
|
Copyright(C) 2003 Altmo
|
| [C++ Index Top] [Prev] [Next] |