multisetは、要素を自動的にソートして格納することができるコンテナであり、重複した要素も格納することができます。
本記事では、multisetの基本的な使い方から応用的な使い方までをサンプルコードを交えてわかりやすく解説します。
multisetとは
multisetは、C++のSTL(Standard Template Library)に含まれるコンテナの一つです。
setと同様に、要素を順序付けされた状態で格納することができますが、setと異なり同じ値を複数格納することができます。
multisetは、赤黒木(Red-Black Tree)と呼ばれるデータ構造を用いて実装されています。
このデータ構造により、要素の挿入・削除・検索をO(log n)の時間計算量で行うことができます。
また、multisetはイテレータをサポートしており、範囲指定や逆順指定なども可能です。
次の見出しでは、multisetの使い方について詳しく解説します。
multisetの使い方
まずは、multisetの宣言方法や要素の追加・削除方法、要素の取得方法などについて解説します。
multisetの宣言
multisetを使用するためには、以下のように宣言します。
#include <set>
std::multiset<int> mySet;
上記の例では、int型を格納するmultisetを作成しています。
multisetへの要素の追加
multisetへ要素を追加するには、insert()
関数を使用します。
#include <iostream>
#include <set>
int main() {
std::multiset<int> mySet;
mySet.insert(1);
mySet.insert(2);
mySet.insert(3);
return 0;
}
上記の例では、1, 2, 3という値を持つ要素が順番に追加されます。また、同じ値でも重複して追加されます。
multisetの要素の取得
multisetから要素を取得する方法としては、イテレーター(反復子)を使用する方法があります。
begin()関数で先頭位置(最小値)へ移動しnext()関数で次々とアクセスしていくことが出来ます。
for (auto itr = mySet.begin(); itr != mySet.end(); ++itr) {
std::cout << *itr << std::endl;
}
1
2
3
上記の例では、全ての要素を順番に表示します。
配列のようにmySet[2]
のようにアクセスして要素を取得することはできないので注意してください。
multisetから要素の削除
multisetから要素を削除するには、erase()
関数を使用します。
#include <iostream>
#include <set>
int main() {
std::multiset<int> mySet;
mySet.insert(1);
mySet.insert(2);
mySet.insert(3);
mySet.erase(2);
for (auto itr = mySet.begin(); itr != mySet.end(); ++itr) {
std::cout << *itr << std::endl;
}
return 0;
}
1
3
上記の例では、値が2である要素が削除されます。
mySet.erase(2)
は2番目の要素を削除するという意味ではなく、値が2の要素を削除するという意味なので注意!
同じ値が複数存在する場合は、見つかったすべての要素が削除されます。
multisetの要素数を調べる
multiset内に格納されている要素数はsize()
関数で調べることが出来ます。
std::cout << "size: " << mySet.size() << std::endl;
3
上記の例では、size:
という文字列と共に現在格納されている要素数が表示されます。
multiset内で特定の値を検索する
特定の値がmultiset内に存在するかどうか調べる場合はcount()
関数やfind()
関数などが利用可能です。
count()
関数は指定した値と等しいもしくはそれ以上大きな値が何個あるかカウントし返り値として返すためbool型で値を受け取れます。
また、find()
関数は指定した値と等しいもしくはそれ以上大きな最初に見つかったイテレーター(反復子)オブジェクトを返すため、コードがシンプルになるauto型で取得するのが一般的です。
#include <iostream>
#include <set>
int main() {
std::multiset<int> mySet;
mySet.insert(1);
mySet.insert(2);
mySet.insert(3);
if (mySet.count(2)) {
std::cout << "2が見つかりました" << std::endl;
}
else {
std::cout << "2が見つかりませんでした" << std::endl;
}
auto itr = mySet.find(3);
if (itr != mySet.end()) {
std::cout << "3が見つかりました: " << *itr << std::endl;
}
else {
std::cout << "3が見つかりませんでした" << std::endl;
}
return 0;
}
2が見つかりました
3が見つかりました: 3
上記例では、2が見つかりました
3が見つかりました: 3
と表示されます。count
やfind
メソッドを使えばわざわざ関数を自作する必要はありません。