使用STL内部实现的红黑树 [英] Using STL's Internal Implementation of Red-Black Tree

问题描述

我知道我的 STL(随 g++ 4.x.x 一起提供)使用红黑树来实现诸如地图之类的容器.是否可以直接使用STL内部的红黑树.如果是这样，如何?如果没有，为什么不 - 为什么 STL 不公开红黑树?

令人惊讶的是，我无法使用谷歌找到答案.

我正在研究使用红黑树作为插入时额外分配器构造函数调用的解决方案.请参阅这个问题.我的 STL 使用红黑树来实现地图.

解决方案

实际上 - 答案很简单，并且与您的 gcc 版本无关.你可以从sgi的网站下载stl源代码，自己看实现和使用.>

例如在3.2版本中，可以在stl_tree.h文件中看到红黑树的实现，以及在stl_set.h中的使用示例.

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

I understand that my STL (that comes with g++ 4.x.x) uses red-black trees to implement containers such as the map. Is it possible to use the STL's internal red-black tree directly. If so, how? If not, why not - why does STL not expose the red-black tree?

Surprisingly, I cannot find an answer using google.

Edit: I'm investigating using the red-black tree as a solution to the extra allocator constructor call on insertion. See this question. My STL uses red-black trees for map implementation.

解决方案

Actually - the answer is very simple, and independent of your version of gcc. You can download the stl source code from sgi's website, and see the implementation and use for yourself.

For example, in version 3.2, you can see the red-black tree implementation in the stl_tree.h file, and an example of its use in stl_set.h.

Note that since the stl classes are template classes, the implementations are actually inside the header files.

这篇关于使用STL内部实现的红黑树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！