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.
François
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 8fac385570b..9e721aad8cc 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -337,6 +337,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
bool _Constant_iteratorsa>
friend struct __detail::_Insert;
+ template<typename _Keya, typename _Valuea, typename _Alloca,
+ typename _ExtractKeya, typename _Equala,
+ typename _H1a, typename _H2a, typename _Hasha,
+ typename _RehashPolicya, typename _Traitsa,
+ bool _Unique_keysa>
+ friend struct __detail::_Equality;
+
public:
using size_type = typename __hashtable_base::size_type;
using difference_type = typename __hashtable_base::difference_type;
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 7bbfdfd375b..55c020f93d1 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -34,6 +34,7 @@
#include <tuple> // for std::tuple, std::forward_as_tuple
#include <limits> // for std::numeric_limits
#include <bits/stl_algobase.h> // for std::min.
+#include <bits/stl_algo.h> // for std::is_permutation.
namespace std _GLIBCXX_VISIBILITY(default)
{
@@ -1815,65 +1816,6 @@ namespace __detail
_M_eq() const { return _EqualEBO::_M_cget(); }
};
- /**
- * struct _Equality_base.
- *
- * Common types and functions for class _Equality.
- */
- struct _Equality_base
- {
- protected:
- template<typename _Uiterator>
- static bool
- _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
- };
-
- // See std::is_permutation in N3068.
- template<typename _Uiterator>
- bool
- _Equality_base::
- _S_is_permutation(_Uiterator __first1, _Uiterator __last1,
- _Uiterator __first2)
- {
- for (; __first1 != __last1; ++__first1, ++__first2)
- if (!(*__first1 == *__first2))
- break;
-
- if (__first1 == __last1)
- return true;
-
- _Uiterator __last2 = __first2;
- std::advance(__last2, std::distance(__first1, __last1));
-
- for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
- {
- _Uiterator __tmp = __first1;
- while (__tmp != __it1 && !bool(*__tmp == *__it1))
- ++__tmp;
-
- // We've seen this one before.
- if (__tmp != __it1)
- continue;
-
- std::ptrdiff_t __n2 = 0;
- for (__tmp = __first2; __tmp != __last2; ++__tmp)
- if (*__tmp == *__it1)
- ++__n2;
-
- if (!__n2)
- return false;
-
- std::ptrdiff_t __n1 = 0;
- for (__tmp = __it1; __tmp != __last1; ++__tmp)
- if (*__tmp == *__it1)
- ++__n1;
-
- if (__n1 != __n2)
- return false;
- }
- return true;
- }
-
/**
* Primary class template _Equality.
*
@@ -1889,7 +1831,7 @@ namespace __detail
bool _Unique_keys = _Traits::__unique_keys::value>
struct _Equality;
- /// Specialization.
+ /// unordered_map and unordered_set specializations.
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
typename _H1, typename _H2, typename _Hash,
@@ -1913,17 +1855,31 @@ namespace __detail
_H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
_M_equal(const __hashtable& __other) const
{
+ using __node_base = typename __hashtable::__node_base;
+ using __node_type = typename __hashtable::__node_type;
const __hashtable* __this = static_cast<const __hashtable*>(this);
-
if (__this->size() != __other.size())
return false;
for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
{
- const auto __ity = __other.find(_ExtractKey()(*__itx));
- if (__ity == __other.end() || !bool(*__ity == *__itx))
+ std::size_t __ybkt = __other._M_bucket_index(__itx._M_cur);
+ __node_base* __prev_n = __other._M_buckets[__ybkt];
+ if (!__prev_n)
return false;
+
+ for (__node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);;
+ __n = __n->_M_next())
+ {
+ if (__n->_M_v() == *__itx)
+ break;
+
+ if (!__n->_M_nxt
+ || __other._M_bucket_index(__n->_M_next()) != __ybkt)
+ return false;
+ }
}
+
return true;
}
@@ -1934,7 +1890,6 @@ namespace __detail
typename _RehashPolicy, typename _Traits>
struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_H1, _H2, _Hash, _RehashPolicy, _Traits, false>
- : public _Equality_base
{
using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_H1, _H2, _Hash, _RehashPolicy, _Traits>;
@@ -1953,24 +1908,27 @@ namespace __detail
_M_equal(const __hashtable& __other) const
{
const __hashtable* __this = static_cast<const __hashtable*>(this);
-
if (__this->size() != __other.size())
return false;
for (auto __itx = __this->begin(); __itx != __this->end();)
{
- const auto __xrange = __this->equal_range(_ExtractKey()(*__itx));
- const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
+ std::size_t __x_count = 1;
+ auto __itx_end = __itx;
+ for (++__itx_end; __itx_end != __this->end()
+ && __this->key_eq()(_ExtractKey()(*__itx_end),
+ _ExtractKey()(*__itx));
+ ++__itx_end)
+ ++__x_count;
- if (std::distance(__xrange.first, __xrange.second)
- != std::distance(__yrange.first, __yrange.second))
+ const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
+ if (__x_count != std::distance(__yrange.first, __yrange.second))
return false;
- if (!_S_is_permutation(__xrange.first, __xrange.second,
- __yrange.first))
+ if (!std::is_permutation(__itx, __itx_end, __yrange.first))
return false;
- __itx = __xrange.second;
+ __itx = __itx_end;
}
return true;
}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/operators/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/operators/1.cc
index 4b87f62b74a..7252cad29c2 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_multiset/operators/1.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/operators/1.cc
@@ -99,8 +99,64 @@ void test01()
VERIFY( !(ums1 != cums2) );
}
+void test02()
+{
+ std::unordered_multiset<int> us1
+ { 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9 };
+ std::unordered_multiset<int> us2
+ { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
+
+ VERIFY( us1 == us2 );
+}
+
+struct Hash
+{
+ std::size_t
+ operator()(const std::pair<int, int>& p) const
+ { return p.first; }
+};
+
+struct Equal
+{
+ bool
+ operator()(const std::pair<int, int>& lhs, const std::pair<int, int>& rhs) const
+ { return lhs.first == rhs.first; }
+};
+
+void test03()
+{
+ std::unordered_multiset<std::pair<int, int>, Hash, Equal> us1
+ {
+ { 0, 0 }, { 1, 0 }, { 2, 0 }, { 3, 0 }, { 4, 0 },
+ { 0, 1 }, { 1, 1 }, { 2, 1 }, { 3, 1 }, { 4, 1 },
+ { 5, 0 }, { 6, 0 }, { 7, 0 }, { 8, 0 }, { 9, 0 },
+ { 5, 1 }, { 6, 1 }, { 7, 1 }, { 8, 1 }, { 9, 1 }
+ };
+ std::unordered_multiset<std::pair<int, int>, Hash, Equal> us2
+ {
+ { 5, 1 }, { 6, 1 }, { 7, 1 }, { 8, 1 }, { 9, 1 },
+ { 0, 1 }, { 1, 1 }, { 2, 1 }, { 3, 1 }, { 4, 1 },
+ { 5, 0 }, { 6, 0 }, { 7, 0 }, { 8, 0 }, { 9, 0 },
+ { 0, 0 }, { 1, 0 }, { 2, 0 }, { 3, 0 }, { 4, 0 }
+ };
+
+ VERIFY( us1 == us2 );
+
+ std::unordered_multiset<std::pair<int, int>, Hash, Equal> us3
+ {
+ { 5, 1 }, { 6, 1 }, { 7, 1 }, { 8, 1 }, { 9, 1 },
+ { 0, 1 }, { 1, 1 }, { 2, 1 }, { 3, 1 }, { 4, 1 },
+ { 5, 0 }, { 6, 0 }, { 7, 1 }, { 8, 0 }, { 9, 0 },
+ { 0, 0 }, { 1, 0 }, { 2, 0 }, { 3, 0 }, { 4, 0 }
+ };
+
+ VERIFY( us1 != us3 );
+}
+
int main()
{
test01();
+ test02();
+ test03();
return 0;
}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/operators/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/operators/1.cc
index d841246e2c1..36a45dfa099 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/operators/1.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/operators/1.cc
@@ -99,8 +99,56 @@ void test01()
VERIFY( !(us1 != cus2) );
}
+void test02()
+{
+ std::unordered_set<int> us1 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
+ std::unordered_set<int> us2 { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 };
+
+ VERIFY( us1 == us2 );
+}
+
+struct Hash
+{
+ std::size_t
+ operator()(const std::pair<int, int>& p) const
+ { return p.first; }
+};
+
+struct Equal
+{
+ bool
+ operator()(const std::pair<int, int>& lhs, const std::pair<int, int>& rhs) const
+ { return lhs.first == rhs.first; }
+};
+
+void test03()
+{
+ std::unordered_set<std::pair<int, int>, Hash, Equal> us1
+ {
+ { 0, 0 }, { 1, 1 }, { 2, 2 }, { 3, 3 }, { 4, 4 },
+ { 5, 5 }, { 6, 6 }, { 7, 7 }, { 8, 8 }, { 9, 9 }
+ };
+ std::unordered_set<std::pair<int, int>, Hash, Equal> us2
+ {
+ { 5, 5 }, { 6, 6 }, { 7, 7 }, { 8, 8 }, { 9, 9 },
+ { 0, 0 }, { 1, 1 }, { 2, 2 }, { 3, 3 }, { 4, 4 }
+ };
+
+ VERIFY( us1 == us2 );
+
+ std::unordered_set<std::pair<int, int>, Hash, Equal> us3
+ {
+ { 5, -5 }, { 6, 6 }, { 7, 7 }, { 8, 8 }, { 9, 9 },
+ { 0, 0 }, { 1, 1 }, { 2, 2 }, { 3, 3 }, { 4, 4 }
+ };
+
+ VERIFY( us1 != us3 );
+}
+
int main()
{
test01();
+ test02();
+ test03();
return 0;
}
