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 ...
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.
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 saw that the _S_is_permutation has been done in 2012, before
std::is_permutation has been added in 2013. I'll try to replace it in
a future patch.
Yes, that seems like a good idea.
PR libstdc++/91223
* include/bits/hashtable_policy.h
(_Equality<_Key, std::pair<const _Key, _Tp>, _Alloc,
__detail::_Select1st, std::equal_to<_Key>, _H1, _H2, _Hash,
_RehashPolicy, _Traits, true>): New partial template spetialization.
(_Equality<_Value, _Value, _Alloc, __detail::_Identity,
std::equal_to<_Value>, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>):
Likewise.
(_Equality<_Key, std::pair<const _Key, _Tp>, _Alloc,
__detail::_Select1st, std::equal_to<_Key>, _H1, _H2, _Hash,
_RehashPolicy, _Traits, false>): Likewise.
(_Equality<_Key, std::pair<const _Key, _Tp>, _Alloc,
__detail::_Select1st, std::equal_to<_Key>, _H1, _H2, _Hash)
(_RehashPolicy, _Traits, false>): Likewise.
* src/c++11/hashtable_c++0x.cc: Include <bits/stl_function.h>.
* testsuite/23_containers/unordered_multiset/operators/1.cc
(Hash, Equal, test02, test03): New.
* testsuite/23_containers/unordered_set/operators/1.cc
(Hash, Equal, test02, test03): New.
unordered tests run under Linux x86_64.
Ok to commit after running all tests ?
François
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h
b/libstdc++-v3/include/bits/hashtable_policy.h
index 7bbfdfd375b..2ac3e959320 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -1959,11 +1959,18 @@ namespace __detail
for (auto __itx = __this->begin(); __itx != __this->end();)
{
- const auto __xrange = __this->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;
This is a nice optimisation.
+ const auto __xrange = std::make_pair(__itx, __itx_end);
const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
- if (std::distance(__xrange.first, __xrange.second)
- != std::distance(__yrange.first, __yrange.second))
+ if (__x_count != std::distance(__yrange.first, __yrange.second))
return false;
if (!_S_is_permutation(__xrange.first, __xrange.second,
@@ -1975,6 +1982,242 @@ namespace __detail
return true;
}
+ /// Specialization.
With the increased number of specializations I think this comment
would be more useful if it said "specialization for multimap", and
change the others to "specialization for multiset" etc.
+ template<typename _Key, typename _Tp, typename _Alloc,
+ typename _H1, typename _H2, typename _Hash,
+ typename _RehashPolicy, typename _Traits>
+ struct _Equality<_Key, std::pair<const _Key, _Tp>, _Alloc,
+ __detail::_Select1st, std::equal_to<_Key>,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
+ {
+ using __hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
+ __detail::_Select1st, std::equal_to<_Key>,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits>;
+
+ bool
+ _M_equal(const __hashtable&) const;
+ };
+
+ template<typename _Key, typename _Tp, typename _Alloc,
+ typename _H1, typename _H2, typename _Hash,
+ typename _RehashPolicy, typename _Traits>
+ bool
+ _Equality<_Key, std::pair<const _Key, _Tp>, _Alloc, __detail::_Select1st,
+ std::equal_to<_Key>, _H1, _H2,
+ _Hash, _RehashPolicy, _Traits, true>::
+ _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(); ++__itx)
+ {
+ const auto __ity = __other.find(__itx->first);
+ if (__ity == __other.end() || !bool(__ity->second == __itx->second))
+ return false;
+ }
+ return true;
+ }
+
+ /// Specialization.
+ template<typename _Value, typename _Alloc,
+ typename _H1, typename _H2, typename _Hash,
+ typename _RehashPolicy, typename _Traits>
+ struct _Equality<_Value, _Value, _Alloc, __detail::_Identity,
Wrong indentation here.
+ std::equal_to<_Value>, _H1, _H2,
+ _Hash, _RehashPolicy, _Traits, true>
+ {
+ using __hashtable = _Hashtable<_Value, _Value, _Alloc,
+ __detail::_Identity, std::equal_to<_Value>,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits>;
+
+ bool
+ _M_equal(const __hashtable&) const;
+ };
+
+ template<typename _Value, typename _Alloc,
+ typename _H1, typename _H2, typename _Hash,
+ typename _RehashPolicy, typename _Traits>
+ bool
+ _Equality<_Value, _Value, _Alloc, __detail::_Identity,
+ std::equal_to<_Value>, _H1, _H2,
+ _Hash, _RehashPolicy, _Traits, true>::
+ _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(); ++__itx)
+ if (__other.find(*__itx) == __other.end())
+ return false;
+
+ return true;
+ }
+
+ /// Specialization.
+ template<typename _Key, typename _Tp, typename _Alloc,
+ typename _H1, typename _H2, typename _Hash,
+ typename _RehashPolicy, typename _Traits>
+ struct _Equality<_Key, std::pair<const _Key, _Tp>, _Alloc,
+ __detail::_Select1st, std::equal_to<_Key>,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
+ {
+ using __hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
+ __detail::_Select1st, std::equal_to<_Key>,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits>;
+
+ bool
+ _M_equal(const __hashtable&) const;
+
+ private:
+ using __hash_cached = typename _Traits::__hash_cached;
+ using __constant_iterators = typename _Traits::__constant_iterators;
+ using const_iterator =
+ __detail::_Node_const_iterator<std::pair<const _Key, _Tp>,
+ __constant_iterators::value,
+ __hash_cached::value>;
+
+ static bool
+ _S_is_permutation(const_iterator, const_iterator, const_iterator);
+ };
+
+ template<typename _Key, typename _Tp, typename _Alloc,
+ typename _H1, typename _H2, typename _Hash,
+ typename _RehashPolicy, typename _Traits>
+ bool
+ _Equality<_Key, std::pair<const _Key, _Tp>, _Alloc,
+ __detail::_Select1st, std::equal_to<_Key>,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits, false>::
+ _S_is_permutation(const_iterator __first1, const_iterator __last1,
+ const_iterator __first2)
+ {
+ for (; __first1 != __last1; ++__first1, ++__first2)
+ if (!(__first1->second == __first2->second))
+ break;
+
+ if (__first1 == __last1)
+ return true;
+
+ const_iterator __last2 = __first2;
+ std::advance(__last2, std::distance(__first1, __last1));
+
+ for (const_iterator __it1 = __first1; __it1 != __last1; ++__it1)
+ {
+ const_iterator __tmp = __first1;
+ while (__tmp != __it1 && !bool(__tmp->second == __it1->second))
+ ++__tmp;
+
+ // We've seen this one before.
+ if (__tmp != __it1)
+ continue;
+
+ std::ptrdiff_t __n2 = 0;
+ for (__tmp = __first2; __tmp != __last2; ++__tmp)
+ if (__tmp->second == __it1->second)
+ ++__n2;
+
+ if (!__n2)
+ return false;
+
+ std::ptrdiff_t __n1 = 0;
+ for (__tmp = __it1; __tmp != __last1; ++__tmp)
+ if (__tmp->second == __it1->second)
+ ++__n1;
+
+ if (__n1 != __n2)
+ return false;
+ }
+ return true;
+ }
+
+ template<typename _Key, typename _Tp, typename _Alloc,
+ typename _H1, typename _H2, typename _Hash,
+ typename _RehashPolicy, typename _Traits>
+ bool
+ _Equality<_Key, std::pair<const _Key, _Tp>, _Alloc,
+ __detail::_Select1st, std::equal_to<_Key>,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits, false>::
+ _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();)
+ {
+ std::size_t __x_count = 1;
+ auto __itx_end = __itx;
+ for (++__itx_end; __itx_end != __this->end()
+ && __this->key_eq()(__itx_end->first, __itx->first);
+ ++__itx_end)
+ ++__x_count;
+
+ const auto __xrange = make_pair(__itx, __itx_end);
+ const auto __yrange = __other.equal_range(__itx->first);
+
+ if (__x_count != std::distance(__yrange.first, __yrange.second))
+ return false;
+
+ if (!_S_is_permutation(__xrange.first, __xrange.second,
+ __yrange.first))
+ return false;
+
+ __itx = __xrange.second;
Why do you use __xrange.second here, rather than __itx_end?
To me it seems clearer to use __itx_end, consistent with the
multiset case below.
+ }
+ return true;
+ }
+
+ /// Specialization.
+ template<typename _Value, typename _Alloc,
+ typename _H1, typename _H2, typename _Hash,
+ typename _RehashPolicy, typename _Traits>
+ struct _Equality<_Value, _Value, _Alloc, __detail::_Identity,
+ std::equal_to<_Value>, _H1, _H2,
+ _Hash, _RehashPolicy, _Traits, false>
+ {
+ using __hashtable = _Hashtable<_Value, _Value, _Alloc,
+ __detail::_Identity, std::equal_to<_Value>,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits>;
+
+ bool
+ _M_equal(const __hashtable&) const;
+ };
+
+ template<typename _Value, typename _Alloc,
+ typename _H1, typename _H2, typename _Hash,
+ typename _RehashPolicy, typename _Traits>
+ bool
+ _Equality<_Value, _Value, _Alloc, __detail::_Identity,
+ std::equal_to<_Value>,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits, false>::
+ _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();)
+ {
+ std::size_t __x_count = 1;
+ auto __itx_end = __itx;
+ for (++__itx_end; __itx_end != __this->end()
+ && __this->key_eq()(*__itx_end, *__itx); ++__itx_end)
+ ++__x_count;
+
+ if (__x_count != __other.count(*__itx))
+ return false;
+
+ __itx = __itx_end;
+ }
+ return true;
+ }
+
/**
* This type deals with all allocation and keeps an allocator instance
* through inheritance to benefit from EBO when possible.
diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc
b/libstdc++-v3/src/c++11/hashtable_c++0x.cc
index de8e2c7cb91..2054791e13a 100644
--- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc
+++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc
@@ -30,6 +30,7 @@
#include <tuple>
#include <ext/aligned_buffer.h>
#include <ext/alloc_traits.h>
+#include <bits/stl_function.h> // equal_to, _Identity, _Select1st
#include <bits/hashtable_policy.h>
namespace std _GLIBCXX_VISIBILITY(default)
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;
}
