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 中搜索操作更快，搜索元素花费几乎恒定的时间；因此，它是首选。