在C++中，set和unordered_set之间有什么区别？
在C++中，set和unordered_set之间有什么区别？
我遇到了一个好问题，它类似但并不相同，因为它讨论的是Java，Java中的哈希表实现不同，因为具有同步的访问器/修改器：
那么C++中的set和unordered_set的实现有什么区别呢？
当然，这个问题可以扩展到map vs unordered_map等其他C++容器。
以下是我的初步评估：
set：虽然标准没有明确要求它作为树来实现，但对于其查找/插入操作的时间复杂度约束要求，意味着它总是以树的形式实现。
通常为红黑树（如GCC 4.8中所见），它是高度平衡的。
由于它们是高度平衡的，对于find()操作它们具有可预测的时间复杂度。
优点：紧凑（与其他DS相比）
缺点：访问时间复杂度为O(log n)
unordered_set：虽然标准没有明确要求它作为树来实现，但对于其查找/插入操作的时间复杂度约束要求，意味着它总是作为哈希表来实现。
优点：
- 更快（承诺搜索的摊还时间复杂度为O(1)
- 与树型数据结构相比，更容易将基本类型转换为线程安全
缺点：
- 查找不保证为O(1)，理论上的最坏情况是O(n)
- 与树型数据结构相比不够紧凑（实际目的上的负载因子永远不会为1）
注：
哈希表的O(1)假设是没有冲突的情况下得出的。即使负载因子为0.5，每秒变量插入也会导致冲突。
可以观察到，哈希表的负载因子与访问其中的元素所需的操作数量成反比。我们减少操作数，哈希表就会变得更稀疏。当存储的元素大小与指针可比时，开销相当显著。
我是否遗漏了任何关于性能分析的map/set之间的差异需要了解的内容？
set和unordered_set在C++中的区别是什么？
一个区别是，尽管不涉及性能方面的考虑，但是set的插入不会使迭代器失效，而unordered_set的插入可能会使迭代器失效，如果插入触发了重新哈希。实际上，这是一个非常小的问题，因为对实际元素的引用仍然有效。
那么，如果set是以红黑树实现的，插入会触发树的重新平衡，这是怎么回事呢？
因为迭代器可以（并且我认为总是）基于指向内部树节点的指针来实现。重新平衡操作不需要创建或销毁节点，只需要调整一些左/右/父指针。因此，之后，之前有效的迭代器仍然指向一个有效的节点，并且仍然可以访问它所需要遍历树的所有内容。
由此可见，set和unordered_set在插入操作上的区别主要是迭代器的有效性。set的插入不会使迭代器失效，而unordered_set的插入可能会使迭代器失效。这是由于unordered_set在插入时可能触发重新哈希，而set不需要进行这样的操作。因此，在使用迭代器遍历集合时，需要注意unordered_set的插入操作可能会导致迭代器失效，需要重新获取有效的迭代器。
C++中的set和unordered_set有什么区别？
在C++中，set和unordered_set都是关联容器，用于存储一组不重复的元素。它们之间的主要区别在于底层实现和迭代顺序。
首先，set是通过红黑树实现的，而unordered_set则是通过哈希表实现的。红黑树是一种自平衡的二叉搜索树，它保持了元素的有序性。哈希表使用哈希函数将元素映射到桶中，并使用链表或其他方法解决哈希冲突。
其次，由于红黑树的特性，set中的元素是按照给定的比较函数从小到大排序的，而unordered_set中的元素没有特定的顺序，它们以“随机”的顺序返回。
此外，set和unordered_set在内存占用方面也有所不同。红黑树中的每个节点都需要占用一定的空间，包括指针大小、元素大小和其他开销。而哈希表中的元素只需占用元素大小和指针大小的空间。对于大小较小的元素，例如基本类型，指针和其他开销的占用会主导内存占用，因此在负载因子大于0.5的情况下，unordered_set可能比等效的set占用更少的内存。
总之，选择set还是unordered_set取决于具体的需求。如果需要元素有序且迭代顺序确定，则应选择set。如果需要快速的插入、查找和删除操作，并且对迭代顺序没有特殊要求，则应选择unordered_set。
代码如下：
#include#include #include int main() { std::set s = {3, 1, 2}; std::unordered_set us = {3, 1, 2}; std::cout << "Set: "; for (auto it = s.begin(); it != s.end(); ++it) { std::cout << *it << " "; } std::cout << std::endl; std::cout << "Unordered Set: "; for (auto it = us.begin(); it != us.end(); ++it) { std::cout << *it << " "; } std::cout << std::endl; return 0; }
C++中的set和unordered_set有什么区别？
在C++中，set和unordered_set是两种不同的容器。它们之间的区别在于底层数据结构和性能。
首先，set是一个有序的容器，它使用红黑树作为底层数据结构来存储元素。红黑树可以保持元素的有序性，并提供O(logn)的插入、删除和查找操作。然而，由于红黑树的特性，set的空间占用较大。
而unordered_set则是一个无序的容器，它使用哈希表作为底层数据结构来存储元素。哈希表可以提供O(1)的插入、删除和查找操作，但是它不保持元素的有序性。由于哈希表的特性，unordered_set的空间占用较小。
在实际使用中，我们可以根据具体的需求来选择set或者unordered_set。如果我们需要保持元素的有序性，并且不关心空间占用，那么可以选择set。如果我们需要快速的插入、删除和查找操作，并且不需要保持元素的有序性，那么可以选择unordered_set。
总结起来，set和unordered_set在底层数据结构和性能上有所区别。set使用红黑树存储元素，保持有序性，但空间占用较大。而unordered_set使用哈希表存储元素，提供快速的插入、删除和查找操作，但不保持有序性。根据具体需求选择合适的容器可以提高程序的效率和性能。