C++：std::map の基礎 - pyてよn日記

map の概要
map のデータ構造：2分木
mapの宣言と値の設定・取り出し
map の全てのキーを取り出す
AtCoder：mapを使った基本的な問題
参考

　C++の標準ライブラリ（STL）std::map の基本的な使い方まとめ．競プロで使いそうなところをピックアップした．

map の概要

　map*1 は「連想配列クラス」と呼ばれ，検索可能なキーと，キーに対応する値の組（ペア）を要素とするコンテナクラスで，保持している要素から、キーを指定して値を高速に取り出せるクラスのことである．#include <map>と記述することにより map クラスが使えるようになる．いわゆる連想配列である．Python 使用者は Python の辞書型のようなものだと思ってもらえば良い．

　単純な配列を使ってキーから要素を取得する処理時間は $O(N)$ であるが，map は各要素が 2 分木により順序付けられているため（データ構造を参照），キーから要素を取得する計算量は $O(log N)$ と高速である．

map のデータ構造：2分木

　map のデータ構造は以下の図のようになっている．

f:id:pytwbf201830:20190101211251p:plain:w350:h400 — map: data structure

C++ 連想配列クラス std::map 入門より引用

　データ構造の要点は以下の3つ．

各ノードにはキーと値のペアが入っており，左右の子供ノードへのポインタを持つ．
左の子供のキー＜キー＜右の子供のキー，という条件が成立している．
ノードの深さは概ね等しく，木がバランスしている．

　上記の構造により，キーに一致するノードをルートから二分探索することが可能なため，探索速度が $O(log N)$ と高速になる．二分探索自体は map クラスが内部で勝手にやってくれるため、使う側は特にこれを意識することはない．

mapの宣言と値の設定・取り出し

　map<key, value> mp;で，キーとそれに対応させる値のデータ型を指定して map クラスを宣言する．値の設定・取り出しには [] 演算子が使える．

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

int main() {
    map<string, int> mp;
    mp["apple"] = 6;
    mp["banana"] = 4;
    cout << mp["apple"] << "\n";
    cout << mp["banana"] << "\n";
    
    return 0;
}

map の全てのキーを取り出す

　先頭・最後尾の要素のイテレータを，mp.begin()，mp.end() で取得できる．全てのキーを取得するには，イテレータを利用して map の要素を一つずつ取り出す．取り出した要素のキー・値にはそれぞれ iter->first，iter->second でアクセスできる．-> は，ポインタからクラスのメンバ変数にアクセスするための演算子．

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

int main() {
    map<string, int> mp;
    mp["apple"] = 3;
    mp["banana"] = 1;
    mp["grape"] = 4;
    
    auto begin = mp.begin(), end = mp.end();
    for (auto iter = begin; iter != end; iter++) {
        // first: key, second: value
        cout << "key = " << iter->first << "\n";
        cout << "value = " << iter->second << "\n";
    }
    
    return 0;
}