区别:
比较项 | set | unordered_set |
---|---|---|
排序 | 升序(默认) | 无排序 |
实现 | 自平衡BST,类似红黑树 | 哈希表 |
搜索时间 | log(n) | O(1) -> Average,O(n) -> Worst Case |
插入时间 | log(n) + Rebalance | Same as search |
删除时间 | log(n) + Rebalance | Same as search |
何时使用set
- 需要有序的数据。
- 将不得不按排序顺序打印/访问数据。
- 需要元素的前任/后继。
- 由于set是有序的,因此可以在set元素上使用binary_search(),lower_bound()和upper_bound()之类的函数。 这些函数不能在unordered_set()上使用。
- 有关更多情况,请参见BST优于哈希表的优势。
在以下情况下使用unordered_set
- 需要保留一组不同的元素,并且不需要排序。
- 需要单元素访问,即无遍历。
set:
Input : 1, 8, 2, 5, 3, 9
Output : 1, 2, 3, 5, 8, 9
Unordered_set:
Input : 1, 8, 2, 5, 3, 9
Output : 9 3 1 8 2 5
如果要查看c ++ STL中set和unordered_set的实现详细信息,请参见Set Vs Map。 Set允许按排序顺序遍历元素,而Unordered_set不允许按排序顺序遍历元素。
// Program to print elements of set
#include <bits/stdc++.h>
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 (auto it : s)
cout << it << " ";
return 0;
}
执行上面示例代码,得到以下结果:
Elements of set in sorted order:
1 2 3 5 6 7
// Program to print elements of set
#include <bits/stdc++.h>
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 unordered_set:
2 7 5 1 6 3
套装中的前任/后继:
可以修改Set来查找其前任或后继,而Unordered_set不允许查找前任/后继。
// Program to print inorder predecessor and inorder successor
#include <bits/stdc++.h>
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(8);
inorderSuccessor(5);
inorderSuccessor(2);
inorderSuccessor(9);
return 0;
}
执行上面示例代码,得到以下结果:
predecessor of 5 is=2
No predecessor
predecessor of 8 is=5
successor of 5 is=8
successor of 2 is=5
No successor
欢迎任何形式的转载,但请务必注明出处,尊重他人劳动成果。
转载请注明:文章转载自 有区别网 [http://www.vsdiffer.com]
本文标题:C++ set 与 unordered_set的区别
本文链接:https://www.vsdiffer.com/vs/set-vs-unordered_set-c-stl.html
免责声明:以上内容仅是站长个人看法、理解、学习笔记、总结和研究收藏。不保证其正确性,因使用而带来的风险与本站无关!如本网站内容冒犯了您的权益,请联系站长,邮箱: ,我们核实并会尽快处理。