最近更新したページ
2013-10-20
2013-09-29
2013-09-23
2012-01-07
2011-11-09
2011-10-23
2011-10-09
2011-10-01
2011-09-29
2011-09-03
2011-08-07
2011-08-02
2011-07-29
2011-07-10
2011-05-05
2011-05-04
2011-04-24
2011-04-13
2011-04-05
2011-03-26
2011-02-18
2011-02-15
2010-12-26
2010-12-07
2010-12-05
2010-11-23
2010-09-28
2010-09-23
2010-08-26
2010-08-22
2010-07-16
2010-01-17
2010-01-11
2009-10-04
2009-08-21
2009-08-13
2009-06-18
2009-06-01
2009-04-29
2009-02-16
2009-02-11
2009-02-03
2008-07-22
2008-07-21
2008-07-15
2008-07-14
2008-07-13
2008-07-12
2008-07-08
2008-07-05
2008-06-28
2008-06-17
2008-06-05
2008-06-02
2008-06-01
2008-05-29
2008-05-26
2008-05-21
2008-05-19
2008-05-18
2007-10-31
2007-10-27
2007-09-28
2007-09-23
2007-09-17
2007-09-16
2007-09-14
2007-09-11
2007-06-18
2007-04-15
2006-12-21
2006-11-30
2006-11-22
2006-08-17
2006-03-29
2006-03-28
2006-03-27

STL 連想コンテナ(sample)


連想コンテナ(sample program)

 二分木データ構造を提供する。メンバ関数は全て共通。
 set/multiset map/multimap のサンプルコード置き場。
 STL コンテナ頁より、分頁。(内容非保証)

set/multiset

 集合を扱う2分木データ(tree)構造を提供。小さい値から検索できる。

set sample

 定義、追加、表示、検索・抽出

set:定義とメイン部
#include <iostream>
#include <string>
#include <set>
using namespace std;
void s_inp(set<int>& s);
void s_dsp(set<int>& s);
void s_find(int ns,int ne,set<int>& s);
void s_bound(int low,int high,set<int>& s);
void main() {
   set<int> s;
   s_inp(s);         // data を追加
   s_dsp(s);         // data の全表示
   s_find(15,24,s);  // 指定範囲データ(集合)抽出(検索)
   s_bound(15,24,s); // メンバ関数利用の集合抽出
}

set:データ追加
// set s へ data を追加
void s_inp(set<int>& s) {
   s.insert(18);   // 意図的な順不同入力
   s.insert(9);    // 出力順に注目(ソートされている)
   s.insert(39);
   s.insert(15);
   s.insert(25);
   s.insert(36);
   s.insert(24);
   s.insert(27);
   s.insert(3);
   s.insert(33);
   cout << "*** set s data insert end ***" << endl;
}

set:データの表示
// set s data 全表示
void s_dsp(set<int>& s) {
   set<int>::iterator itr   = s.begin();
   set<int>::iterator itr_e = s.end();
   cout << "data 範囲:" << *itr << "〜" << *(--itr_e) << endl;
   for ( ;itr != s.end(); ++itr) {
      printf("%i ",*itr);          // s.begin() 〜 s.end() まで表示
   }
   cout << endl << "*** set data view end ***" << endl;
}

set:データの抽出・検索
// set s から指定範囲のデータを逐次抽出(検索)
void s_find(int ns,int ne,set<int>& s) {
   cout << "抽出範囲:" << ns << "〜" << ne << endl;
   set<int>::iterator itr_f;
   for (int i=ns; i<(ne+1); ++i ) {      // 検索範囲 ns〜ne 指定
      itr_f = s.find(i);                 // i を検索
      if ( itr_f != s.end() ) {
         printf("%3i is found. *itr_f=%i\n",i,*itr_f);}   // found
      } else {
         cout << " --- " << i << " is not found." << endl; // not found.
      }
   }
   cout << "*** set data found view end ***" << endl;
}
// lower_bound(low) upper_bound(high) 指定範囲データ抽出
void s_bound(int low,int high,set<int>& s) {
   cout << "指定範囲:" << low << "〜" << high << endl;
   set<int>::iterator itr_fs = s.lower_bound(15);  // 下限指定
   set<int>::iterator itr_fe = s.upper_bound(24);  // 上限指定
   set<int>::iterator itr    = itr_fs;
   for(itr_fs; itr != itr_fe; ++itr) {             // 検索範囲 15〜24
      printf("%3i(*itr) is found. \n",*itr);       // 抽出結果表示
   }
   cout << "*** set data bound view end ***" << endl;
}

▲上へ [ 編集 ]

set:表示サンプル
*** set s data insert end ***
data 範囲:3〜39
3 9 15 18 24 25 27 33 36 39   // 補足:自動ソートされている
*** set s data view end ***
抽出範囲:15〜24
 15 is found. *itr_f=15
 … 16 is not found.
 … 17 is not found.
 18 is found. *itr_f=18
 … 19 is not found.
 … 20 is not found.
 … 21 is not found.
 … 22 is not found.
 … 23 is not found.
 24 is found. *itr_f=24
*** set s data found view end ***
指定範囲:15〜24
 15(*itr) is found.  // lower_bound() upper_bound() 使用
 18(*itr) is found.  // 該当ノードをダイレクトに抽出する
 24(*itr) is found.
*** set data bound view end ***
続行するには何かキーを押してください . . .
※サンプルは数値型だが、文字列他でも利用可能と思われる。
※文字列を抽出対象とする場合、強力な集合処理が期待できそう。
※set を multiset としても同じ結果が返る。

▲上へ [ 編集 ]

multiset sample

 set の重複キーを許容するコンテナ。
 使用方法等は、set と同じだが、set で定義した部分を multiset へ変更する必要あり。

※基本は set と同じ。set のサンプルの変更部分のみ記述。

multiset:set multiset を任意に切り替える
typedef tdef_set multiset     // set/multiset の切り替え

※以降 set を tdef_set と変更。( multisetと直接書いても良い)

multiset:関数テンプレートを修正
void s_inp(tdef_set<int>& s); // set の部分を修正
〜
void main() {
   tdef_set<int> s;           // 修正
   〜
}

multiset:データ追加
^void s_inp(tdef_set<int>& s) {
   〜            // 適当な位置へ以下追加
   s.insert(9);  // ml9  追加計 2
   s.insert(24); // ml24 追加
   s.insert(24); // ml24 追加計 3
   s.insert(15); // ml15 追加
   s.insert(15); // ml15 追加計 3
}

multiset:データの表示
void s_dsp(tdef_set<int>& s) {
   tdef_set<int>::iterator itr   = s.begin();
   tdef_set<int>::iterator itr_e = s.end();
   〜
}

multiset:データの抽出・検索(利用不可)
※この関数では、重複データまで検索されない。
void s_find(int ns,int ne,tdef_set<int>& s) {
   cout << "抽出範囲:" << ns << "〜" << ne << endl;
   tdef_set<int>::iterator itr_f;
   for (int i=ns; i<(ne+1); ++i ) {      // 検索範囲 ns〜ne 指定
      itr_f = s.find(i);                 // i を検索
      if ( itr_f != s.end() ) {
         printf("%3i is found. *itr_f=%i\n",i,*itr_f);}   // found
      } else {
         cout << " --- " << i << " is not found." << endl; // not found.
      }
   }
   cout << "*** set data found view end ***" << endl;
}
※範囲指定が、値範囲、且つ、1データ検索終了で次範囲へインクリメントされるのが原因。
※イテレータを使用するか、データ範囲突合せなら同データ not found が出るまで検索が必要。

multiset:データの抽出・検索(正常動作)
※こちらの抽出関数は問題無い。
void s_bound(int low,int high,tdef_set<int>& s) {
   〜
   tdef_set<int>::iterator itr_fs = s.lower_bound(15);  // 下限指定
   tdef_set<int>::iterator itr_fe = s.upper_bound(24);  // 上限指定
   tdef_set<int>::iterator itr    = itr_fs;
   〜
}

▲上へ [ 編集 ]

multiset:表示サンプル
*** set s data insert end ***
data 範囲:3〜39
3 9 9 15 15 15 18 24 24 24 25 27 33 36 39 // 重複表示(安定?)
*** set data view end ***
 15 is found. *itr_f=15 // 重複出力に失敗している
 … 16 is not found.
 … 17 is not found.
 18 is found. *itr_f=18 // 重複出力に失敗している
 … 19 is not found.    // 重複キー検索方法に問題あり
 … 20 is not found.
 … 21 is not found.
 … 22 is not found.
 … 23 is not found.
 24 is found. *itr_f=24 // 重複出力に失敗している
*** set s data found view end ***
指定範囲:15〜24
found. *itr_f=15 // lower_bound() upper_bound() 使用
found. *itr_f=15 // この方法ならまったく問題無い
found. *itr_f=15
found. *itr_f=18
found. *itr_f=24
found. *itr_f=24
found. *itr_f=24
*** set data bound view end ***
続行するには何かキーを押してください . . .

▲上へ [ 編集 ]

map/multimap

 set/multiset をより複雑にした、2分木データ(tree)構造を提供。
 キーとなる部分を整数に限定しない構造になっている。

 また、map / multimap は、その構造上2つのデータをペアで管理する。この対になるペアデータを格納する class が、peir である。

pair sample

 マップの前にペア(クラス)のサンプル使用例。

pair sample1
#include <iostream>
#include <map>
using namespace std;

void main() {
   pair< int, string > pr( 47, "Clare" );
      printf( "first=%2i second=%s \n", pr.first, (pr.second).c_str() );
}
※string のように2つのデータがセットになった新しい型を提供している。pair型として宣言、代入、参照をサポートするクラスである。

pair:表示サンプル
first=47 second=Clare
続行するには何かキーを押してください . . .
※これだけの事だが、pair の宣言、代入、first/second 参照 まで知らなければ、map/multimap の次のステップに進めない。

▲上へ [ 編集 ]

map sample 2


sample 2
C言語系とは、思えないほどふざけた(?柔軟な…)配列名を使える。
#include <iostream>
#include <map>
#include <string>
using namespace std;
void main() {
   map<int, string>    no;
   map<string, int>    age;
   map<string, string> name;

   no[3] = "李 小狼";
   no[4] = "李 苺鈴";
   no[1] = "木之本 桜";
   no[2] = "大道寺 知世";
   no[5] = "柊沢 エリオル";

   age["李 小狼"]       = 14;
   age["李 苺鈴"]       = 13;
   age["木之本 桜"]     = 14;
   age["大道寺 知世"]   = 13;
   age["柊沢 エリオル"] = 13;

   name["li syaoran"]        = "李 小狼";
   name["li meirin"]         = "李 苺鈴";
   name["kinomoto sakura"]   = "木之本 桜";
   name["daidouji tomoyo"]   = "大道寺 知世";
   name["hiiragizawa eriol"] = "柊沢 エリオル";

   cout << "2番の生徒は「" << no[2] << "」ちゃん" << endl;
   cout << "エリオル君の年齢は " << age["柊沢 エリオル"] << " 歳"<< endl;
   cout << "メイリンちゃんの名前は「" << name["li meirin"] << "」" << endl;
}

表示サンプル
2番の生徒は「大道寺 知世」ちゃん
エリオル君の年齢は 13 歳
メイリンちゃんの名前は「李 苺鈴」
続行するには何かキーを押してください . . .

▲上へ [ 編集 ]

map sample 0

 pair を理解したところで、ごく簡単な map の例。

map:定義からデータ表示まで
void main() {
   typedef pair< int, string > tdef_pr;  // pair の短縮定義
   typedef map< int, string >  tdef_map; // map/multimap 切替容易
   // データをセットする
   tdef_map claymore;                    // map<int,string> 短縮
   claymore.insert( tdef_pr( 1,"Alicia"   ));
   claymore.insert( tdef_pr( 2,"Beth"     ));
   claymore.insert( tdef_pr( 3,"Galatea"  ));
   claymore.insert( tdef_pr( 4,"Rafaela"  ));
   claymore.insert( tdef_pr( 5,"Ophelia"  ));
   claymore.insert( tdef_pr( 6,"Miria"    ));
   claymore.insert( tdef_pr( 9,"Jean"     ));
   claymore.insert( tdef_pr(15,"Deneve"   ));
   claymore.insert( tdef_pr(22,"Helen"    ));
   claymore.insert( tdef_pr(47,"Clare"    ));
   /* 重複部分はコメントアウト
   claymore.insert( tdef_pr( 1,"Teresa"   )); // 重複
   claymore.insert( tdef_pr( 2,"Irene"    )); // 重複
   claymore.insert( tdef_pr( 2,"Priscilla")); // 重複
   */
   // 表示
   tdef_map::iterator it = claymore.begin(); // map<int,string> 短縮
   for( ; it != claymore.end(); ++it ) {
      printf( "%2i:%s \n", it->first, (it->second).c_str() );
   }
}
※動作確認済み。
map sample0:表示サンプル
 1:Alicia
 2:Beth
 3:Galatea
 4:Rafaela
 5:Ophelia
 6:Miria
 9:Jean
15:Deneve
22:Helen
47:Clare
続行するには何かキーを押してください . . .

▲上へ [ 編集 ]

map sample 1

 定義、追加、検索、全表示

map:定義とメイン部分
#include <iostream>
#include <string>
#include <map>
using namespace std;
void dsp(map<int,string>& item);
void inp(map<int,string>& item);
void find_dsp(int x,map<int,string>& item);
void main() {
   map<int, string> item;
   inp(item);          // データ入力
   find_dsp(4,item);   // データ検索
   dsp(item);          // 全データ表示
}

map:データ一覧表示
// *** map data list view ***
void dsp(map<int,string>& item) {
   map<int,string>::iterator itr;
   // 一覧表示
   for(itr=item.begin(); itr!=item.end(); ++itr) {
      printf( "%.4i:%s \n", itr->first, (itr->second).c_str() );
   }
}

map:データの追加
// *** map data input ***
void inp(map<int,string>& item) {
   //                         -key- -item-
   item.insert(pair<int,string>( 4,"ノート"   )); // "A-1"
   item.insert(pair<int,string>( 5,"えんぴつ" )); // "B-1"
   item.insert(pair<int,string>( 2,"定規"     )); // "B-2"
   item.insert(pair<int,string>( 1,"コンパス" )); // "B-3"
   item.insert(pair<int,string>( 7,"画用紙"   )); // "C-1"
   item.insert(pair<int,string>( 3,"下敷き"   )); // "B-4"
   item.insert(pair<int,string>( 6,"消しゴム" )); // "B-5"
   cout << "*** 代入終了 ***" << "\n";
   // map は、-key-値を string として A-1 等として管理可能
   // multimap では、-key-値の重複を許す
}

map:データから検索
// *** map data find ***
void find_dsp(int item_no,map<int,string>& item) {
   map<int, string>::iterator itr;
   itr=itms.find(item_no);              // イテレータを使って検索
   if(itr != item.end()) {
      print("検索結果:%.4i %s \n",itr->first,(itr->second).c_str());
   } else {
      cout << "該当商品無し" << endl;
   }
}

▲上へ [ 編集 ]

map/multimap 比較用 sample

 map を multimap で置き換え、重複インデックスキーを許す例。

map/multimap:動物の種類(目)と名称の関連付け
void main() {
   // map → multimap 変更で重複キーを許可可能。
   map<string, string> item;
   // 代入
   item.insert(pair<string,string>("ネコ目","ライオン"));       // 正常登録
   item.insert(pair<string,string>("ペンギン目","ペンギン"));   // 正常登録
   item.insert(pair<string,string>("ウシ目","キリン"));         // 正常登録
   item.insert(pair<string,string>("カンガルー目","コアラ"));   // 正常登録
   // map 重複キー登録テスト → 実行時エラー無しで登録もされず。
   // multimap では「ネコ目:レッサーパンダ」の登録可能。
   item.insert(pair<string,string>("ネコ目","レッサーパンダ")); // 無視
   itms.insert(pair<string,string>("ワニ目","ワニ"));          // 正常登録
   // 検索
   map<string, string>::iterator itr;
   itr=itms.find("ウシ目");              // イテレータを使って検索
   if(itr != item.end()) {
      print("結果:%s:%s\n",(itr->first).c_str(),(itr->second).c_str());
   } else {
      cout << "登録無" << endl;
   }
   // map では、直接指定して表示可能
   // multimap では、コンパイルエラーが発生する
   cout << item["ウシ目"] << endl;       // map →「キリン」を返す!!
   // at.item("ウシ目") は利用不可。連想コンテナのメンバ関数に無い。
}
※map/multimap での動作の違いに注目。
※C/C++ らしからぬデータ処理が、こんなに簡単に出きる!!

▲上へ [ 編集 ]

multimap sample


multimap sample
 pair, map, maltimap の概要を理解したところで、再確認の multimap 例。

multimap:定義からデータ表示まで
※map sample0 を 2〜3箇所変更するだけで multimap 使用に変更できる。
void main() {
   〜
   typedef multimap< int, string >  tdef_map; // multimap へ切替
   〜
   /* コメント解除 */
   claymore.insert( tdef_pr( 1,"Teresa"    )); // 重複登録
   claymore.insert( tdef_pr( 2,"Irene"     )); // 重複登録
   claymore.insert( tdef_pr( 2,"Priscilla" )); // 重複登録
   /* コメント解除 */
   〜
}
※typedef で multimap へ、コメント解除し重複登録実行へ修正。

map sample0:表示サンプル
 1:Alicia
 1:Teresa    // 重複キー
 2:Beth
 2:Irene     // 重複キー
 2:Priscilla // 重複キー
 3:Galatea
 4:Rafaela
 5:Ophelia
 6:Miria
 9:Jean
15:Deneve
22:Helen
47:Clare
続行するには何かキーを押してください . . .
※typedef は、とっても便利!

▲上へ [ 編集 ]

リンク


内部リンク


外部リンク


  • 現在ありません

▲上へ [ 編集 ]

覚え書き


試行錯誤

 set 同様 範囲を渡しての検索結果を抽出は中々難しい。要再考。

multiset:データの抽出・検索(利用不可)
※この関数では、重複データまで検索されない。
void s_find(int ns,int ne,tdef_set<int>& s) {
   cout << "抽出範囲:" << ns << "〜" << ne << endl;
   tdef_set<int>::iterator itr_f;
   for (int i=ns; i<(ne+1); ++i ) {      // 検索範囲 ns〜ne 指定
      itr_f = s.find(i);                 // i を検索
      if ( itr_f != s.end() ) {
         printf("%3i is found. *itr_f=%i\n",i,*itr_f);}   // found
      } else {
         cout << " --- " << i << " is not found." << endl; // not found.
      }
   }
   cout << "*** set data found view end ***" << endl;
}
※範囲指定が、値範囲、且つ、1データ検索終了で次範囲へインクリメントされるのが原因。
※イテレータを使用するか、データ範囲突合せなら同データ not found が出るまで検索が必要。

 取り合えずこの件は置いといて、multiset で重複データ存在時の「範囲 検索・抽出」を「再考」中、連想コンテナのメンバ関数とアルゴリズム にも同名で存在する equal_range() にぶち当たる。
 これが結構厄介物で辟易。以下その概要のメモ。

※重複データが存在しても lower_bound() upper_bound() で漏れなくイテレータ抽出参照可能である。

▲上へ [ 編集 ]

検索関連の「メンバ関数」と「アルゴリズム」


 何れも「連想コンテナ」の検索・抽出を前提とした覚え書ぎメモである。

lower_bound/upper_bound


 連想コンテナ(set,multiset,map,maltimap)のメンバ関数 lower_bound/upper_bound は、それぞれ指定値(value or value+1)の'開始位置'を'イテレータ'で返す。

lower_bound
※指定された値(キー)とそれ以上の値を含む開始イテレータ(位置)取得。
it_low = s.lower_bound(s.begin(), s.end(), value);
※検索・抽出範囲の先頭イテレータを取得する。
upper_bound
※指定された値(キー)より大きい値の開始イテレータ(位置)取得。
it_upp = s.upper_bound(s.bigin(), s.end(), value);
※検索・抽出範囲の先頭イテレータを取得する。

sample
//       --- 0 1 2 3 4 5 6 7 8 9 0 1 2 3 ---
// set s : { 0,1,1,2,3,3,3,4,5,5,6,7,8,9 }
it_l = s.lower_bound( 3 ); // s[4]  を示すイテレータ
it_u = s.upper_bound( 5 ); // s[10] を示すイテレータ


 lower_bound/upper_bound は、メンバ関数 同名の アルゴリズム が存在する。
example
it_low = s.lower_bound( value );                     // メンバ関数
it_low = s.lower_bound( s.begin(), s.end(), value ); // アルゴリズム
※アルゴリズムを使用するには、#include <algorithm> が必要。


▲上へ [ 編集 ]

equal_range


 他の検索・抽出関連関数と比較して、最も難解なのが equl_range である。
 但し、結果だけ見ると lower_bound / upper_bound の2つで取得するイテレータを同時に求めるだけのことである。
 その前段階の手続きが面倒なため難解に見える。

equl_range
※前提:int型 multiset データ。データ登録同時に昇順ソート済み。
※指定値のデータ範囲を pair型 イテレータで取得する。
010: void s_find(multiset<int>& s) {
020:    multiset< int >::iterator  itr;
030:    // equal_range() 専用戻値専用イテレータペアを作成
040:    typedef multiset<int>::iterator tdef_itr;        // 短縮記述
050:    pair< tdef_itr, tdef_itr > itr_pair;             // 難解!
060:    // multiset int データ全体から 値 15 の存在範囲を抽出
070:    itr_pair = equal_range(s.begin(), s.end(), 15 );
080:    // この時点で itr_pair.firs itr_pair.second に抽出範囲取得。
090: }
※重複データ数を得たい場合、081: へ次のコードを追加。
081:    printf("found %i ", (int)distance(itr_pair.first,itr_pair.second));
※distance() は、指定イテレータの相対的距離(個数)を返す。

 040〜070:equal_range() の戻り値が、抽出値範囲の「開始、終了」位置を返すと言うことで「関数が値を2つ返す???」・・・ことから、理解するのに半日以上掛かった。利用する側では戻り値2つだが、戻しているのは pair型1つなので、結局1個の値をリターンしているに過ぎない。

 070:で何を返している(指定地重複範囲のイテレータ pair)か理解できれば、取得されたイテレータを処理対象とすればよい。判ればさほどでも無いが・・・理解するまで苦しんだ。

 それから、メンバ関数とアルゴリズムで同名の関数が多数有る様子。使い方も異なるようで相当混乱しそうである。

▲上へ [ 編集 ]

binary_search


binary_serch
※検索対象データの存在チェック
sample
bool_f = binary_search(it_first, it_last, value);
※指定範囲(it_first~it_last)に、指定値(value)があれば true を返す。

▲上へ [ 編集 ]
2008年07月14日(月) 18:34:53 Modified by cafeboy1




スマートフォン版で見る

×

この広告は60日間更新がないwikiに表示されております。