C++ 中的集合與雜湊集

1. C++ 中的 Set 與 Hashset
2. C++ 中的集合
3. C++ 中的雜湊集
4. C++ 中 Set 和 Hashset 之間的主要區別
5. まとめ

C++ 中的 set 用作儲存資料元素並在需要時檢索它們的容器。類似地，hashset，更準確地說，C++ 中的 unordered_set，與儲存資料元素集的用途相似。

在本文中，我們將詳細討論 set 和 unordered_set。

C++ 中的 Set 與 Hashset

set 是用於儲存資料元素的關聯容器，而 unordered_set 也是用於儲存資料元素以滿足我們未來需求的關聯容器。那麼，這兩種資料結構與向量、地圖和其他容器物件有何不同？

答案很簡單。set 和 unordered_set 儲存唯一的資料元素。

因此，它們不允許重複元素。然而，向量和地圖等其他資料結構也允許儲存重複元素。

這兩種資料結構都存在於 C++ 標準模板庫中。

現在，由於我們簡要解釋了何時在 C++ 中使用 set 和 unordered_set，現在讓我們詳細瞭解它們。

C++ 中的集合

如前所述，set 是一個關聯容器，它以排序方式儲存唯一的資料元素。但是，你可以以任何隨機順序儲存它們，但是一旦從 set 中檢索它們，它將僅以排序方式返回元素。

因此，set 包含用於對來自使用者的隱藏資料元素進行排序的定義。

C++ 中的 sets 實現為二叉搜尋樹；因此，它們是有序的。此外，搜尋元素需要 O(log n) 時間。

讓我們看看如何在 C++ 中實現一個 set。

#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++ 中的雜湊集

C++ 中的 unordered_set 或 hashset 都是同一個意思。這個 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++ 中 Set 和 Hashset 之間的主要區別

1. sets 用於按升序儲存元素，而 unordered_set 以無序儲存元素。
2. sets 是使用二叉搜尋樹實現的，而 unordered_set 是使用雜湊表實現的。
3. sets 中的搜尋操作需要 O(log n) 時間來搜尋一個元素，而搜尋一個 unordered_set 中的元素需要 O(1) 時間。
4. sets 包含在 #include<set> 標頭檔案中，而 unordered_set 使用 #include<unordered_set> 標頭檔案包含。

まとめ

在本文中，我們討論了 C++ 中的 set 和 hashset。這兩種資料結構都存在於 C++ STL 中，用於儲存唯一的資料元素。

但是，兩者之間的主要區別在於 set 返回一組已排序的元素，而 unordered_set 返回無序的資料元素。

你可以使用兩者中的任何一種，但在 unordered_set 中搜尋操作更快，搜尋元素花費幾乎恆定的時間；因此，它是首選。