top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

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

+2 votes
460 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 LinkedIn 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?

...