Boost logo

Boost :

Subject: Re: [boost] [container][set, map, flat_set, flat_map, +multi_xxx] operator< and operator== seems to ignore custom KeyCompare
From: Evgeny Panasyuk (evgeny.panasyuk_at_[hidden])
Date: 2013-07-18 05:04:50

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<T*> or std::set<T*> is not guaranteed to work?

As well as std::vector<double> -

>> + 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

Boost list run by bdawes at, gregod at, cpdaniel at, john at