STL set 在 C++ 中的底层数据结构是什么？

13 浏览
0 Comments

STL set 在 C++ 中的底层数据结构是什么？

我想了解C++中如何实现集合。如果我要实现自己的集合容器而不使用STL提供的容器，最好的方法是什么？

我了解STL的集合是基于二叉搜索树的抽象数据结构实现的。那么底层的数据结构是什么？是数组吗？

另外，对于一个集合，insert()是如何工作的？集合如何检查元素是否已存在其中？

我在维基百科上读到另一种实现集合的方法是使用哈希表。这是如何工作的呢？

0

3 答案

0 Comments

STL（Standard Template Library）是C++的一个重要组成部分，其中的set是一种有序容器。那么，STL set在C++中使用的底层数据结构是什么呢？

首先，可以通过定义一个Node结构来实现二叉搜索树（Binary Search Tree）：

struct Node
{
  void *nodeData;
  Node *leftChild;
  Node *rightChild;
}

然后，可以使用另一个Node *rootNode;来定义树的根节点。

对于插入方法的实现，可以参考维基百科关于二叉搜索树的条目，那里有一个很好的例子。

至于重复元素，通常在集合中是不允许存在的。因此，可以根据规范丢弃重复的输入，抛出异常等。

关于遍历的顺序，std::set是一个有序容器，但它使用的底层数据结构是平衡二叉搜索树（balanced binary search tree）。这意味着，通过使用前序遍历（pre-order traverse），可以按照一定的顺序获取元素。

为了满足标准所承诺的性能规范，需要使用一棵平衡的二叉搜索树。

0
0 Comments

STL（Standard Template Library）是C++标准库的一部分，提供了一套通用的模板类和函数，用于实现常用的数据结构和算法。其中，STL set是一个有序的集合容器，它的底层数据结构是红黑树（Red-black tree）。

红黑树是一种自平衡的二叉搜索树，它具有以下特性：

1. 每个节点要么是红色，要么是黑色；

2. 根节点是黑色；

3. 每个叶子节点（NIL节点，空节点）是黑色；

4. 如果一个节点是红色，则它的两个子节点都是黑色；

5. 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点。

STL set使用红黑树作为底层数据结构有以下原因：

1. 红黑树可以保持集合的有序性，支持按照元素大小进行遍历和查找。如果使用哈希表作为底层数据结构，无法保证集合的有序性，导致遍历效率低下。

2. 红黑树的插入、删除和查找操作的时间复杂度都是O(log n)，具有较好的平衡性能。

下面是通过调试g++源代码来验证STL set底层数据结构的过程：

1. 编写一个简单的C++程序，包含set的插入和查找操作。

2. 使用g++编译该程序，并通过gdb调试。

3. 在插入操作中，跟踪到/usr/include/c++/6/bits/stl_set.h文件，发现insert方法实际调用了_M_t._M_insert_unique方法。

4. 在该文件中，找到_M_t的定义，发现它的类型是_Rep_type，而_Rep_type是一个_Rb_tree。

5. 因此，可以得出结论，STL set的底层数据结构是红黑树。

与STL set类似，STL unordered_set是一个无序的集合容器，它的底层数据结构是哈希表（hash table）。

哈希表是一种根据键（key）直接访问值（value）的数据结构，它通过将键通过哈希函数映射到数组中的一个位置来实现快速的插入、删除和查找操作。

STL unordered_set使用哈希表作为底层数据结构有以下原因：

1. 哈希表可以实现常数时间复杂度的插入、删除和查找操作，具有较好的平均性能。

2. 由于无序性，哈希表无法按照元素大小进行遍历和查找。

通过调试g++源代码可以验证STL unordered_set底层数据结构的过程与STL set类似。

总结起来，STL set使用红黑树作为底层数据结构，支持有序性和较好的平衡性能；STL unordered_set使用哈希表作为底层数据结构，支持常数时间复杂度的插入、删除和查找操作。这些选择是基于数据结构的特性和性能需求。

附加内容中还提到了STL map和unordered_map的底层数据结构，以及通过性能测试验证了各种数据结构的性能特征。最后，作者强调了实现可以在某些方面给出自己的实现，所以需要根据具体情况来确定底层数据结构。

0
0 Comments

STL（Standard Template Library）是C++标准库中的一个重要组成部分，提供了许多常用的数据结构和算法。其中，std::set是STL中的一个集合容器，用于存储一组有序的元素，并且不允许重复。

然而，std::set的底层数据结构并没有在C++标准中明确规定，只是规定了它应该支持哪些操作。因此，不同的实现可以采用不同的底层数据结构。大多数STL的实现（如GNU libstdc++）通常使用红黑树或其他平衡二叉搜索树作为std::set的底层数据结构。

虽然理论上可以使用哈希表来实现集合，并且获得更快的渐进性能（平摊O(键长度)的查找和插入时间复杂度，而红黑树的时间复杂度为O(log n)），但这将需要用户提供键类型的哈希函数。然而，std::set的用户在标准中并没有被要求提供哈希函数。因此，使用哈希表来实现std::set会有一些困难。

总结起来，std::set的底层数据结构可以是红黑树或其他平衡二叉搜索树，而不是哈希表。这是因为红黑树可以满足std::set的有序性要求，并且提供较好的性能保证。如果要实现一个使用哈希表作为底层数据结构的集合容器，需要用户提供键类型的哈希函数，并且无法满足std::set的迭代器和查找、插入等要求。

参考资料：

- [C++中的STL的set是如何实现的？](https://stackoverflow.com/questions/2620862)

0