Fwd: Why are RB-trees used to implement std::set?

Andrew Bell andrew.bell.ia@gmail.com
Mon May 11 15:03:00 GMT 2015

On Mon, May 11, 2015 at 9:54 AM, Martin Sebor <msebor@redhat.com> wrote:
> On 05/11/2015 05:41 AM, Jakub Arnold wrote:
>> Hi,
>> 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?
> 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.

Break binary compatibility?  What kind of guarantees are there?  I'm
not advocating a change in data structures, but it doesn't seem like
there are any promises beyond API conformance, are there?

Andrew Bell

More information about the Gcc-help mailing list