Using STL's Internal Implementation of Red-Black Tree

c++ stl tree red-black-tree
Prasoon Tiwari picture Prasoon Tiwari · Jul 8, 2012 · Viewed 14.4k times · Source

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.

Answer

Guy Adini picture Guy Adini · Jul 8, 2012

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.

Related questions

Why does the C++ STL not provide any "tree" containers?

Why does the C++ STL not provide any "tree" containers, and what's the best thing to use instead? I want to store a hierarchy of objects as a tree, rather than use a tree as a performance enhancement...

Read More
What is the easiest way to initialize a std::vector with hardcoded elements?

I can create an array and initialize it like this: int a[] = {10, 20, 30}; How do I create a std::vector and initialize it similarly elegant? The best way I know is: std::vector<int> ints; ints.push_back(10); ints.…

Read More
How do I erase an element from std::vector<> by index?

I have a std::vector<int>, and I want to delete the n'th element. How do I do that? std::vector<int> vec; vec.push_back(6); vec.push_back(-17); vec.push_back(12); vec.erase(???);

Read More