我知道我的 STL（g++ 4.xx 附带）使用红黑树来实现地图等容器。是否可以直接使用STL内部的红黑树。如果是这样，怎么做？如果不是，为什么不——为什么 STL 不暴露红黑树？
令人惊讶的是，我无法使用谷歌找到答案。
编辑：我正在研究使用红黑树作为插入时额外分配器构造函数调用的解决方案。看到这个问题。我的 STL 使用红黑树来实现地图。
问问题
15821 次
3 回答
9
实际上 - 答案很简单，并且与您的 gcc 版本无关。您可以从sgi 的网站下载 stl 源代码，自己查看实现和使用。
例如，在3.2版本中，您可以在stl_tree.h文件中看到红黑树的实现，以及在stl_set.h中的使用示例。
请注意，由于 stl 类是模板类，因此实现实际上在头文件中。
于 2012-07-08T08:02:41.077 回答
3
我相信大多数 STL 实现set和map都是红黑树，尽管没有什么能阻止人们使用不同的数据结构来实现它们——如果我没记错的话，C++ 标准不需要 RB 树实现。
STL 不会公开它，因为这会违反 OOP 原则。如果其他人要使用您的库，公开底层数据结构可能会导致一些不良行为。也就是说，特别是对于setand map，您应该只被允许访问符合setandmap数据结构的方法。暴露底层表示可能会导致用户在内部有重复set，这很糟糕。
话虽这么说，（据我所知）没有办法直接使用底层的红黑树。这在很大程度上取决于你想如何使用它。实现你自己的红黑树很可能是你最好的选择，或者查看我们的 3rd 方库（也许是 Boost？）
于 2012-07-08T06:32:22.380 回答
3
您甚至无法保证所使用的数据结构将是一棵红黑树（例如，它至少作为 AVL 树被实现过一次，并且像 B-、B* 或 B+ 树这样的东西可能就可以了好）。
因此，了解内部结构的唯一方法是查看特定的实现，并利用它不（至少尝试）公开公开的东西。
至于为什么：我认为主要是因为它是一种抽象的尝试，而不是暴露所有的实现细节。
于 2012-07-08T06:33:41.733 回答