[container][set, map, flat_set, flat_map, +multi_xxx] operator< and operator== seems to ignore custom KeyCompare
Hi Ion & others, I think that there might be a problem in the implementation of operator< for these containers. There might be a problem with operator== too. The problem is that they all use some variant of the following definition: template <class Key, class Value, class KeyOfValue, class KeyCompare, class A> inline bool operator<(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) { return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } There is no KeyCompare (or other compare object) passsed to lexicographical compare. Reading up on the standard, it seems that all standard containers are implemented this way. Consequence: when having e.g. set<T*>, the comparison is not portable, since only std::less<T*> is guaranteed to be. So isn't this a defect? The other issue is perhaps more sensitive. What should users expect from typedef set<std::string,CaseInsensitiveLess> Set; Set s1{ "foo", "BAR" }; Set s2{ "FOO", "bar" }; assert( s1 < s2 ); // true? assert( s1 == s2 ); // true? I was at least surprised by this behavior. regards Thorsten
El 17/07/2013 16:58, Thorsten Ottosen escribió:
Reading up on the standard, it seems that all standard containers are implemented this way.
Consequence: when having e.g. set<T*>, the comparison is not portable, since only std::less<T*> is guaranteed to be. So isn't this a defect?
The other issue is perhaps more sensitive. What should users expect from
typedef set<std::string,CaseInsensitiveLess> Set; Set s1{ "foo", "BAR" }; Set s2{ "FOO", "bar" }; assert( s1 < s2 ); // true? assert( s1 == s2 ); // true?
I was at least surprised by this behavior.
It's a bit surprising but that's also how vector::operator< is implemented (vector has no Compare function object so std::less<T> is used). The operator is just there to have a default order to be inserted in parent associative containers. The standard is quite clear: (taken from N3680) Table 98 — Optional container operations -> Expression: a < b -> Return type: convertible to bool -> 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. -> Complexity: linear I guess using Compare for associative containers' operator < could perfectly work it won't be the standard behaviour. Best, Ion
18.07.2013 1:22, Ion Gaztañaga:
(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. [...] I guess using Compare for associative containers' operator < could perfectly work it won't be the standard behaviour.
+ 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. " -- Evgeny Panasyuk
On 18-07-2013 01:07, Evgeny Panasyuk wrote:
18.07.2013 1:22, Ion Gaztañaga:
(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?
[...]
I guess using Compare for associative containers' operator < could perfectly work it won't be the standard behaviour.
Yeah, it's definitely a breaking change.
+ 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 <. Still, we can't know what compare to use for ==, unless we require it to rely on < (which may be slower). -Thorsten
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> - 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
participants (3)
-
Evgeny Panasyuk -
Ion Gaztañaga -
Thorsten Ottosen