Dominique Devienne <ddevienne <at> gmail.com> writes:
I would like to support a slightly unusual use-case. We have a class with a integer member, and a BMI container for instances of this class.
That member is supposed to be unique, *except* for a special "invalid" value (-1), which several instances can use.
Right now, we use an ordered_non_unique index, because of the -1's, but that leaves the door open for other duplicate "valid" values, which should be forbidden.
So my question is whether one can index this member uniquely, thanks to a custom comparator, such that the comparator does not violate the usual strict-weak-ordering requirement of ordered containers?
Steven's answer is, as always, correct, and we can leave it at that. But, if you want to venture into uncharted lands... Suppose we use the following: template<typename T,T puncture> struct punctured_less { bool operator()(const T& x,const T& y)const { if(x==puncture&&y==puncture)return true; return x<y; } }; using set=boost::multi_index_container< int, indexed_by< ordered_unique<identity<int>,punctured_less<int,-1>> >
;
Fist thing to notice is: punctured_less<int,-1> is *not* a strict weak ordering. For instance, it is not irreflexive as ::operator()(-1,-1)==true. But if we write: set s={-3,-2,-1,0,0,1,-1,2,3,-1,4,5,-1,6,7,-1,8,9,9,-1}; for(int x:s)std::cout<<x<<" "; the thing seemingly works and prints -3 -2 -1 -1 -1 -1 -1 -1 0 1 2 3 4 5 6 7 8 9 Note duplicates for 0 and 9 have been rejectet as they should. How come this is behaving so reasonably? The key insight is that insert(x) does as many internal comparisons as *strictly* necessary and not one more. Which means: no comparison is made if it can be inferred from the general properties of strict weak orderings (in particular, x is not compared against itself). Another interesting way to look at this fact is: insert(x) walks down the internal rb tree doing the minimum required number of comparisons (log(N) or the number of levels in the tree) and there is always a strict weak ordering compatible with whatever log(N) outputs we get from the Compare object (hey, even if Compare spits random booleans). In the case of punctured_less<int,-1> Boost.MultiIndex behaves as if each new -1 to be inserted is less that all other -1s already in the container. Insertion sort of works, lookup is more difficult to handle. You can verify that s.lower_bound(-1)==s.lower_bound(0) s.upper_bound(-1)==s.upper_bound(-2) that is, looking up for -1 behaves as if the -1s are not quite there, which is (in some sense) consistent with the fact that -1s never compare false to themselves. Note that [s.lower_bound(-1),s.upper_bound(-1)) is not a proper range (the end precedes the beginning). equal_range also behaves oddly: s.equal_range(-1)==std::make_pair(s.lower_bound(0),s.lower_bound(0) which is at least a valid range (but not the same as std::make_pair(s.lower_bound(-1),s.upper_bound(-1)) as guaranteed by the documentation). Lookup for values other than -1 behaves perfectly, as it is only when invoking operator()(-1,-1) that strict weak ordering properties are violated. If you're able to live in a state of undefined behavior and cope with the oddities described above, well, you might take advantage of this. Joaquín M López Muñoz