c++のSTLライブラリには、便利な set と map というデータ構造がある。
これらの違いや使い分けなどが曖昧になっていたため、自分なりにまとめてみたものを留めようと思う。

set とは

ユニークな(重複しない)データを格納するためのコンテナ
データ構造には平衡二分探索木(赤黒木)が採用されているため、O(log N)の時間計算量となる。
データ挿入時にソートされる。(デフォルトで昇順)
ユースケースとしては、あるデータの集合があった時、ユニークなもののみが欲しい時など。

set

// 英小文字からなる文字列中に含まれるユニークなアルファベットを取得する
string S = "abcdeadehn";

set<char> sc;
for(auto c: S) {
  sc.insert(c);
}

for(char c: sc) cout << c << ":" << sc.count(c) << endl;
// output:
// a:1
// b:1
// c:1
// d:1
// e:1
// h:1
// n:1

mapとは

<キー、値>のペアのうち、キーがユニークな(重複しない)データを格納するためのコンテナ
同じくデータ構造は平衡二分探索木であり、O(log N)の時間計算量となる。
データ挿入時にソートされる。(デフォルトで昇順)
ユースケースとしては、あるデータの集合があった時、各データの出現頻度をカウントする時など。

map

// 英小文字からなる文字列中に含まれる各アルファベットの出現頻度を取得する
string S = "abcdeadehn";

map<char, int> mci;
for(char c: S) {
  // mapでは、[]によるアクセス時にそのkeyが存在しないとvalueに指定した型に応じた値で初期化されてから処理が行われる。
  // int型の場合は0が初期値となるため、mci[c] = 0 の処理後 msi[c]++がなされる。
  mci[c]++;
}
    
for(auto m: mci) cout << m.first << ":" << m.second << endl;
// output:
// a:2
// b:1
// c:1
// d:2
// e:2
// h:1
// n:1

vectorでやると。。

ちなみに上記の例のようにデータの出現頻度のカウントは vector を用いても実現可能。

vector

string S = "abcdeadehn";

vector<int> v(26, 0);
for(auto c: S) {
  v[c - 97]++;
}
for(int i=0; i<26; i++) cout << (char)('a' + i) << ":" << v[i] << endl;
// output:
// a:2
// b:1
// c:1
// d:2
// e:2
// f:0
// g:0
// h:1
// i:0
// j:0
// k:0
// l:0
// m:0
// n:1
// o:0
...
// y:0
// z:0

しかし、出現しないアルファベットまで0を出力することになり、これを訂正しようとすると、0より大きいものをフィルターしたり、vectorに渡すデータ型を再考したりする必要がありそうだ。また、配列長を固定で持つところなども柔軟性に欠ける。
mapを用いることで、よりシンプルにこのような処理を記述できる。

vectorの方が適している場合もある

map[]によるアクセスにはO(log N)かかる。一方でvector[]によるアクセスはO(1)である。
N個のデータをmap, vectorにしたためることを考えると、それぞれO(N*log N)とO(N)である。
そのため、Nが大きいと結構な差になるため注意が必要だ。

vector_time

vector<int> v(n);
for(int i = 0; i < n; i++) {
    v[i] += i;
}

map_time

map<int, int> mp(n);
for(int i = 0; i < n; i++) {
    mp[i] += i;
}

上のコードで、N=10^3, 10^5, 10^7のときの差は以下の表のようになった。

N	10^3	10^5	10^7
vector	0ms	2ms	210ms
map	1ms	150ms	19524ms

データの集合に重複があるかの判定

set による実装

set_unique

string S = "thereisduplicate";

set<char> sc;
for(char c: S) {
  // 早期チェック
  if(sc.find(c) != sc.end()) {
    cout << "not unique";
  }
  sc.insert(c);
}

cout << (sc.size() == S.size() ? "unique" : "not unique") << endl; // output: not unique

データに重複がある場合、それを set に入れるとその分サイズは小さくなる。そのため 元のデータサイズ > set にした際のデータサイズ が真ならば重複がある。
データを set に挿入するとき、既に同じデータが set にあるかどうかをチェックする(set::find)。ただし find は O(log N) の時間計算量となるため、トータルで最悪時間計算量は O(Nlog N) となる。データ次第では1番目の判定の方が効率が良い場合もあればそうでない場合もあると思われる。¹

map による実装

map_unique

string S = "thereisduplicate";

map<char, int> mci;
for(char c: S) {
  mci[c]++;
  // 早期チェック
  if(mci[c] > 1) {
    cout << "not unique" << endl;
  }
}

cout << (mci.size() == S.size() ? "unique" : "not unique") << endl;

set 同様 元のデータサイズ > setにした際のデータサイズ が真ならば重複がある。
データを map に挿入した結果、そのキーの出現頻度が1を超える場合は重複がある。ただし[]オペレーターは O(log N) の時間計算量となるため、トータルで最悪時間計算量は O(Nlog N) となる。これも set と同様である。¹

set or map?

データ集合を扱う上で、単純にユニークかどうかに主眼が置かれる場合は set
それ以外は map

その他にもある set と map

multi系

multiset

データの重複を許された set

各データの出現頻度のカウント

multiset_frequency

string S = "qiitaissoawesome";

multiset<char> msc;
for(char c: S) msc.insert(c);

// multiset::upper_bound は、指定された値の次の要素へのイテレーターを返す。
// 指定値が複数あるときは、条件を満たす最後の値の次の要素を指す。
for(auto it = msc.begin(); it != msc.end(); it = msc.upper_bound(*it)) {
  cout << *it << " appears " << msc.count(*it) << " time(s)." << endl;
}
// output:
// a appears 2 time(s).
// e appears 2 time(s).
// i appears 3 time(s).
// m appears 1 time(s).
// o appears 2 time(s).
// q appears 1 time(s).
// s appears 3 time(s).
// t appears 1 time(s).
// w appears 1 time(s).

先の map による実装の方がシンプルである。

multimap

キーの重複を許された map

あるデータの出現位置の列挙

multimap_specify_position

string S = "qiitaissoawesome";

multimap<char, int> mmci;
for(int i = 0; i < S.size(); i++) mmci.insert({S[i], i});

auto rng = mmci.equal_range('i'); // key = 'i' の要素に対するイテレーターを取得
for(auto it = rng.first; it != rng.second; it++) {
  cout << it->first << " appears at pos:" << it->second << endl;
}
// output:
// i appears at pos:1
// i appears at pos:2
// i appears at pos:5

同様の結果が vector を用いても実現できる。

vector_specify_position

string S = "qiitaissoawesome";

vector<vector<int>> v(26);
for(int i = 0; i < S.size(); i++) v[S[i] - 97].push_back(i);

for(auto _v: v['i' - 97]) {
  cout << "i" << " appears at pos:" << _v << endl;
}
// output:
// i appears at pos:1
// i appears at pos:2
// i appears at pos:5

しかし、出現頻度のカウントの部分でも説明したように、この記述の仕方は柔軟性に欠ける。

unordered系

### unordered系 #### unordered_set set のソートされていないバージョン

データ構造としてハッシュテーブルが採用されており、O(1) のアクセスが可能。
データ挿入時にソートされない。
データの順序は問わず、速さが求められる場面で使用するのが良い。

unordered_map

map のソートされていないバージョン
特徴は unordered_set と同様。

例えばデータが巨大で、重複があるとすれば集合の最初の方に存在すると言うことが予めわかっている場合は、2 の方法の方が速いだろう。逆に集合の最後の方に重複が存在することが想定されるようなケースでは、1 の方法の速くなる可能性が高い。 ↩ ↩²