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;
}
※範囲指定が、値範囲、且つ、１データ検索終了で次範囲へインクリメントされるのが原因。※イテレータを使用するか、データ範囲突合せなら同データ 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 は、その構造上２つのデータをペアで管理する。この対になるペアデータを格納する 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 のように２つのデータがセットになった新しい型を提供している。pair型として宣言、代入、参照をサポートするクラスである。pair:表示サンプル
first=47 second=Clare 続行するには何かキーを押してください . . .※これだけの事だが、pair の宣言、代入、first/second 参照 まで知らなければ、map/multimap の次のステップに進めない。
▲上へ [ 編集 ]
map sample 2
sample 2
Ｃ言語系とは、思えないほどふざけた(？柔軟な…)配列名を使える。
#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 は、とっても便利！
▲上へ [ 編集 ]
リンク
内部リンク
- C/C++ C++/CLI C# 関連
- VC++ 2005 Express のインストール
- C/C++ の簡単なプログラム例
- C/C++ ソート（並べ替え）
- C/C++ テストの実行
- C/C++ STL(Standard Template Library)
- 変数・定数
- プログラムの分割/ダイナミックリンクライブラリ など
- その他
- C/C++ その他::書式文字/ESC code など
- VB2005リファレンス（覚え書き）
- SQL文：SQLステートメント
- VBA(VisualBasic for Applications)
外部リンク
- 現在ありません
▲上へ [ 編集 ]
覚え書き
試行錯誤
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;
}
※範囲指定が、値範囲、且つ、１データ検索終了で次範囲へインクリメントされるのが原因。※イテレータを使用するか、データ範囲突合せなら同データ 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 の２つで取得するイテレータを同時に求めるだけのことである。
その前段階の手続きが面倒なため難解に見える。
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() の戻り値が、抽出値範囲の「開始、終了」位置を返すと言うことで「関数が値を２つ返す？？？」・・・ことから、理解するのに半日以上掛かった。利用する側では戻り値２つだが、戻しているのは pair型１つなので、結局１個の値をリターンしているに過ぎない。
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