46. ハッシュセット¶
重複のない集合を扱うデータ構造、ハッシュセットについて学びます。
46.1 HashSet の概要¶
HashSet<Key>は、C++ 標準のstd::unordered_set<Key>に相当するクラスです- 要素が重複しない集合を扱うためのコンテナです
- 要素の追加、削除、検索を高速に行えます
46.1.1 基本的な特徴¶
- 要素は一意です。同じ要素は重複しません
- ハッシュを使って実装されています
- 要素の順序は保証されません（指定した順序やソートができません）
- 要素の追加、削除、検索の平均的な計算量は O(1) （要素数によらずほぼ一定）で、非常に高速です
46.1.2 主な操作¶
| コード | 説明 | 計算量 |
|---|---|---|
.insert(key) |
要素を追加する（すでに存在する場合は何もしない） | O(1) |
.erase(key) |
指定した要素を削除する（存在しない場合は何もしない） | O(1) |
.contains(key) |
指定した要素が存在するかを返す | O(1) |
.size() |
要素数を返す | O(1) |
.empty() |
要素数が 0 であるかを返す | O(1) |
.clear() |
すべての要素を削除する | O(N) |
.begin(), .end() |
先頭・終端位置のイテレータを返す | O(1) |
46.2 ハッシュセットの作成¶
HashSetは次のような方法で作成します- 空のハッシュセットを作成
- 初期化リストから作成
- 別のコンテナから作成
- 空のハッシュセットを作成し、要素を追加
# include <Siv3D.hpp>
void Main()
{
// 空のハッシュセットを作成
{
HashSet<int32> hs;
Print << hs.size();
Print << hs;
}
// 初期化リストから作成
{
HashSet<int32> hs = { 3, 1, 4, 1, 5 };
Print << hs.size();
Print << hs;
}
// 別のコンテナから作成
{
const Array<int32> a = { 3, 1, 4, 1, 5 };
HashSet<int32> hs(a.begin(), a.end());
Print << hs.size();
Print << hs;
}
// 空のハッシュセットを作成し、要素を追加
{
HashSet<int32> hs;
hs.insert(3);
hs.insert(1);
hs.insert(4);
hs.insert(1); // 重複しているので無視される
hs.insert(5);
Print << hs.size();
Print << hs;
}
while (System::Update())
{
}
}
46.3 要素数の取得¶
.size()はハッシュセットの要素数をsize_t型で返します
# include <Siv3D.hpp>
void Main()
{
{
HashSet<int32> hs;
Print << hs.size();
}
{
HashSet<String> hs = { U"C", U"C++", U"Java" };
Print << hs.size();
}
while (System::Update())
{
}
}
46.4 空であるかを調べる¶
.empty()はハッシュセットが空であるか（要素数が 0 であるか）をbool型で返します
# include <Siv3D.hpp>
void Main()
{
{
HashSet<int32> hs;
Print << hs.empty();
}
{
HashSet<String> hs = { U"C", U"C++", U"Java" };
Print << hs.empty();
}
while (System::Update())
{
}
}
46.5 要素の追加¶
.insert(key)で要素を追加します- すでに同じ要素が存在する場合は、何もしません
- 戻り値は
std::pair<iterator, bool>で、要素の追加に成功した（同じ要素が存在しなかった）場合、.secondがtrueになります
# include <Siv3D.hpp>
void Main()
{
HashSet<int32> hs = { 3, 1, 4 };
if (hs.insert(1).second)
{
Print << U"1 added";
}
else
{
Print << U"1 already exists";
}
if (hs.insert(5).second)
{
Print << U"5 added";
}
else
{
Print << U"5 already exists";
}
while (System::Update())
{
}
}
46.6 指定した要素の存在チェック¶
.contains(key)で指定した要素が存在するかを調べます- 存在する場合は
trueを、存在しない場合はfalseを返します
# include <Siv3D.hpp>
void Main()
{
{
HashSet<int32> hs = { 3, 1, 4, 1, 5 };
Print << hs.contains(3);
Print << hs.contains(2);
}
{
HashSet<String> hs = { U"C", U"C++", U"Java" };
Print << hs.contains(U"C");
Print << hs.contains(U"Python");
}
while (System::Update())
{
}
}
46.7 範囲 for 文による要素の列挙¶
- 範囲 for 文を使って、ハッシュセットのすべての要素にアクセスします
- 要素はコンピュータにとって都合のよい並び方で格納されるため、順序は保証されません
- 各要素へのアクセスは const 参照で行います
- 範囲 for 文の中で、対象のハッシュセットのサイズを変更する操作は行わないでください
# include <Siv3D.hpp>
void Main()
{
HashSet<String> hs = { U"C", U"C++", U"Java" };
hs.insert(U"Python");
for (const auto& elem : hs)
{
Print << elem;
}
while (System::Update())
{
}
}
46.8 要素の削除¶
.erase(key)で指定した要素を削除します- 指定した要素が存在しない場合は、何もしません
# include <Siv3D.hpp>
void Main()
{
HashSet<int32> hs = { 3, 1, 4, 1, 5 };
hs.erase(1);
hs.erase(2);
Print << hs;
while (System::Update())
{
}
}
46.9 すべての要素の削除¶
.clear()でハッシュセットのすべての要素を削除します