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 ==.
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.
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.
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; + + 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. + 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, + 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; + } + 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; }