On 05/11/2015 09:03 AM, Andrew Bell wrote:
On Mon, May 11, 2015 at 9:54 AM, Martin Sebor <msebor@xxxxxxxxxx> 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?
libstdc++ (as well as most other implementations) guarantees
binary compatibility between releases. That includes, among
other constraints, avoiding changes to the layout of types
exposed in the API. This is necessary in order to make it
possible to build an object with one version of GCC and link
it with another object built with a different version of the
compiler (and libstdc++).
Martin
