On 1/10/20 11:01 PM, Jonathan Wakely wrote:
On 10/01/20 18:54 +0100, François Dumont wrote:
Hi
Here is my attempt to improve == operator.
There is a small optimization for the std::unordered_mutiXXX
containers but the main enhancement rely on some partial template
specialization of the _Equality type. I limit it to usage of
unordered containers with std::equal_to to be sure that the
container _Equal functor is like the key type ==.
I think we can assume that for any _Equal, not just std::equal_to:
http://eel.is/c++draft/unord.req#12.sentence-5
However ...
Ok but...
Do I need to also consider user partial template
specialization of std::equal_to ? It is a well know bad practice
so I hope the Standard says that such a partial specialization
leads to undefined behavior.
It's certainly not undefined to specialize equal_to, and I'm not sure
how to make your optimisations valid in that case.
This proposal is indeed invalid if you use a std::equal_to partial
specialization, this is why I asked.
Consider:
struct X
{
int i;
int rounded() const { return i - (i % 10); }
bool operator==(X x) const { return i == x.i; }
};
template<> struct std::equal_to<X>
{
bool operator()(X l, X r) const
{ return l.rounded() == r.rounded(); }
};
template<> std::hash<X>
{
bool operator()(X x) const { return hash<int>()(x.rounded()); }
};
std::unordered_multiset<X> u{ X{10}, X{11}, X{12} };
std::unordered_multiset<X> v{ X{15}, X{16}, X{17} };
bool b1 = u == v;
bool b2 = std::is_permutation(u.begin(), u.end(), v.begin());
assert(b1 == b2);
I think the last new specialization in your patch would be used for
this case, and because __x_count == v.count(*u.begin()) it will say
they're equal. But the is_permutation call says they're not.
So I think the assertion would fail, but the standard says it should
pass. Am I mistaken?
I agree, it would fail and the Standard says it should pass.
So here is a new proposal. For the unique keys case I think we are
good, I do not see any other optimization.
For the multi-keys we could still avoid redundant comparisons when
_Equal is just doing == on the key type. On unordered_multiset we
could just avoids the call to is_permuation and on the
unordered_multimap we could check the is_permutation only on the
associated value rather than on the std::pair.
In order to detect that _Equal is the std::equal_to from
stl_function.h it would be great to have something like a
__builtin_is_system returning true for types defined in system
headers. For now I try to propose something similar without compiler
help.