16

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.

Community
  • 1
  • 1
Prasoon Tiwari
  • 840
  • 2
  • 12
  • 23
  • "I'm investigating using the red-black tree as a solution to the extra allocator constructor call on insertion." A proper solution would be to use an implementation of standard containers that doesn't have this property. C++11 requires stateful allocators, so any standard library that properly supports this C++11 feature will have more reasonable behavior (though it will still construct different allocator instances, it will only do so from the original allocator object). – Nicol Bolas Jul 08 '12 at 06:56
  • @Prasoon - It wouldn't help you here, because it is the underlying tree implementation that does the constructor calls anyway. Trying a newer compiler than gcc 4.1 would be an option (previous question [Custom memory allocator for STL map](http://stackoverflow.com/questions/11373796/custom-memory-allocator-for-stl-map)) – Bo Persson Jul 08 '12 at 07:16

3 Answers3

9

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.

Guy Adini
  • 5,188
  • 5
  • 32
  • 34
  • I believe that the link that you used is outdated as it routes me to a site from Hewitt Packaging. –  Jan 11 '22 at 01:43
3

Most STL implementations of set and map are red black trees I believe, though nothing is stopping someone from implementing them using a different data structure - if I remember correctly, the C++ standard does not require a RB tree implementation.

The STL does not expose it as that would violate OOP principles.. exposing the underlying data structure could lead to some undesired behavior if someone else were to use your library. That is, specifically for set and map, you should only be allowed access to methods that would conform to the set and map data structures.. exposing the underlying representation could perhaps lead a user to have duplicates inside set, which is bad.

That being said, there is no way (to my knowledge) to directly use the underlying red black tree.. it would depend a lot on how you would want to use it. Implementing your own red-black tree would most likely be your best bet, or check our 3rd party libraries (perhaps Boost?)

adelbertc
  • 7,270
  • 11
  • 47
  • 70
3

You're not even given a guarantee that the data structure used will be a red-black tree (e.g., it's been implemented at least once as an AVL tree, and something like B-, B* or B+ tree would probably be fine as well).

As such, the only way to get at the internals would be to look at a specific implementation, and make use of things it doesn't (at least try to) expose publicly.

As to the why: I think mostly because it's an attempt at abstraction, not exposing all the implementation details.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111