Re: [Boost-users] [MultiIndex] is ordered_non_unique stable?

Subject: Re: [Boost-users] [MultiIndex] is ordered_non_unique stable?
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2013-01-19 12:22:49

John M. Dlugosz <mpbecey7gu <at> snkmail.com> writes:

> 
> Will equivalent elements in a ordered_non_unique index be "stable" and
> maintain their relative ordering based on the order in which they were
> inserted?

Yes, this is the case, though the explanation is a little sophisticated:
Suppose we have an ordered_non_unique index of doubles and the following range
happens to be inserted into the container:

  1.0 2.0 3.0 3.0 3.0 4.0 5.0

Now we try to insert and element k with value 3.0: will it go righmost or some
other place? If we take a look at the relevant piece of code in
<multi_index/ordered_index.hpp>:

  bool link_point(key_param_type k,link_info& inf,ordered_non_unique_tag)
  {
    node_type* y=header();
    node_type* x=root();
    bool c=true;
    while (x){
     y=x;
     c=comp(k,key(x->value()));
     x=node_type::from_impl(c?x->left():x->right());
    }
    inf.side=c?to_left:to_right;
    inf.pos=y->impl();
    return true;
  }

You can see that k is always compared in a k<x form, not the other way around
(i.e. x<k). And from the point of view of std::less<double>, these
comparisons cannot distinguish between inserting 3.0 or inserting 3.0 plus an
epsilon (3.0<3.0 yields the same as 3.00001<3.0 --false-- and for the rest of
elements comparison stay the same), so insertion must happen at the rightmost
position possible.

The only problem with this is that the behavior is *undocmented*. If you want
to stay legal, use hinted insertion with end() (which will *documentedly*
work for all the ordered_non_unique indices of your container, not only the one
you happen to be doing for the insertion.)

Joaquín M López Muñoz
Telefónica Digital