C++の標準ライブラリでsetとmapを扱う - プログラミング原人の進化論

C++のSTLで提供されている、setとmapについてメモしておきます。
STLでは複数の要素を扱うコンテナを提供しています。要素の順番の決め方によって、コンテナはシーケンスコンテナと連想コンテナの２つに分類されます。シーケンスコンテナは要素の値に関係なく、追加されたタイミングなどによって要素の位置が決定されます。一方、連想コンテナでは何らかの基準に従って要素がソートされています。setとmapは連想コンテナに分別されます。
要素がソートされていることによって、連想コンテナは高速な二分探索を利用できるという利点があります。

set

setは要素に重複がない連想コンテナです。数学における集合に似ています。要素のソートは要素の持つ値によって行われています。
次のような次のようなメソッドを持ちます。

size()	要素数を返す
clear()	空にする
begin()	先頭を指すイテレータを返す
end()	末尾を指すイテレータを返す
insert(key)	要素keyを挿入
erase(key)	要素keyを削除
find(key)	要素keyへのイテレータを返す。なければend()を返す

例：

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

// setの要素を先頭から順に表示する関数
void print(set<int> s) {
  for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
    cout << *it << " ";
  }
  cout << endl;
}

int main() {
  set<int> s;

  for (int i = 0; i < 5; i++) {
    s.insert(i);
  }

  print(s);  // 0 1 2 3 4

  s.erase(4);
  print(s);  // 0 1 2 3

  s.insert(3);
  print(s);  // 0 1 2 3

  cout << *s.find(1) << endl;  // 1

  return 0;
}

実行結果：

map

mapは各要素がキーと値を持ち、キーによってソートされている連想コンテナです。
次のようなメソッドを持ちます。

size()	要素数を返す
clear()	空にする
begin()	先頭を指すイテレータを返す
end()	末尾を指すイテレータを返す
insert*1	キーkey、値valueの要素を挿入
erase(key)	要素keyを削除
find(key)	要素keyへのイテレータを返す。なければend()を返す

setとおおよそ同じですね。insetメソッドはキーと値の両方を指定する必要があります。要素はstd::pairで保持することに注意。キーと値のペアはmake_pairという関数を利用して指定します。

例：

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

// マップmの要素を順番に表示
void print(map<string, int> m) {
  pair<string, int> item;
  for (map<string, int>::iterator it = m.begin(); it != m.end(); it++) {
    item = *it;
    cout << item.first << ": " << item.second << endl;
  }
  cout << endl;
}

int main() {
  map<string, int> m;  // キー：string型, 値：int型

  // 異なる方法で要素を加える
  m["Math"] = 60;
  m["Science"] = 65;
  m["Latin"] = 75;

  cout << "size: " << m.size() << endl;
  print(m); 

  m.erase("Latin");

  cout << "size: " << m.size() << endl;
  print(m);

  return 0;
}

実行結果：

size: 3
Latin: 75
Math: 60
Science: 65

size: 2
Math: 60
Science: 65

まとめ

setとmapについて勉強しました。うまい具合に使い分けたいところです。イテレータにだんだん慣れてきた。

参考

make_pair - cpprefjp C++日本語リファレンス
渡部有隆. プログラミングコンテスト攻略のためのアルゴリズムとデータ構造. Ozy, 秋葉拓哉協力. 株式会社マイナビ. 2015.

*1:key, value