C++ でのセットとハッシュセット

1. C++ でのセットとハッシュセット
2. C++ でのセット
3. C++ のハッシュセット
4. C++ でのセットとハッシュセットの主な違い
5. まとめ

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++ でのセットとハッシュセットの主な違い

1. sets は要素を昇順で格納するために使用されますが、unordered_set は要素を順不同で格納します。
2. sets はバイナリ検索ツリーを使用して実装されますが、unordered_set はハッシュテーブルを使用して実装されます。
3. set での検索操作は、要素の検索に O(log n) の時間がかかりますが、unordered_set の要素の検索には O(1) の時間がかかります。
4. sets は #include<set> ヘッダーファイルにインクルードされますが、unordered_set は #include<unordered_set> ヘッダーファイルを使用してインクルードされます。

まとめ

この記事では、C++ のセットと hashset について説明しました。これらのデータ構造は両方とも C++STL に存在し、一意のデータ要素を格納するために使用されます。

ただし、この 2つの主な違いは、set はソートされた要素のセットを返すのに対し、unordered_set はデータ要素を順序なしで返すことです。

2つのうちのいずれかを使用できますが、unordered_set では検索操作が高速であり、要素の検索にほぼ一定の時間がかかります。したがって、それが好ましい。