c++ - C++ 中 STL 集的底层数据结构是什么？

Question

我想知道一个集合是如何在 C++ 中实现的。如果我在不使用 STL 提供的容器的情况下实现自己的 set 容器，那么完成这项任务的最佳方法是什么？

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

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

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

Answer 1

单步调试到 g++ 6.4 stdlibc++ 源代码

你知道在 Ubuntu 的 16.04 默认 g++-6 包或 GCC 6.4 build from source无需任何进一步设置即可进入 C++ 库？

通过这样做，我们很容易得出结论，此实现中使用了红黑树。

这是有道理的，因为 std::set 可以按顺序遍历，如果使用 HashMap 则效率不高。

main.cpp

#include <cassert>
#include <set>

int main() {
    std::set<int> s;
    s.insert(1);
    s.insert(2);
    assert(s.find(1) != s.end());
    assert(s.find(2) != s.end());
    assert(s.find(3) == s3.end());
}

编译调试:

g++ -g -std=c++11 -O0 -o main.out main.cpp
gdb -ex 'start' -q --args main.out

现在，如果您进入 s.insert(1)，您会立即到达 /usr/include/c++/6/bits/STL_set.h:

487 #if __cplusplus >= 201103L
488       std::pair<iterator, bool>
489       insert(value_type&& __x)
490       {
491     std::pair<typename _Rep_type::iterator, bool> __p =
492       _M_t._M_insert_unique(std::move(__x));
493     return std::pair<iterator, bool>(__p.first, __p.second);
494       }
495 #endif

这显然只是转发到 _M_t._M_insert_unique。

于是我们在vim中打开源文件，找到_M_t的定义:

      typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
           key_compare, _Key_alloc_type> _Rep_type;
       _Rep_type _M_t;  // Red-black tree representing set.

所以 _M_t 是 _Rep_type 类型，而 _Rep_type 是 _Rb_tree。

好的，现在这对我来说已经足够了。如果您不相信 _Rb_tree 是黑红树，请进一步阅读算法。

unordered_set 使用哈希表

相同的过程，但将代码上的 set 替换为 unordered_set。

这是有道理的，因为 std::unordered_set 不能按顺序遍历，所以标准库选择 HashMap 而不是红黑树，因为 HashMap 具有更好的分摊插入时间复杂度。

进入 insert 会导致 /usr/include/c++/6/bits/unordered_set.h:

415       std::pair<iterator, bool>
416       insert(value_type&& __x)
417       { return _M_h.insert(std::move(__x)); }

于是我们在vim中打开源文件，搜索_M_h:

      typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc>  _Hashtable;
      _Hashtable _M_h;

哈希表就是这样。

std::map 和 std::unordered_map

类似于 std::set 与 std:unordered_set:What data structure is inside std::map in C++?

性能特点

您还可以通过计时来推断使用的数据结构:

图形生成过程和堆与 BST 分析，位于:Heap vs Binary Search Tree (BST)

我们清楚地看到:

• std::set，对数插入时间

• std::unordered_set，更复杂的hashmap模式:

  • 在非缩放图上，我们清楚地看到后备动态阵列在线性增加的峰值上翻倍

  • 在放大图上，我们看到时间基本上是恒定的，接近 250ns，因此比 std::map 快得多，除了非常小的 map 尺寸

    几个 strip 清晰可见，每当阵列翻倍时，它们的倾斜度就会变小。

    我相信这是由于平均线性增加的链表遍历每个 bin。然后当数组加倍时，我们有更多的 bin，所以走的时间更短。