[MultiIndex] is ordered_non_unique stable?
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? Or do I need to use a complex key, adding my own sequence number, to ensure the desired ordering? —John
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
participants (2)
-
Joaquin M Lopez Munoz
-
John M. Dlugosz