top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

Why are RB-trees used to implement std::set in C++?

+2 votes
39 views

I'm curious as to why libstdc++ is using a RB-tree to implement std::set (details here
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/std/set and here https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/include/bits/stl_tree.h ),
when there are faster alternatives?

I'm mainly curious, because from all the people I've asked there hasn't been a single answer in favor of RB-trees, other than "they're already popular" or "easy to implement".

If you'd like more details on that, here's a link to my question on stackexchange http://cs.stackexchange.com/questions/41969/why-are-red-black-trees-so-popular,
where nobody has yet answered as well.

Using a variant of B-tree (or (a,b)-tree) should be faster, and everyone seems to suggest so, which makes me wonder what is the reason for picking RB-trees? This is not a question about their theoretical speed, but about real world behavior on real hardware with respect to CPU caches, etc.

posted May 11, 2015 by anonymous

Share this question
Facebook Share Button Twitter Share Button Google+ Share Button LinkedIn Share Button Multiple Social Share Button

2 Answers

+1 vote

Because the original HP STL that most implementations (including libstdc++) are derived from was written that way. Changing the underlying data structure would likely break binary compatibility and so the benefits of such a change would have to significantly outweigh its costs.

answer May 11, 2015 by Kiran Kumar
+1 vote

Imagine you write a library and you compile and distribute the binaries. Someone else builds against those. If std::set is used in your API, and they have a different version of libstdc++, do you still want the library and the binary to be compatible, even across different versions of libstdc++?

answer May 11, 2015 by Jagan Mishra
Similar Questions
+3 votes

Why B Trees are used to implement databases? Please explain with example.

+3 votes

I am in the middle of a project where now I have to add Google Authenticator into it. The problem is that the project is entirely in C++. I haven't found anything about Google Authenticator in C++. Is there a way to do it?

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...