Re: [boost] [container][set, map, flat_set, flat_map, +multi_xxx] operator< and operator== seems to ignore custom KeyCompare

18.07.2013 11:27, Thorsten Ottosen:

...

...

(taken from N3680) Table 98 — Optional container operations [...] -> Operational semantics lexicographical_compare (a.begin(), a.end(), b.begin(), b.end())

-> Assertion/note: pre: < is defined for values of T. < is a total ordering relationship. So std::vector or std::set is not guaranteed to work?

As well as std::vector<double> - http://ideone.com/dcoKYd

...

+ also, here (Table 98) < is **total ordering**, while "23.2.4 Associative containers" says: " 2. Each associative container is parameterized on Key and an ordering relation Compare that induces a **strict weak ordering** (25.4) on elements of Key. In addition, map and multimap associate an arbitrary mapped type T with the Key. The object of type Compare is called the comparison object of a container. "

Well, one could argue that the internal ordering is a different concept than the semantics of the comparison operators. My motivation was more that I can't think of a situation where I don't want the KeyCompare to be used for <.

I think such situations may arise within generic code. For instance, some function template that takes two containers, uses operator< on them, and then does some computations with container's elements that assumes properties imposed by definition of operator<. If std::set would have internal ordering with another meaning, and that would be used for operator<, then such properties may no longer be true.

Still, we can't know what compare to use for ==, unless we require it to rely on < (which may be slower).

Problem is not only in speed, but also in fact that ordering relation of associative containers is **strict weak ordering**, which means that "equivalence of keys" imposed by comparison does not have to be equality. -- Evgeny Panasyuk