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? -- Andrew Bell andrew.bell.ia@xxxxxxxxx
