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

Question

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

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

此外，集合的insert()函数如何工作？集合如何检查元素是否已经存在于其中？

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

- zebraman

Answer 1

调试进入 g++ 6.4 stdlibc++源码

你是否知道在 Ubuntu 16.04 默认的 g++-6 软件包或者从源代码构建的 GCC 6.4中，无需任何其他设置即可进入 C++ 库？

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

这是有道理的，因为 std::set 可以按顺序遍历，如果使用哈希映射，则效率会降低。

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不能按顺序遍历，所以标准库选择了哈希表而不是红黑树，因为哈希表具有更好的平均插入时间复杂度。

进入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类似：C++标准库中的std::map使用的是什么数据结构？

性能特征

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

图形生成过程和堆栈和二叉搜索树分析详见：Heap vs Binary Search Tree (BST)

我们清楚地看到：

• std::set，插入时间对数级别
• std::unordered_set，更复杂的哈希表模式：
  • 在非缩放的情况下，我们清楚地看到支持动态数组在巨大的一次性线性增长峰值上翻倍
  • 在缩放后的情况下，我们看到时间基本上是恒定的，并且趋向于250ns，因此比std::map快得多，除了非常小的地图大小
  • 可以清楚地看到几个条带，每个条带内部的平均线性增长链接列表遍历。 然后，当数组翻倍时，我们有更多的bins，因此步行更短。

- Ciro Santilli OurBigBook.com

---

通过这样做，我们很容易得出使用红黑树的结论。*...通过这种实现。在标准的许多*部分中，实现有自己的实现方式。 - Caleth

Answer 2

正如KTC所说，std::set的实现方式可能会有所不同--C++标准只是指定了一个抽象数据类型。换句话说，标准并没有规定容器应该如何实现，而是规定了它需要支持哪些操作。然而，据我所知，STL的大多数实现都使用红黑树或其他平衡二叉搜索树（例如GNU libstdc++使用红黑树）。

虽然你可以理论上将set实现为哈希表并获得更快的渐近性能（摊销O（键长）对于查找和插入，而不是O（log n）），但这需要用户提供他们想要存储的任何类型的哈希函数（参见Wikipedia关于哈希表的条目以获得关于它们工作原理的良好解释）。至于二叉搜索树的实现，你不想使用数组--正如Raul所提到的，你需要一些Node数据结构。

- Toli

---

你可以使用哈希表来实现一个集合类型。然而，你不能（至少不容易）实现符合std::set迭代器要求的集合类型。 - dan04

@dan04说，你甚至不能实现一个满足std::set查找和插入要求的程序。就像Toli所说，你需要一个关键字类型的哈希函数，但使用std::set的用户不需要按照标准提供一个。因此，当他们的代码在编译时出现“没有找到hash（MyElement）的匹配项”的错误时，这意味着std::set的实现有缺陷。 - Steve Jessop

Hashtable 不太可能，因为 std::set 是有序的。 - Ciro Santilli OurBigBook.com

我希望看到一个能够从任意“Compare”综合哈希并保持std::set复杂性要求的实现。 - Caleth

@Caleth 我相信你可以按照以下链接中的说明完成：https://dev59.com/c3E85IYBdhLWcg3wwWet - Ciro Santilli OurBigBook.com

@CiroSantilli新疆改造中心996ICU六四事件。不，这是在谈论使用一个不是std::less的Compare，而不是从bool(T, T)中构建一个std::size_t(T)。 - Caleth

Answer 3

你可以通过首先定义一个 Node 结构来实现二叉搜索树：

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

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

二叉搜索树的维基百科条目有一个非常好的示例，展示了如何实现插入方法，我也建议您查看一下。

关于重复项，通常在集合中不允许存在重复项，因此您可以根据您的规范丢弃该输入、抛出异常等。

- Raul Agrait

---

据我所知，std::set是一个有序容器。如果它是一棵二叉搜索树，那么如何遍历才能保证有序？ - Shasha99

@Shasha99，预订遍历将按顺序提供元素。 - Shafi

@MASh，我想我们在谈论插入的顺序。 - Shasha99

插入顺序并不是“有序容器”中“有序”的意思。 - n. m.

为了满足标准承诺的性能规格，需要使用一个平衡的二叉搜索树。 - n. m.

Answer 4

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

正如其他人指出的，它因实现方式而异。集合通常被实现为树（红黑树、平衡树等），但可能存在其他实现方式。

此外，对于一个集合，insert() 是如何工作的？

这取决于你的集合的底层实现。如果它被实现为二叉树，则 Wikipedia 上有 insert() 函数的示例递归实现。你可能需要查看它。

集合如何检查其中是否已经存在一个元素？

如果它被实现为树，则遍历树并检查每个元素。然而，集合不允许存储重复元素。如果你想要一个允许重复元素的集合，则需要使用 multiset。

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

您可能在提到哈希集，其中使用哈希表来实现集合。您需要提供一个哈希函数来确定存储元素的位置。当您想要快速搜索元素时，这种实现是理想的。但是，如果您的元素按特定顺序存储很重要，则树实现更合适，因为您可以按先序、中序或后序遍历它。

- jasonline

Answer 5

特定容器在C++中的实现完全取决于具体实现。所需的只是结果符合标准规定的要求，例如各种方法的复杂度要求、迭代器要求等。

- KTC

---

话虽如此，大多数（全部？）都是红黑树。 - GManNickG

有基于AVL的实现可以在http://sourceforge.net/projects/stlavlmap/找到，还有一个不完整的基于B树的实现可以在http://idlebox.net/2007/stx-btree/找到。 - MSalters

考虑到时间复杂度的限制和需要进行排序，几乎没有可以避免使用某种平衡树的替代方案。 - Fabio Ceconello

复杂度要求通常是针对特定实现而指定的，因此可能会对数据结构的选择产生相当大的限制。 - M.M

Answer 6

参与讨论一下，因为我没有看到有人明确提到... C++标准并没有指定用于std::set和std::map的数据结构。然而，它确实规定了各种操作的运行时复杂度。对于插入、删除和查找操作的计算复杂度要求，更或多或少地迫使实现使用平衡树算法。

实现平衡二叉树的两种常见算法是红黑树和AVL树。在这两种算法中，红黑树的实现稍微简单一些，每个树节点需要比AVL树少1位存储空间（这几乎无关紧要，因为在简单的实现中你会在一个字节上进行操作），并且在节点删除方面比AVL树稍微快一些（这是由于对树平衡的要求更加宽松）。

所有这些，再加上std::map要求键和数据存储在std::pair中，都迫使你在不明确命名容器所必须使用的数据结构的情况下完成所有这些操作。

这一切，反过来又被c++14/17的容器补充功能所加强，这些功能允许将节点从一棵树剪切到另一棵树中。

- jschmerge

Answer 7

cppreference says:

集合通常被实现为红黑树。

我查过了，无论是 libc++ 还是 libstdc++ 都使用红黑树来实现 std::set。

std::unordered_set 在 libc++ 中使用哈希表实现，我认为在 libstdc++ 中也是这样，但没有检查。

编辑： 显然我的话不足以说服人。

• libc++：1 2
• libstdc++：1

- Timmmm

---

我已经通过逐步调试进入libstdc++进行了确认：https://dev59.com/m3E85IYBdhLWcg3w432o#51944661，因为我只相信来自GDB本身的结果 :-) - Ciro Santilli OurBigBook.com