使用STL的红黑树内部实现

Question

我知道我的STL（随g++ 4.x.x提供）使用红黑树来实现诸如map之类的容器。是否可以直接使用STL内部的红黑树？如果可以，如何使用？如果不行，为什么不行——为什么STL没有暴露红黑树？

令人惊讶的是，我在谷歌上找不到答案。

编辑：我正在研究使用红黑树作为解决插入时额外分配构造函数调用的方法。请参见这个问题。我的STL使用红黑树来实现map。

- Prasoon Tiwari

---

我正在研究使用红黑树作为解决方案，以避免在插入时调用额外的分配器构造函数。一个适当的解决方法是使用不具有此属性的标准容器实现。C++11要求有状态的分配器，因此任何正确支持此C++11特性的标准库都将具有更合理的行为（尽管它仍会构造不同的分配器实例，但只会从原始分配器对象中进行构造）。 - Nicol Bolas

@Prasoon - 这里不会对你有所帮助，因为它是底层的树实现，无论如何都会调用构造函数。尝试使用比gcc 4.1更新的编译器可能是一个选择（之前的问题为STL map自定义内存分配器）。 - Bo Persson

Answer 1

实际上，答案非常简单，与您的gcc版本无关。 您可以从sgi的网站下载stl源代码，并自行查看其实现和用法。

例如，在3.2版中，您可以在stl_tree.h文件中看到红黑树的实现，并在stl_set.h中看到其用法示例。

请注意，由于stl类是模板类，因此实现实际上在头文件中。

- Guy Adini

---

我相信你使用的链接已经过时了，因为它将我重定向到了Hewitt Packaging网站。 - user17705437

Answer 2

大多数 STL 实现的 set 和 map 是红黑树，不过没有人阻止使用其他数据结构来实现它们，如果我没记错的话，C++ 标准并没有要求必须使用红黑树实现。但是，STL 不会将其公开，因为这样会违反 OOP 原则。暴露底层数据结构可能会导致一些不希望出现的行为，如果其他人使用您的库，那就更糟了。也就是说，对于 set 和 map，您只应该允许访问符合 set 和 map 数据结构的方法。公开底层表示可能会导致用户在 set 中有重复项，这是不好的。

话虽如此，据我所知，并没有直接使用底层红黑树的方法，这很大程度上取决于您想如何使用它。最好自己实现红黑树，或者查看第三方库（例如 Boost）。

- adelbertc

Answer 3

您甚至不能保证使用的数据结构将是红黑树（例如，它已经被实现为AVL树，而像B-、B*或B+树这样的东西也可能很好）。

因此，唯一获取内部信息的方法是查看特定实现，并利用它不公开的内容（至少尝试）。

至于原因：我认为主要是因为它是一种抽象尝试，不暴露所有实现细节。

- Jerry Coffin