map四種類の使い分け

今回はmapの４種類について。

map、unordered_map、multimap、unordered_multimapといった四つの種類がある。
mapとmultimapは木構造を用いているため自動でsortされる特徴がある。
unorder_mapとunordered_multimapは自動でハッシュを用いて値の検索用に作られている。(sortされない)

mapとunorder_mapは重複を許さず、(unique)
multimapとunordered_multimapは重複して値を持てる。(multi)

それぞれの機能は以下の通り。見るだけでは中々覚えづらかったのでコピーしてお試しあれ。

#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <utility>

using namespace std;

int main() {
    map<string, int>mp;//挿入するたびsort,unique,eraseが行われる
    mp["BB"] = 10;
    mp["AA"] = 20;
    mp["AA"] = 30;
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        cout << itr->first << ' ' << itr->second << endl;
    }
    cout << endl;

    unordered_map<string, int>ump;//挿入するたびunique,eraseが行われる
    ump["BB"] = 10;
    ump["AA"] = 20;
    ump["AA"] = 30;
    for (auto itr = ump.begin(); itr != ump.end(); itr++) {
        cout << itr->first << ' ' << itr->second << endl;
    }
    cout << endl;

    multimap<string, int>mmp;//挿入するたびsortが行われる
    mmp.insert(make_pair("BB", 10));
    mmp.insert(make_pair("AA", 20));
    mmp.insert(make_pair("AA", 30));
    for (auto itr = mmp.begin(); itr != mmp.end(); itr++) {
        cout << itr->first << ' ' << itr->second << endl;
    }
    cout << endl;

    unordered_multimap<string, int>ummp;//ハッシュバージョンのpair
    ummp.insert(make_pair("BB", 10));
    ummp.insert(make_pair("AA", 20));
    ummp.insert(make_pair("AA", 30));
    for (auto itr = ummp.begin(); itr != ummp.end(); itr++) {
        cout << itr->first << ' ' << itr->second << endl;
    }
    cout << endl;

    pair<string, int>pa[10];//pairが気になる方もいると思うので載せました。
    pa[0] = make_pair("BB", 10);
    pa[1] = make_pair("AA", 20);
    pa[2] = make_pair("AA", 30);
    for (int i = 0; i < 3; i++) {
        cout << pa[i].first << ' ' << pa[i].second << endl;
    }
}

ただ、競プロだとハッシュの危険性から普段は遠慮せずにmapを使い、O(1)を必要とする場合はunordered_mapを使うのが良さそう。
でもどれも色々な場面で使えそうなSTLで良い感じ。

mapを使えるC問題はこちら。
C - Good Sequence