List コンテナをソートする関数

前田稔(Maeda Minoru)の超初心者のプログラム入門

プログラムの説明

1. ソースプログラムです。
   

   ファイル名	説明
   listsort.cpp	List ソート関数

2. ゲームプログラムでは STL の list を使うと便利なことが多いのですが、構造体リストをキー項目で順番に並べたいことがあります。
   STL には強力な共通アルゴリズムが備わっているのですが、構造体には無力で自分で作成しなければならないようです。 (^_^;
   このページではソート関数を使って STL の構造体リストをソートする方法を説明します。
   
3. ヘッダファイルのインクルードと構造体の定義です。
   list を使うときは list をインクルードして下さい。
   using namespace で std で宣言されたネームを使えるようにします。
   LANK が構造体の定義で、key で list をソートします。
   LANK tbl[6] で list に登録するデータを定義しています。
   

   #include <iostream> #include <list> using namespace std; typedef struct { int key; char s[8]; } LANK; LANK tbl[6]= { {5,"suzuki"}, {3,"tanaka"}, {1,"aoki"}, {4,"maeda"}, {6,"yamada"}, {2,"ozawa"} };

4. 構造体を list に登録するソースコードです。
   

   list<LANK> v; int i; for(i=0; i<6; i++) v.push_back(tbl[i]);

5. 登録が終わると list をソートする Sort() 関数を呼び出します。
   

   Sort(v);

6. ソートした list を表示します。
   

   list<LANK> v; list<LANK>::iterator p; for(p=v.begin(); p!=v.end(); p++) cout << p->key << " " << p->s << endl;

7. 今回のメインテーマである構造体リストをソートする関数です。
   隣接ソートを使って key が同じ値のとき順番が入れ替わらないようにしています。
   ep には list の最後の要素のポインタを設定します。
   pv.end() が list の「最後の要素の次」をポイントしていることに留意して下さい。
   sw は入れ替えが起こったことを記憶するフラグです。
   p と q(p+1) のポインタが指す構造体の key を比較して ＞ の時に swap で入れ替えています。
   

   void Sort(list<LANK> &pv) { list<LANK>::iterator p,q,ep; int sw; ep= pv.end(); ep--; sw= 1; while(sw) { for(sw=0,p=pv.begin(); p!=ep; p++) { q= p; q++; if (p->key > q->key) { sw =1; swap(*p,*q); } } } }

【演習】

超初心者のプログラム入門(C/C++)