Re: [Boost-users] Intrsuive multisets and stable sorting

Subject: Re: [Boost-users] Intrsuive multisets and stable sorting
From: Jeffrey Lee Hellrung, Jr. (jeffrey.hellrung_at_[hidden])
Date: 2012-10-18 00:08:42

On Wed, Oct 17, 2012 at 9:51 AM, Dan Posluns <dan_at_[hidden]> wrote:

> Hi there,
>
> I'm attempting to use intrusive associative containers, but it's essential
> to
> the application that as I add "equivalent" objects to the multiset that
> their
> order is maintained, ie. that the sort is stable.
>
> I'm looking at using avl_multiset for its fast retrieve times. I ran an
> experiment several times over where I added 1000 entries of random numbers
> from
> 0-9 that also contained ordering information to a multiset, and that
> ordering
> information wound up being preserved, even when I removed some items and
> added
> new ones to the initial tree. So that looks promising. If someone were
> able to
> confirm the results of my experiment it would be better, though. Best
> would be
> documentation that lists which multiset implementations are stable and
> which
> aren't, but I can't find such a thing in the docs.
>

I agree; if stability of insertions with equal keys can be guaranteed
(which I don't see why it can't be off-hand for any of the binary tree
implementations), that fact would be nice to add to the documentation.

- Jeff