Fwd: Why are RB-trees used to implement std::set?
Mon May 11 15:03:00 GMT 2015
On Mon, May 11, 2015 at 9:54 AM, Martin Sebor <firstname.lastname@example.org> wrote:
> On 05/11/2015 05:41 AM, Jakub Arnold wrote:
>> I'm curious as to why libstdc++ is using a RB-tree to implement
>> std::set (details here
>> 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?
More information about the Gcc-help