競プロのコンテスト中に参照する用として，std::map の使い方をまとめました．以下の記事と多少被ってるかもしれませんが，本記事は使い方に重きを置いています．
初期化，値の参照
例を見た方が早いので以下を参照してください．
#include <iostream> #include <string> #include <map> using namespace std; typedef long long ll; int main() { // 初期化 map<string, ll> mp = { {"Alice", 3}, {"Bob", 1}, {"Carol", 4} }; // 参照 cout << mp["Alice"] << "\n"; // 3 cout << mp["Bob"] << "\n"; // 1 return 0; }
要素の挿入 map::emplace
3 通りくらいありますが，それぞれ処理効率が違います．std::emplace が一番早いのでおすすめです．
- map[key] = value
- map::insert
- map::emplace
map::insert
map::insert は，
map.insert(make_pair(key, value))
のように呼び出します．std::pair が一時的に生成され，それがコピー，ムーブされて std::map に要素が格納されます．
map::emplace (推奨)
map::emplace は，
map.emplace(key, value)
のように呼び出します．std::pair ではなくvalue_type が取りうるコンストラクタ引数の値をカンマ区切りで渡します．要素が直接コンテナ内に構築され（コピーもムーブもされず）map::insert よりも効率的に要素が格納されます．
要素の生成がコンテナ内部で行われる，つまり，std::pair のコンストラクタ呼び出しがコンテナ内部で行われるということです．map::insert の場合は，コンテナ外部で一時オブジェクト生成のために std::pair のコンストラクタが呼ばれています．
まとめると，map::emplace は，要素の直接構築によりオブジェクトや一時オブジェクトの余計な生成やコピー，ムーブ処理，破棄処理が回避されるという利点があるということです．
用法
上記に挙げた 3 通りの方法で要素の挿入を行ってみました．
#include <iostream> #include <string> #include <map> using namespace std; typedef long long ll; int main() { // map[key] = value cout << "----- map[key] = value -----" << "\n"; map<string, ll> mp; mp["Alice"] = 3; mp["Bob"] = 1; mp["Carol"] = 4; auto begin = mp.begin(), end = mp.end(); for (auto itr = begin; itr != end; itr++) { cout << "key = " << itr->first << " " << "val = " << itr->second << "\n"; } mp.clear(); // map::insert cout << "----- mp.insert -----" << "\n"; mp.insert(make_pair("Bob", 1)); mp.insert(make_pair("Carol", 4)); mp.insert(make_pair("Alice", 3)); // 弱順序によりキーが整列されている auto begin1 = mp.begin(), end1 = mp.end(); for (auto itr = begin1; itr != end1; itr++) { cout << "key = " << itr->first << " " << "val = " << itr->second << "\n"; } mp.clear(); // 推奨：map::emplace cout << "----- RECOMMENDED: mp.emplace -----" << "\n"; mp.emplace("Bob", 1); mp.emplace("Carol", 4); mp.emplace("Alice", 3); // 弱順序によりキーが整列されている auto begin2 = mp.begin(), end2 = mp.end(); for (auto itr = begin2; itr != end2; itr++) { cout << "key = " << itr->first << " " << "val = " << itr->second << "\n"; } return 0; }
出力
----- map[key] = value ----- key = Alice val = 3 key = Bob val = 1 key = Carol val = 4 ----- mp.insert ----- key = Alice val = 3 key = Bob val = 1 key = Carol val = 4 ----- RECOMMENDED: mp.emplace ----- key = Alice val = 3 key = Bob val = 1 key = Carol val = 4
キーの検索 map::find
map::find
std::map に対して，あるキーが存在するかどうかは map::find で調べることができます．
map.find(key)
のように呼び出し，検索結果は以下のような形で返されます．
以上が std::map でのキーの検索の基本となります．
map::count
キーの検索には map::find が一般的ですが，map::count でも検索ができます．map::count はキーと一致する要素がコンテナ内にいくつ存在するかを調べるメンバ関数で，std::vector など他のコンテナクラスにも備わっています．
std::map の場合，キーは重複を許さないため map.count(key) では 0 or 1 のどちらかを返します．得られる情報は map::find の方が多いですね．
用法
両者の使用例を示しました．
#include <iostream> #include <string> #include <map> using namespace std; typedef long long ll; int main() { map<string, ll> mp; mp.emplace("Bob", 1); mp.emplace("Carol", 4); mp.emplace("Alice", 3); // mp.find auto iter = mp.find("Alice"); if (iter != mp.end()) { cout << "key: " << iter->first << ", value: " << iter->second << "\n"; } // mp.count size_t num = mp.count("Bob"); // num = 1 if (num > 0) { cout << "found" << "\n"; } else { cout << "not found" << "\n"; } return 0; }
出力
key: Alice, value: 3 found
ちなみに両者の計算量は，
- map::find：
- map::count：
となっています．要素数の対数オーダーでキーの検索ができます．
キーを探すだけなら要素のイテレータが返ってくる map::find 一択かと思います（map.count は使い所あるんでしょうか．std::vector とかなら使い道がありそうですが．もし知ってる方いたらコメントお願い致します）．
発展：キーに対する二分探索
二分探索の記事で少し触れましたが，std::map には二分探索のための map::lower_bound，map::upper_bound の二つのメンバ関数が定義されています．それぞれ，
という，キーを二分探索できるメンバ関数です（map[key] = value となる key の方を探索します）．キーが見つからない場合は map::find 同様 map 末尾のイテレータを返します．
使用例を下記に示しました．
#include <iostream> #include <string> #include <map> using namespace std; typedef long long ll; int main() { map<string, ll> mp; mp.emplace("B", 1); mp.emplace("C", 4); mp.emplace("A", 3); mp.emplace("D", 5); // A 以上，D以下の範囲を取得 auto begin = mp.lower_bound("B"); // "B" 以上のキー auto last = mp.upper_bound("D"); // "D" より大きいキー // begin: "B" 以上のキー，"B" が存在するためそのイテレータが返ってくる // last: "D" より大きいキーは存在しないため，last = mp.end() が返ってくる while (begin != last) { cout << "key: " << begin->first << ", value: " << begin->second << "\n"; begin++; } return 0; }
出力
key: B, value: 1 key: C, value: 4 key: D, value: 5
二分探索ができるのは，std::map の key が平衡二分木によって順序つけられているからです．詳しくはこちらをご覧ください．
注意点：std::lower_bound と map::lower_bound
std::map でキーの二分探索をするときの注意点を挙げます．
std::map のメンバ関数の map::lower_bound と std::lower_bound（STL の algorithm）という関数はどちらも C++ 標準ライブラリの二分探索を行うための関数ですが，内部で比較するオブジェクトの構造が違うため，どのコンテナに適用するかで計算量が変わってきます．
これに関しては私の過去の記事に一度まとめていますが，大事なことなので本記事で再掲させていただきます（以下の記事で言及しています）．
std::map に対して std::lower_bound(map.begin(), map.end(), key) としても計算量は線形時間 になってしまいます．std::map のキーに対しては
map.lower_bound(key) とメンバ関数を呼び出す必要があり，この場合計算量は入力の対数オーダー となり二分探索の特性（計算量）が生かされます．
std::lower_bound だと線形時間になってしまう理由は以下の通りです（std::set に関する説明ですが std::map とデータ構造は大体同じです）．
std::lower_bound() の計算時間が対数オーダーになるためには，渡すものがランダムアクセス可能なもの（配列，std::vector）である必要があり，ランダムアクセス可能でない構造の std::set （内部は平衡二分木）を渡すと対数オーダーにならなくてなってしまいます．
二分探索の基本に関して過去の記事でまとめていますので良かったらご覧ください．
例題
最後に，std::map の使い方を復習するために AtCoder の問題を載せておきます．map::find, map::emplace，要素へのアクセスを一通り確認できると思います（私の解答が最適と言うわけではありません）．
終わりに
最後まで読んでくださりありがとうございました．色々な関数を覚えるのが苦手なのでこれからもこういった覚書を増やしていきたいなと思います．間違い，ご指摘等あればコメント，Twitter のリプライ等でご連絡ください．
