作用
set与unordered_set一样，都是关联式容器，和 map 容器不同，使用 set 容器存储的各个键值对，要求键 key 和值 value 必须相等。
当使用 set 容器存储键值对时，只需要为其提供各键值对中的 value 值（也就是 key 的值）即可。
使用 set 容器存储的各个元素的值必须各不相同。
从语法上讲 set 容器并没有强制对存储元素的类型做 const 修饰，即 set 容器中存储的元素的值是可以修改的。但是，C++ 标准为了防止用户修改容器中元素的值，对所有可能会实现此操作的行为做了限制，使得在正常情况下，用户是无法做到修改 set 容器中元素的值的。
下面主要讨论一下set和unordered_set的区别之处。
set
- 定义于<set>头文件
- 底层实现通常是平衡二叉树
- 元素自动排序，这为查找元素提供了良好性能，但同时也造成了一个重要限制：不能直接改变元素值，因为这会打乱原本正确的顺序
- 查找函数具有对数复杂度
- 要改变元素的值，必须先删除该元素，再插入新元素
使用示例如下：
// Program to print elements of set
#include <set>
using namespace std;
int main()
{
set<int> s;
s.insert(5);
s.insert(1);
s.insert(6);
s.insert(3);
s.insert(7);
s.insert(2);
cout << "Elements of set in sorted order: \n";
for (const auto& it : s)
cout << it << " ";
return 0;
}
输出结果：
Elements of set in sorted order:
1 2 3 5 6 7unordered_set
- 定义于<unordered_set>头文件
- 底层实现通常是hash-table
- 元素是无序的
- 插入、删除、查找元素的时间复杂度是常量的（排除偶尔的rehashing导致的线性复杂度）
示例：
// Program to print elements of set
#include <unordered_set>
using namespace std;
int main()
{
unordered_set<int> s;
s.insert(5);
s.insert(1);
s.insert(6);
s.insert(3);
s.insert(7);
s.insert(2);
cout << "Elements of unordered_set: \n";
for (auto it : s)
cout << it << " ";
return 0;
}
输出结果：
Elements of set in sorted order:
2 7 5 1 6 3小结
综上，以下情况使用set：
- 需要排序的数据
- 需要通过前序、后序等方式遍历元素或者查找前继后继元素
- 想要使用binary_search(), lower_bound() and upper_bound()等需要在有序元素上使用的方法
- 其他平衡二叉树具有而hash表没有的优点
在以下情况使用unordered_set:
- 仅需要保存互异的元素而不需要排序
- 只需要获取单个元素而不需要遍历
它们的区别概览：
最后通过set进行按序查找前继后继元素的示例如下：
// Program to print inorder predecessor and inorder successor
#include <set>
using namespace std;
set<int> s;
void inorderPredecessor(int key)
{
if (s.find(key) == s.end()) {
cout << "Key doesn't exist\n";
return;
}
set<int>::iterator it;
it = s.find(key); // get iterator of key
// If iterator is at first position
// Then, it doesn't have predecessor
if (it == s.begin()) {
cout << "No predecessor\n";
return;
}
--it; // get previous element
cout << "predecessor of " << key << " is=";
cout << *(it) << "\n";
}
void inorderSuccessor(int key)
{
if (s.find(key) == s.end()) {
cout << "Key doesn't exist\n";
return;
}
set<int>::iterator it;
it = s.find(key); // get iterator of key
++it; // get next element
// Iterator points to NULL (Element does
// not exist)
if (it == s.end())
{
cout << "No successor\n";
return;
}
cout << "successor of " << key << " is=";
cout << *(it) << "\n";
}
int main()
{
s.insert(1);
s.insert(5);
s.insert(2);
s.insert(9);
s.insert(8);
inorderPredecessor(5);
inorderPredecessor(1);
inorderPredecessor