C++ でのセットとハッシュセット
C++ のセットは、データ要素を格納し、必要に応じてそれらを取得するためのコンテナとして機能します。同様に、ハッシュセット、より正確には、C++ の unordered_set は、データ要素を格納するセットと同様の目的を果たします。
この記事では、set と unordered_set について詳しく説明します。
C++ でのセットとハッシュセット
set はデータ要素を格納するために使用される連想コンテナですが、unordered_set は将来のニーズのためにデータ要素を格納するために使用される連想コンテナでもあります。では、これらのデータ構造はどちらも、ベクトル、マップ、その他のコンテナオブジェクトとどのように異なりますか？
答えは簡単です。set と unordered_set は一意のデータ要素を格納します。
したがって、重複する要素は許可されません。ただし、ベクトルやマップなどの他のデータ構造でも、重複する要素を保存できます。
これらのデータ構造は両方とも、C++ 標準テンプレートライブラリにあります。
ここで、C++ で set と unordered_set を使用するタイミングについて簡単に説明したので、次にそれらを詳細に理解しましょう。
C++ でのセット
前に説明したように、セットは、一意のデータ要素を並べ替えられた方法で格納する連想コンテナです。ただし、ランダムな順序でそれらを保存できますが、セットからそれらを取得するとすぐに、ソートされた方法でのみ要素が返されます。
したがって、セットには、ユーザーから非表示のデータ要素を並べ替えるための定義が含まれています。
C++ のセットは、二分探索木として実装されています。したがって、それらは注文されます。さらに、要素の検索には O(log n) の時間がかかります。
C++ でセットを実装する方法を見てみましょう。
#include <iostream>
#include <set>
using namespace std;
int main() {
int a[] = {4, 8, 3, 6, 9, 8, 1, 3, 3};
int size = sizeof(a) / sizeof(a[0]);
set<int> s;
for (int i = 0; i < size; i++) {
s.insert(a[i]);
}
set<int>::iterator i;
for (i = s.begin(); i != s.end(); i++) {
cout << *i << " ";
}
}
出力：
1 3 4 6 8 9
したがって、上記のコード例でわかるように、配列に格納されている要素はランダムな順序であり、重複する要素が含まれています。ただし、それらがセット s に格納されるとすぐに、それらは内部でソートされ、重複する要素も削除されます。
したがって、出力は重複のないソートされた要素のグループです。
C++ のハッシュセット
unordered_set または C++ のハッシュセットはどちらも同じ意味です。この unordered_set は、一意のデータ要素を格納するためにも使用されますが、set と unordered_set の唯一の違いは、unordered_set には、set が格納するときに要素が格納される順序がないことです。ソートされた順序で要素。
この unordered_set も重複する要素を保存しません。ただし、これらはハッシュテーブルを使用して実装されます。
挿入される要素はキーとも呼ばれ、ハッシュテーブルのインデックスにハッシュされ、その特定のインデックスに格納されます。
要素はランダムな順序で格納されるため、要素の取得には O(1) 時間がかかり、検索操作の実装が高速になります。
C++ で unordered_set を使用する例を見てみましょう。
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
int a[] = {4, 8, 3, 6, 9, 8, 1, 3, 3};
int size = sizeof(a) / sizeof(a[0]);
unordered_set<int> s;
for (int i = 0; i < size; i++) {
s.insert(a[i]);
}
unordered_set<int>::iterator i;
for (i = s.begin(); i != s.end(); i++) {
cout << *i << " ";
}
}
出力：
1 9 6 3 8 4
したがって、上記のコード例でわかるように、要素はセット内で任意のランダムな順序で格納されます。ただし、セットから返される要素もランダムな順序ですが、重複する要素はすべて削除され、一意の要素のみがユーザーに返されます。
C++ でのセットとハッシュセットの主な違い
setsは要素を昇順で格納するために使用されますが、unordered_setは要素を順不同で格納します。setsはバイナリ検索ツリーを使用して実装されますが、unordered_setはハッシュテーブルを使用して実装されます。setでの検索操作は、要素の検索にO(log n)の時間がかかりますが、unordered_setの要素の検索にはO(1)の時間がかかります。setsは#include<set>ヘッダーファイルにインクルードされますが、unordered_setは#include<unordered_set>ヘッダーファイルを使用してインクルードされます。
まとめ
この記事では、C++ のセットと hashset について説明しました。これらのデータ構造は両方とも C++STL に存在し、一意のデータ要素を格納するために使用されます。
ただし、この 2つの主な違いは、set はソートされた要素のセットを返すのに対し、unordered_set はデータ要素を順序なしで返すことです。
2つのうちのいずれかを使用できますが、unordered_set では検索操作が高速であり、要素の検索にほぼ一定の時間がかかります。したがって、それが好ましい。