C++コンテナ(四):mapタイプ

mapタイプmapは、キー値ペアの集合です.mapタイプは、通常、関連配列として理解されます.組み込み配列タイプと同様に、キーを下付き文字として使用して値を取得できます.関連付けの本質は、要素の値が配列内の要素の位置で取得されるのではなく、特定のキーに関連付けられることです.mapオブジェクトを使用するには、mapヘッダファイルを含める必要があります.

#include <map>

mapオブジェクトを定義する場合は、キーと値のタイプを指定する必要があります.

map<string, int> wordCount; // empty map from string to int

1mapオブジェクトのコンストラクション関数
操作
意味map<k, v> m mという名前のmapオブジェクトを作成します.そのキーと値のタイプはそれぞれkとvです.map<k, v> m(m2) m2のコピーmを作成します.mとm2は同じキータイプと値タイプを持つ必要があります.map<k, v> m(b, e) mapタイプのオブジェクトmを作成し、反復bおよびeタグ範囲内のすべての要素のコピーを格納します.要素のタイプはpair<const k, v>に変換できる必要があります.
キータイプの場合、唯一の制約は<操作をサポートする必要があります.他の関係や等しい演算をサポートするかどうかは、要求されません.
2map定義のタイプ
キータイプ、値タイプ、およびキー値(pair)タイプが含まれます.
を選択します.
意味map<k, v>::key_type mapコンテナで、インデックスとして使用されるキーのタイプmap<k, v>::mapped_type mapタイプで、キーに関連付けられた値のタイプmap<k, v>::value_type pairタイプ.first要素はconst map<k, v>::key_typeタイプを有し、secondはmap<k, v>::mapped_typeタイプである.

map反復器を参照解除すると、pairタイプのオブジェクト

が生成されます.
反復器を参照解除すると、コンテナのvalue_typeタイプ値を指す参照が得られます.

map<string, int>::iterator map_it = wordCount.begin();
// *map_it is a reference to a pair<const string, int> object
cout << map_it->first << " " << map_it->second << endl; // print the key and value of the element

map_it->first = "new key"; // error: key is const type
++ map_it->second; // ok: we can change value through the iterator

3mapに要素を追加mapにキー値要素ペアを追加するには、下付きオペレータで要素を取得し、取得した要素に値を付与する方法と、insertメンバー関数を使用して実装する方法の2つがあります.
3.1下付きアクセスmapオブジェクトの使用
次のプログラムを作成する場合:

map<string, int> wordCount; // empty map
// insert default initialized element with key "Anna"; then assign 1 to its value
wordCount["Anna"] = 1;

次のことが起こります.

wordCountで検索キーがAnnaの要素で見つかりませんでした.

新しいキー値ペアをwordCountに挿入します.そのキーはconst stringタイプのオブジェクトであり、Annaを保存します.値は初期化され、この例では値が0であることを意味します.

この新しいキー値ペアをwordCountに挿入する.

挿入された新しい要素を読み込み、その値を1にします.

下付きオペレータ戻り値の使用

通常、下付きオペレータは左の値を返します.返される左の値は、特定のキーに関連付けられた値です.

cout << wordCount["Anna"] <<endl;  // fetch element indexed by Anna; ptint 1
++ wordCount["Anna"];              // fetch the element and add one to it
cout << wordCount["Anna"] << endl; // fetch element and print it; print 2

vectorまたはstringタイプとは異なり、map下付きオペレータが返すタイプは、map反復器を逆参照して得られるタイプとは異なる.

下書き行為のプログラミング意義

mapコンテナの場合、下付きのキーがコンテナに存在しない場合は、新しい要素を追加します.この特性は、プログラムを驚くほど簡潔にすることができます.

// count the number of times each word occurs in the input
map<string, int> wordCount; // empty map from string to int
string word;
while ( cin >> word )
    ++ wordCount[word];

このプログラムは、各単語の出現回数を記録するためのmapオブジェクトを作成し、whileループは標準入力から1つの単語を読み出すたびに、新しい単語である場合はwordCountにその単語をインデックスとする新しい要素を追加し、読み込まれた単語がmapオブジェクトにすでに存在する場合は、対応する値に1を加算する.
3.2insertメンバー関数mapコンテナのinsertメンバーはシーケンスコンテナと似ていますが、キーの役割を考慮する必要があります.
操作
意味m.insert(e) eは、mに使用されるvalue_typeタイプの値です.キー(e.first)がmにない場合は、e.secondの値を持つ新しい要素を挿入します.キーが既にmに存在する場合、mは保持されます.この関数は、pairを指す要素を含むe.first反復器と、mapを挿入したかどうかを示すオブジェクトを含むboolタイプのオブジェクトを返します.m.insert(begin, end) beginおよびendは、要素範囲をマークする反復器であり、要素はm.value_typeタイプのキー値ペアでなければならない.この範囲内のすべての要素について、そのキーがmに存在しない場合、そのキーとその関連する値をmに挿入します.戻りvoidタイプm.insert(iter, e) eは、mに使用されるvalue_typeタイプの値です.キー(e.first)がmにない場合、新しい要素が作成され、反復器iterを起点として新しい要素が格納されている場所が検索されます.mの所与のキーを持つ要素を指す反復器を返します.

以insert为下标演算

下付きmapコンテナを使用して新しい要素を追加すると、要素の値部分が値初期化されます.通常、同じオブジェクトを初期化して値を割り当てます.insert構文はよりコンパクトです.

// if Anna not already in wordCount, inserts new element with value 1
wordCount.insert( map<string, int>::value_type("Anna", 1) );

このinsert関数バージョンの実パラメータ:

map<string, int>::value_type("Anna", 1)

は、新しく作成されたpairオブジェクトで、mapコンテナに直接挿入されます.しかしinsertに伝達される実パラメータはかなり不器用で、2つの方法で簡略化することができる.

// first
wordCount.insert( make_pair("Anna", 1) );

// second
typedef map<string, int>::value_type valueType;
wordCount.insert( valueType("Anna", 1) );

前述したように、下付きオペレータを使用して入力された単語を統計することは、insertメンバー関数と同様に実現できます.

// count number of times each word occurs in the input
map<string, int> wordCount; // empty map from string to int
string word;
while ( cin >> word )
{
    // insert element with key equal to word and value 1
    // if word already in wordCount, insert does nothing
    pair<map<string, int>::iterator, bool> ret = 
        wordCount.insert(make_pair(word, 1));
    if ( !ret->second )       // word already in wordCount
        ++ ret.first->second; // increment counter
}

ここで使用するキー値pairパラメータ付きinsertバージョンは、反復器とbool値を含むpairオブジェクトを返します.反復器はmapに対応するキーを持つ要素を指し、bool値は要素が挿入されているかどうかを示します.キーが既にコンテナ内にある場合、関連する値はそのままであり、返されるboolの値はfalseである.キーがコンテナにない場合は、新しい要素が挿入され、boolの値はtrueです.各単語について、insertを試み、その値を1に割り当てます.if文検出insert関数は値を返し、値がfalseであれば挿入操作をしていないことを示す.wordに従ってインデックスされた要素がwordCountにすでに存在し、その要素に関連付けられた値に1を加算します.
4map要素の検索と読み込み
下付きオペレータは、値を読み込む最も簡単な方法を示します.

map<string, int> wordCount;   // empty map from string to int
int occurs = wordCount["Anna"];

ただし、このメソッドには、mapコンテナにキーが存在しない場合、下付き操作によってキーを持つ新しい要素が挿入されます.ほとんどの場合、ある要素が存在するかどうかを知りたいだけで、その要素が存在しない場合、挿入演算を行うつもりはありません.このため、mapコンテナが提供する2つの動作は、この問題を解決することができる.
操作
意味m.count(k)
戻りm中kの出現回数m.find(k) mコンテナにkインデックス付き要素が存在する場合、その要素を指す反復器が返されます.存在しない場合、戻りはエンド反復器を超えています.

// count()
int occurs(0);
if ( wordCount.count("Anna") )
    occurs = wordCount["Anna"];

// find()
int occurs(0);
map<string, int>::iterator iter = wordCount.find("Anna");
if ( iter != wordCount.end() )
    occurs = iter->second;

5mapオブジェクトから要素を削除
操作
意味m.erase(k) mの中ボタンがkの要素を削除します.削除された要素の数を示すsize_typeタイプの値を返します.m.erase(p) mから反復pが指す要素を削除します.pは、mに確かに存在する要素を指し示さなければならず、m.end()に等しくはならない.戻りvoidタイプm.erase(b, e) mから、反復器対bおよびeによってマークされる範囲内の要素を削除します.bおよびeは、mの有効範囲をマークする必要があります.すなわち、bおよびeは、いずれもmの要素または最後の要素の次の位置を指します.また、bおよびeは等しいか(この場合削除範囲は空)、またはbが指す要素はeが指す要素の前に表示されなければならない.戻りvoidタイプ

// erase of a key returns number of elements removed
if ( wordCount.erase( removalWord ) )
    cout << "ok: " << removalWord << " removed!" << endl;
else
    cout << "oops: " << removalWord << " not found!" << endl;

6対mapオブジェクトの反復ループ

// get iterator positioned on the first element
map<string, int>::const_iterator iter = wordCount.begin();

// for each element in the map
while ( iter != wordCount.end() )
{
    // print the element key, value pairs
    cout << iter->first << " occurs " << iter->second << " times." << endl;
    ++ iter; // increment iterator to denote the next element
}

参考文献:

『C++Primer中国語版(第4版)』,Stanley B.Lippman et al.著,人民郵電出版社,2013.