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

Michael Powell mwpowellhtx@gmail.com
Mon May 11 17:47:00 GMT 2015


On Mon, May 11, 2015 at 1:29 PM, Paul Smith <paul@mad-scientist.net> wrote:
> On Mon, 2015-05-11 at 12:40 -0400, Michael Powell wrote:
>> > 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++?
>>
>> Playing devil's advocate, I want interface compatibility.
>
> Indeed.  But "interface" is part of both API and ABI so your statement
> doesn't help answer the question.
>
> If you want to be able to link against pre-compiled libraries, then you
> require *binary* interface compatibility.  Making changes to the
> underlying type of a std:: type can break the ABI.
>
> If you're OK with recompiling everything yourself rather than using
> pre-compiled libraries, then you only require *program* interface
> compatibility.  In this case it's straightforward to make those changes.

Thanks for clarifying the comparison/contrast.

> Most people really require ABI stability for a library like libstdc++.
>



More information about the Gcc-help mailing list