Intrsuive multisets and stable sorting
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. Thanks, Dan.
On Wed, Oct 17, 2012 at 9:51 AM, Dan Posluns <dan@danposluns.com> 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
El 18/10/2012 6:08, Jeffrey Lee Hellrung, Jr. escribió:
On Wed, Oct 17, 2012 at 9:51 AM, Dan Posluns <dan@danposluns.com <mailto:dan@danposluns.com>> wrote:
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.
Current implementation has stability, and it should be documented. However, it's missing N1780: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1780.html http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#233 Could please fill a ticket in Trac, requesting documentation on stability and the implementation of N1780? Once Boost.Intrusive gets N1780, Boost.Container will get it, as it's based on Boost.Intrusive. Best, Ion
El 18/10/2012 12:33, Ion Gaztañaga escribió:
Could please fill a ticket in Trac, requesting documentation on stability and the implementation of N1780?
Once Boost.Intrusive gets N1780, Boost.Container will get it, as it's based on Boost.Intrusive.
Sorry! I've reviewed the code and Boost.Intrusive already implements N1780, I wrongly reviewed insert_unique_xxx, instead of insert_equal_xxx. So all we need is to document it. Best, Ion
On Thu, Oct 18, 2012 at 3:44 AM, Ion Gaztañaga <igaztanaga@gmail.com> wrote:
El 18/10/2012 12:33, Ion Gaztañaga escribió:
Could please fill a ticket in Trac, requesting documentation on
stability and the implementation of N1780?
Once Boost.Intrusive gets N1780, Boost.Container will get it, as it's based on Boost.Intrusive.
Sorry! I've reviewed the code and Boost.Intrusive already implements N1780, I wrongly reviewed insert_unique_xxx, instead of insert_equal_xxx.
So all we need is to document it.
it == insertion stability, I presume. https://svn.boost.org/trac/boost/ticket/7529 - Jeff
El 18/10/2012 15:12, Jeffrey Lee Hellrung, Jr. escribió:
On Thu, Oct 18, 2012 at 3:44 AM, Ion Gaztañaga <igaztanaga@gmail.com <mailto:igaztanaga@gmail.com>> wrote:
El 18/10/2012 12:33, Ion Gaztañaga escribió:
Could please fill a ticket in Trac, requesting documentation on stability and the implementation of N1780?
Once Boost.Intrusive gets N1780, Boost.Container will get it, as it's based on Boost.Intrusive.
Sorry! I've reviewed the code and Boost.Intrusive already implements N1780, I wrongly reviewed insert_unique_xxx, instead of insert_equal_xxx.
So all we need is to document it.
it == insertion stability, I presume.
Thanks Ion
participants (3)
-
Dan Posluns -
Ion Gaztañaga -
Jeffrey Lee Hellrung, Jr.