一.set介绍
C++ 中的 set 容器是一种关联容器，用于存储唯一的元素，并能够根据特定的顺序对元素进行排列。在这里，我们将对 set 容器进行详细的分析。
- 概述
set 容器是 C++标准库中的一个部分，位于 头文件中。它是一个关联容器，意味着每个元素都是唯一的，并且可以根据特定的顺序对元素进行排列。
- 特点
- 唯一性：set 容器中的元素是唯一的，不允许重复。
- 有序性：set 容器中的元素是按照特定的顺序排列的，通常是升序或降序。
- 关联性：set 容器是关联容器，意味着每个元素都是唯一的，并且可以根据特定的顺序对元素进行排列。
- 实现
set 容器的实现是基于红黑树（Red-Black Tree）数据结构的。红黑树是一种自平衡的二叉查找树，它能够维护树的平衡，使得查找、插入和删除操作的时间复杂度保持在 O(log n) 级别。
- 常用操作
- 插入：使用 insert 方法将元素插入到 set 容器中。如果元素已经存在，将不会被插入。
set<int> mySet;
mySet.insert(10);
mySet.insert(20);
- 遍历：使用迭代器遍历 set 容器中的元素。
for (auto it = mySet.begin(); it != mySet.end(); ++it) {
cout << *it << " ";
}
- 查找：使用 find 方法在 set 容器中查找特定元素。如果找到，将返回该元素的迭代器；否则，将返回结束迭代器。
auto it = mySet.find(20);
if (it != mySet.end()) {
cout << "Element found in set";
}
- 删除：使用 erase 方法删除 set 容器中的元素。
mySet.erase(10);
- 优点
- 快速查找：set 容器的查找操作非常快，时间复杂度为 O(log n)。
- 自动排序：set 容器自动维护元素的顺序，无需手动排序。
- 唯一性：set 容器保证元素的唯一性，无需手动检查重复元素。
- 缺点
- 插入慢：set 容器的插入操作相对较慢，时间复杂度为 O(log n)。
- 空间占用：set 容器的空间占用相对较高，因为红黑树需要维护树的平衡。
- 应用场景
- 集合操作：set 容器非常适合集合操作，如 union、intersection、difference 等。
- 自动排序：set 容器自动维护元素的顺序，无需手动排序。
- 快速查找：set 容器的查找操作非常快，时间复杂度为 O(log n)。
二.unordered_set介绍
unordered_set 是 C++11 中引入的一个关联容器，它用于存储唯一的元素，但是不维护元素的顺序。相比于 set 容器，unordered_set 容器提供了更快的查找、插入和删除操作，但牺牲了元素的顺序。
- 概述
unordered_set 容器是 C++11 中引入的一个关联容器，位于 <unordered_set> 头文件中。它是一个无序容器，意味着元素的顺序是无关紧要的。
- 特点
- 唯一性：unordered_set 容器中的元素是唯一的，不允许重复。
- 无序性：unordered_set 容器中的元素是无序的，元素的顺序无关紧要。
- 快速查找：unordered_set 容器提供了非常快的查找操作，时间复杂度为平均 O(1)，最坏 O(n)。
快速插入和删除：unordered_set 容器提供了非常快的插入和删除操作，时间复杂度为平均 O(1)，最坏 O(n)。
- 实现
unordered_set 容器的实现是基于 hash table 数据结构的。hash table 使用哈希函数来将元素映射到容器中的索引上，使得查找、插入和删除操作变得非常快。
- 常用操作
- 插入：使用 insert 方法将元素插入到 unordered_set 容器中。如果元素已经存在，将不会被插入。
unordered_set<int> mySet;
mySet.insert(10);
mySet.insert(20);
- 遍历：使用迭代器遍历 unordered_set 容器中的元素。
for (auto it = mySet.begin(); it != mySet.end(); ++it) {
cout << *it << " ";
}
- 查找：使用 find 方法在 unordered_set 容器中查找特定元素。如果找到，将返回该元素的迭代器；否则，将返回结束迭代器。
auto it = mySet.find(20);
if (it != mySet.end()) {
cout << "Element found in set";
}
- 删除：使用 erase 方法删除 unordered_set 容器中的元素。
mySet.erase(10);
- 优点
-
快速查找：unordered_set 容器提供了非常快的查找操作，时间复杂度为平均 O(1)，最坏 O(n)。
-
快速插入和删除：unordered_set 容器提供了非常快的插入和删除操作，时间复杂度为平均 O(1)，最坏 O(n)。
-
低内存占用：unordered_set 容器的内存占用相对较低，因为hash table 需要的内存空间少。
缺点 -
无顺序：unordered_set 容器中的元素是无序的，无法维护元素的顺序。
-
可能存在哈希碰撞：如果哈希函数不够完善，可能会出现哈希碰撞，导致查找、插入和删除操作变得慢。
- 应用场景
- 快速查找：unordered_set 容器非常适合需要快速查找操作的场景。
- ** cache实现**：unordered_set 容器可以用于实现 cache，快速地查找和存储缓存内容。
- 集合操作：unordered_set 容器可以用于实现集合操作，如 union、intersection、difference 等。
三.两者选择场景
set 和 unordered_set 都是 C++ 的关联容器，用于存储唯一的元素，但是它们有不同的实现和特点，选择哪一个取决于具体的使用场景和需求。
- 选择 set 的场景
- 需要有序：如果需要元素保持特定的顺序，例如按照升序或降序排列，那么 set 是不二之选。set 使用红黑树作为底层数据结构，能够维护元素的顺序。
- 需要遍历元素：如果需要遍历整个容器，例如 foreach 循环，set 提供了更好的遍历性能，因为红黑树的遍历效率高于哈希表。
- 元素类型支持排序：如果元素类型支持排序，例如 int、string 等，那么 set 可以使用这个排序规则来维护元素的顺序。
- 选择 unordered_set 的场景
- 需要快速查找：如果需要快速查找特定元素，例如频繁地查找特定元素，那么 unordered_set 是不二之选。unordered_set 使用哈希表作为底层数据结构，能够提供 O(1) 的平均查找时间。
- 需要快速插入和删除：如果需要频繁地插入和删除元素，那么 unordered_set 是不二之选。unordered_set 提供了 O(1) 的平均插入和删除时间。
- 元素类型不支持排序：如果元素类型不支持排序，例如自定义类， 那么 unordered_set 是不二之选，因为哈希表不需要元素类型支持排序。
- 其他考虑因素
- 内存占用：unordered_set 通常需要更少的内存，因为哈希表需要的内存空间少。
- 哈希函数：如果使用 unordered_set，需要提供一个良好的哈希函数，以避免哈希碰撞。
- ** Collision resolution**：如果使用 unordered_set，需要选择合适的 Collision resolution 策略，以避免哈希碰撞。
- 结论
如果需要元素保持顺序或需要遍历整个容器，选择 set。如果需要快速查找、插入和删除元素，并且元素类型支持哈希函数，那么选择 unordered_set。
