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番目の判定の方が効率が良い場合もあればそうでない場合もあると思われる。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 と同様である。1
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
しかし、出現頻度のカウントの部分でも説明したように、この記述の仕方は柔軟性に欠ける。