C++のmapまとめてみた．

mapの概要

C++のmapはとてもよく使われる標準ライブラリコンテナの一つで，
「キーと値のペア」を管理するデータ構造です．

使い方

cpp

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

int main() {
    map<string, int> m;

    // 要素を追加
    m["apple"] = 3;
    m["banana"] = 5;
    m["orange"] = 2;

    // 要素にアクセス
    cout << m["apple"] << endl; // 出力: 3

    // 全要素をループ
    for (auto it = m.begin(); it != m.end(); ++it) {
        cout << it->first << " => " << it->second << endl;
    }

    // 要素の検索
    if (m.find("banana") != m.end()) {
        cout << "bananaは存在します" << endl;
    }

    return 0;
}

ポイントのまとめ

操作	方法
要素追加	m[key] = value;
要素取得	value = m[key];
要素削除	m.erase(key);
要素数取得	m.size();
すべてループ	for (auto& p : m) { p.first, p.second }
検索	m.find(key) != m.end()
全削除	m.clear();

詳しく

mapは自動的にキーの昇順に並びます（内部では赤黒木という木構造で管理）．
同じキーは2回入れられない（上書きされる）．
もし「同じキーを複数持ちたい」なら、multimapを使います．
挿入・検索はだいたい O(log N) の速さ．

例題

AtCoderABC394-Cより
頂点に1からNの，辺に1からMの番号がついたN頂点M辺の無向グラフが与えられます.
そのグラフが，自己ループや多重辺のない単純グラフになるためには，少なくとも何本の辺を取り除く必要があるか．

イメージ（頂点N=3，辺M=5で，入力の詳細は省略）

解説

回答.cpp

#include <iostream>
#include <map>
using namespace std;
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int N, M;
  cin >> N >> M;
  int ans = 0;
  map<pair<int, int>, int> m;
  for (int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    if (u == v) {
      ans++;
      continue;
    }
    if (u > v) swap(u, v);
    m[{u, v}]++;
  }
  for (auto& [edge, k] : m) ans += k - 1;
  cout << ans << "\n";
}

ここで，map< pair< int, int >, int > m;
は，keyがpair< int, int >であり，頂点1と頂点2をそれぞれ表している．
そのkeyに対応するvalueも同じく，intで指定されている．
つまり，map< keyの型, valueの型 > map名;
という形．

問題の解説としては，そのmapの中から，頂点1と頂点2が同じだった場合，つまり自己ループはans++をする．
また，

cpp

    if (u > v) swap(u, v);
    m[{u, v}]++;

ここでは，同方向のグラフを，カウントしている（（3,2)も（2,3）も同じだから）．
カウントしているというのは， m[{u, v}]++; のところ．
ここでは，key{u, v}に対するvalueである，m[{u, v}]を追加している．

公式の解説はこちら

補足

型	例
数値（int, double）	map< string, int >, map< int, double >
文字列（string）	map< int, string >
配列やベクター（vector）	map< int, vector< int >>
別のmapやset	map< int, map< int, int> みたいなネストもできる
自分で作ったクラスや構造体	map< int, MyClass > もOK