C++ 中的集合与哈希集

Namita Chaudhary 2023年1月30日 2022年7月18日
  1. C++ 中的 Set 与 Hashset
  2. C++ 中的集合
  3. C++ 中的哈希集
  4. C++ 中 Set 和 Hashset 之间的主要区别
  5. 结论
C++ 中的集合与哈希集

C++ 中的 set 用作存储数据元素并在需要时检索它们的容器。类似地,hashset,更准确地说,C++ 中的 unordered_set,与存储数据元素集的用途相似。

在本文中,我们将详细讨论 setunordered_set

C++ 中的 Set 与 Hashset

set 是用于存储数据元素的关联容器,而 unordered_set 也是用于存储数据元素以满足我们未来需求的关联容器。那么,这两种数据结构与向量、地图和其他容器对象有何不同?

答案很简单。setunordered_set 存储唯一的数据元素。

因此,它们不允许重复元素。然而,向量和地图等其他数据结构也允许存储重复元素。

这两种数据结构都存在于 C++ 标准模板库中。

现在,由于我们简要解释了何时在 C++ 中使用 setunordered_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 也用于存储唯一的数据元素,但是 setunordered_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++ 中的 sethashset。这两种数据结构都存在于 C++ STL 中,用于存储唯一的数据元素。

但是,两者之间的主要区别在于 set 返回一组已排序的元素,而 unordered_set 返回无序的数据元素。

你可以使用两者中的任何一种,但在 unordered_set 中搜索操作更快,搜索元素花费几乎恒定的时间;因此,它是首选。

相关文章 - C++ Set