Index: include/unordered_map =================================================================== --- include/unordered_map +++ include/unordered_map @@ -79,12 +79,12 @@ unordered_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a) : unordered_map(f, l, n, hasher(), key_equal(), a) {} // C++14 template - unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf, + unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf, const allocator_type& a) : unordered_map(f, l, n, hf, key_equal(), a) {} // C++14 unordered_map(initializer_list il, size_type n, const allocator_type& a) : unordered_map(il, n, hasher(), key_equal(), a) {} // C++14 - unordered_map(initializer_list il, size_type n, const hasher& hf, + unordered_map(initializer_list il, size_type n, const hasher& hf, const allocator_type& a) : unordered_map(il, n, hf, key_equal(), a) {} // C++14 ~unordered_map(); @@ -277,12 +277,12 @@ unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a) : unordered_multimap(f, l, n, hasher(), key_equal(), a) {} // C++14 template - unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf, + unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf, const allocator_type& a) : unordered_multimap(f, l, n, hf, key_equal(), a) {} // C++14 unordered_multimap(initializer_list il, size_type n, const allocator_type& a) : unordered_multimap(il, n, hasher(), key_equal(), a) {} // C++14 - unordered_multimap(initializer_list il, size_type n, const hasher& hf, + unordered_multimap(initializer_list il, size_type n, const hasher& hf, const allocator_type& a) : unordered_multimap(il, n, hf, key_equal(), a) {} // C++14 ~unordered_multimap(); @@ -951,14 +951,14 @@ : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {} template _LIBCPP_INLINE_VISIBILITY - unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, + unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a) : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {} _LIBCPP_INLINE_VISIBILITY unordered_map(initializer_list __il, size_type __n, const allocator_type& __a) : unordered_map(__il, __n, hasher(), key_equal(), __a) {} _LIBCPP_INLINE_VISIBILITY - unordered_map(initializer_list __il, size_type __n, const hasher& __hf, + unordered_map(initializer_list __il, size_type __n, const hasher& __hf, const allocator_type& __a) : unordered_map(__il, __n, __hf, key_equal(), __a) {} #endif @@ -1637,6 +1637,41 @@ { __libcpp_erase_if_container(__c, __pred); } #endif +#if _LIBCPP_STD_VER > 17 +template +bool operator==(const unordered_map<_Key, _Tp, _Hash1, _Pred, _Alloc1> &__x, + const unordered_map<_Key, _Tp, _Hash2, _Pred, _Alloc2> &__y) +{ + if (__x.size() != __y.size()) + return false; + typedef + typename unordered_map<_Key, _Tp, _Hash1, _Pred, _Alloc1>::const_iterator + const_iterator; + typedef pair _EqRng; + for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) + { + _EqRng __xeq = __x.equal_range(__i->first); + _EqRng __yeq = __y.equal_range(__i->first); + if (_VSTD::distance(__xeq.first, __xeq.second) != + _VSTD::distance(__yeq.first, __yeq.second) || + !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) + return false; + __i = __xeq.second; + } + return true; +} + +template +inline _LIBCPP_INLINE_VISIBILITY +bool +operator!=(const unordered_map<_Key, _Tp, _Hash1, _Pred, _Alloc1> &__x, + const unordered_map<_Key, _Tp, _Hash2, _Pred, _Alloc2> &__y) +{ + return !(__x == __y); +} +#else template bool operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, @@ -1644,14 +1679,19 @@ { if (__x.size() != __y.size()) return false; - typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator - const_iterator; - for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); - __i != __ex; ++__i) + typedef + typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator + const_iterator; + typedef pair _EqRng; + for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) { - const_iterator __j = __y.find(__i->first); - if (__j == __ey || !(*__i == *__j)) + _EqRng __xeq = __x.equal_range(__i->first); + _EqRng __yeq = __y.equal_range(__i->first); + if (_VSTD::distance(__xeq.first, __xeq.second) != + _VSTD::distance(__yeq.first, __yeq.second) || + !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) return false; + __i = __xeq.second; } return true; } @@ -1664,6 +1704,7 @@ { return !(__x == __y); } +#endif // _LIBCPP_STD_VER > 17 template , class _Pred = equal_to<_Key>, class _Alloc = allocator > > @@ -1778,14 +1819,14 @@ : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {} template _LIBCPP_INLINE_VISIBILITY - unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, + unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a) : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {} _LIBCPP_INLINE_VISIBILITY unordered_multimap(initializer_list __il, size_type __n, const allocator_type& __a) : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {} _LIBCPP_INLINE_VISIBILITY - unordered_multimap(initializer_list __il, size_type __n, const hasher& __hf, + unordered_multimap(initializer_list __il, size_type __n, const hasher& __hf, const allocator_type& __a) : unordered_multimap(__il, __n, __hf, key_equal(), __a) {} #endif @@ -2264,6 +2305,39 @@ { __libcpp_erase_if_container(__c, __pred); } #endif +#if _LIBCPP_STD_VER > 17 +template +bool operator==(const unordered_multimap<_Key, _Tp, _Hash1, _Pred, _Alloc1> &__x, + const unordered_multimap<_Key, _Tp, _Hash2, _Pred, _Alloc2> &__y) +{ + if (__x.size() != __y.size()) + return false; + typedef + typename unordered_map<_Key, _Tp, _Hash1, _Pred, _Alloc1>::const_iterator + const_iterator; + typedef pair _EqRng; + for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) + { + _EqRng __xeq = __x.equal_range(__i->first); + _EqRng __yeq = __y.equal_range(__i->first); + if (_VSTD::distance(__xeq.first, __xeq.second) != + _VSTD::distance(__yeq.first, __yeq.second) || + !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) + return false; + __i = __xeq.second; + } + return true; +} + +template +bool operator!=(const unordered_multimap<_Key, _Tp, _Hash1, _Pred, _Alloc1> &__x, + const unordered_multimap<_Key, _Tp, _Hash2, _Pred, _Alloc2> &__y) +{ + return !(__x == __y); +} +#else template bool operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, @@ -2295,6 +2369,7 @@ { return !(__x == __y); } +#endif // _LIBCPP_STD_VER > 17 _LIBCPP_END_NAMESPACE_STD Index: include/unordered_set =================================================================== --- include/unordered_set +++ include/unordered_set @@ -75,7 +75,7 @@ template unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14 template - unordered_set(InputIterator f, InputIterator l, size_type n, + unordered_set(InputIterator f, InputIterator l, size_type n, const hasher& hf, const allocator_type& a); // C++14 unordered_set(initializer_list il, size_type n, const allocator_type& a); // C++14 unordered_set(initializer_list il, size_type n, @@ -242,7 +242,7 @@ unordered_multiset(InputIterator f, InputIterator l, size_type n, const hasher& hf, const allocator_type& a); // C++14 unordered_multiset(initializer_list il, size_type n, const allocator_type& a); // C++14 - unordered_multiset(initializer_list il, size_type n, + unordered_multiset(initializer_list il, size_type n, const hasher& hf, const allocator_type& a); // C++14 ~unordered_multiset(); unordered_multiset& operator=(const unordered_multiset&); @@ -450,11 +450,11 @@ #if _LIBCPP_STD_VER > 11 template inline _LIBCPP_INLINE_VISIBILITY - unordered_set(_InputIterator __first, _InputIterator __last, + unordered_set(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {} template - unordered_set(_InputIterator __first, _InputIterator __last, + unordered_set(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a) : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {} #endif @@ -480,7 +480,7 @@ const allocator_type& __a) : unordered_set(__il, __n, hasher(), key_equal(), __a) {} inline _LIBCPP_INLINE_VISIBILITY - unordered_set(initializer_list __il, size_type __n, + unordered_set(initializer_list __il, size_type __n, const hasher& __hf, const allocator_type& __a) : unordered_set(__il, __n, __hf, key_equal(), __a) {} #endif @@ -950,6 +950,42 @@ { __libcpp_erase_if_container(__c, __pred); } #endif +#if _LIBCPP_STD_VER > 17 +template +bool +operator==(const unordered_set<_Value, _Hash1, _Pred, _Alloc1>& __x, + const unordered_set<_Value, _Hash2, _Pred, _Alloc2>& __y) +{ + if (__x.size() != __y.size()) + return false; + typedef + typename unordered_set<_Value, _Hash1, _Pred, _Alloc1>::const_iterator + const_iterator; + typedef pair _EqRng; + for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) + { + _EqRng __xeq = __x.equal_range(*__i); + _EqRng __yeq = __y.equal_range(*__i); + if (_VSTD::distance(__xeq.first, __xeq.second) != + _VSTD::distance(__yeq.first, __yeq.second) || + !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) + return false; + __i = __xeq.second; + } + return true; +} + +template +inline _LIBCPP_INLINE_VISIBILITY +bool +operator!=(const unordered_set<_Value, _Hash1, _Pred, _Alloc1>& __x, + const unordered_set<_Value, _Hash2, _Pred, _Alloc2>& __y) +{ + return !(__x == __y); +} +#else template bool operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, @@ -957,14 +993,19 @@ { if (__x.size() != __y.size()) return false; - typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator - const_iterator; - for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); - __i != __ex; ++__i) + typedef + typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator + const_iterator; + typedef pair _EqRng; + for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) { - const_iterator __j = __y.find(*__i); - if (__j == __ey || !(*__i == *__j)) + _EqRng __xeq = __x.equal_range(*__i); + _EqRng __yeq = __y.equal_range(*__i); + if (_VSTD::distance(__xeq.first, __xeq.second) != + _VSTD::distance(__yeq.first, __yeq.second) || + !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) return false; + __i = __xeq.second; } return true; } @@ -977,6 +1018,7 @@ { return !(__x == __y); } +#endif // _LIBCPP_STD_VER > 17 template , class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> > @@ -1052,7 +1094,7 @@ #if _LIBCPP_STD_VER > 11 template inline _LIBCPP_INLINE_VISIBILITY - unordered_multiset(_InputIterator __first, _InputIterator __last, + unordered_multiset(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {} template @@ -1523,6 +1565,42 @@ { __libcpp_erase_if_container(__c, __pred); } #endif +#if _LIBCPP_STD_VER > 17 +template +bool +operator==(const unordered_multiset<_Value, _Hash1, _Pred, _Alloc1>& __x, + const unordered_multiset<_Value, _Hash2, _Pred, _Alloc2>& __y) +{ + if (__x.size() != __y.size()) + return false; + typedef + typename unordered_multiset<_Value, _Hash1, _Pred, _Alloc1>::const_iterator + const_iterator; + typedef pair _EqRng; + for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) + { + _EqRng __xeq = __x.equal_range(*__i); + _EqRng __yeq = __y.equal_range(*__i); + if (_VSTD::distance(__xeq.first, __xeq.second) != + _VSTD::distance(__yeq.first, __yeq.second) || + !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) + return false; + __i = __xeq.second; + } + return true; +} + +template +inline _LIBCPP_INLINE_VISIBILITY +bool +operator!=(const unordered_multiset<_Value, _Hash1, _Pred, _Alloc1>& __x, + const unordered_multiset<_Value, _Hash2, _Pred, _Alloc2>& __y) +{ + return !(__x == __y); +} +#else template bool operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, @@ -1554,6 +1632,7 @@ { return !(__x == __y); } +#endif // _LIBCPP_STD_VER > 17 _LIBCPP_END_NAMESPACE_STD Index: test/std/containers/unord/unord.map/comp_different_hash.pass.cpp =================================================================== --- /dev/null +++ test/std/containers/unord/unord.map/comp_different_hash.pass.cpp @@ -0,0 +1,106 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++98, c++03, c++11, c++14, c++17 + +// template +// bool operator==( const unordered_map& lhs, +// const unordered_map& rhs ); + +// template +// bool operator!=( const unordered_map& lhs, +// const unordered_map& rhs ); + +#include +#include + +// Hasher that behaves in the same way as std::hash, but is a different object. +template +struct other_hash +{ + std::size_t operator()(T const& value) const + { + return std::hash()(value); + } +}; + +template +void fill(Map& map, Itter begin, Itter end) +{ + for (; begin != end; ++begin) + { map.insert(*begin); } +} + +template +void test(Values... values) +{ + using set_a = std::unordered_multimap>; + using set_b = std::unordered_multimap>; + std::pair ordered[] = { values... }; + std::size_t const size = sizeof(ordered) / sizeof(std::pair); + + { + set_a a; + set_b b; + + fill(a, ordered, ordered + size); + fill(b, ordered, ordered + size); + + assert(a == b); + } + { + set_a a; + set_b b; + + fill(a, ordered, ordered + size - 1); + fill(b, ordered + 1, ordered + size); + + assert(a != b); + } + { + set_a a; + set_b b; + + fill(a, ordered, ordered + size); + fill(b, ordered + 1, ordered + size); + + assert(a != b); + } + { + set_a a; + set_b b; + + fill(a, ordered, ordered + size); + fill(b, ordered, ordered + size); + + // TODO: make `a` and `b` have different order + + // assert(std::is_permutation(std::begin(a), std::end(a), std::begin(b)) == false); + // assert(a != b); + } +} + +int main(int, char**) +{ + test(std::make_pair(1, 1), + std::make_pair(2, 2), + std::make_pair(3, 3), + std::make_pair(4, 4), + std::make_pair(5, 5)); + test(std::make_pair(true, true), + std::make_pair(true, false), + std::make_pair(false, true), + std::make_pair(false, false)); + test(std::make_pair("a", 0), + std::make_pair("b", 0), + std::make_pair("cde", 1)); + + return 0; +} Index: test/std/containers/unord/unord.multimap/comp_different_hash.pass.cpp =================================================================== --- /dev/null +++ test/std/containers/unord/unord.multimap/comp_different_hash.pass.cpp @@ -0,0 +1,107 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++98, c++03, c++11, c++14, c++17 + +// template +// bool operator==( const unordered_multimap& lhs, +// const unordered_multimap& rhs ); + +// template +// bool operator!=( const unordered_multimap& lhs, +// const unordered_multimap& rhs ); + +#include +#include + +// Hasher that behaves in the same way as std::hash, but is a different object. +template +struct other_hash +{ + std::size_t operator()(T const& value) const + { + return std::hash()(value); + } +}; + +template +void fill(Map& map, Itter begin, Itter end) +{ + for (; begin != end; ++begin) + { map.insert(*begin); } +} + +template +void test(Values... values) +{ + using set_a = std::unordered_multimap>; + using set_b = std::unordered_multimap>; + std::pair ordered[] = { values... }; + std::size_t const size = sizeof(ordered) / sizeof(std::pair); + + { + set_a a; + set_b b; + + fill(a, ordered, ordered + size); + fill(b, ordered, ordered + size); + + assert(a == b); + } + { + set_a a; + set_b b; + + fill(a, ordered, ordered + size - 1); + fill(b, ordered + 1, ordered + size); + + assert(a != b); + } + { + set_a a; + set_b b; + + fill(a, ordered, ordered + size); + fill(b, ordered + 1, ordered + size); + + assert(a != b); + } + { + set_a a; + set_b b; + + fill(a, ordered, ordered + size); + fill(b, ordered, ordered + size); + + // TODO: make `a` and `b` have different order + + // assert(std::is_permutation(std::begin(a), std::end(a), std::begin(b)) == false); + // assert(a != b); + } +} + +int main(int, char**) +{ + test(std::make_pair(1, 1), + std::make_pair(2, 2), + std::make_pair(3, 3), + std::make_pair(4, 4), + std::make_pair(5, 5)); + test(std::make_pair(true, true), + std::make_pair(true, true), + std::make_pair(true, false), + std::make_pair(false, true), + std::make_pair(false, false)); + test(std::make_pair("a", 0), + std::make_pair("b", 0), + std::make_pair("cde", 1)); + + return 0; +} Index: test/std/containers/unord/unord.multiset/comp_different_hash.pass.cpp =================================================================== --- /dev/null +++ test/std/containers/unord/unord.multiset/comp_different_hash.pass.cpp @@ -0,0 +1,97 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++98, c++03, c++11, c++14, c++17 + +// template +// bool operator==( const unordered_multiset& lhs, +// const unordered_multiset& rhs ); + +// template +// bool operator!=( const unordered_multiset& lhs, +// const unordered_multiset& rhs ); + +#include +#include + +// Hasher that behaves in the same way as std::hash, but is a different object. +template +struct other_hash +{ + std::size_t operator()(T const& value) const + { + return std::hash()(value); + } +}; + +template +void fill(Set& set, Itter begin, Itter end) +{ + for (; begin != end; ++begin) + { set.insert(*begin); } +} + +template +void test(Values... values) +{ + using set_a = std::unordered_multiset>; + using set_b = std::unordered_multiset>; + T ordered[] = { values... }; + std::size_t const size = sizeof(ordered) / sizeof(T); + + { + set_a a; + set_b b; + + fill(a, ordered, ordered + size); + fill(b, ordered, ordered + size); + + assert(a == b); + } + { + set_a a; + set_b b; + + fill(a, ordered, ordered + size - 1); + fill(b, ordered + 1, ordered + size); + + assert(a != b); + } + { + set_a a; + set_b b; + + fill(a, ordered, ordered + size); + fill(b, ordered + 1, ordered + size); + + assert(a != b); + } + { + set_a a; + set_b b; + + fill(a, ordered, ordered + size); + fill(b, ordered, ordered + size); + + // TODO: make `a` and `b` have different order + + // assert(std::is_permutation(std::begin(a), std::end(a), std::begin(b)) == false); + // assert(a != b); + } +} + +int main(int, char**) +{ + test(1, 2, 3, 4, 5); + test(true, true, false); + test("a", "b", "cde"); + + return 0; +} Index: test/std/containers/unord/unord.set/comp_different_hash.pass.cpp =================================================================== --- /dev/null +++ test/std/containers/unord/unord.set/comp_different_hash.pass.cpp @@ -0,0 +1,97 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++98, c++03, c++11, c++14, c++17 + +// template +// bool operator==( const unordered_set& lhs, +// const unordered_set& rhs ); + +// template +// bool operator!=( const unordered_set& lhs, +// const unordered_set& rhs ); + +#include +#include + +// Hasher that behaves in the same way as std::hash, but is a different object. +template +struct other_hash +{ + std::size_t operator()(T const& value) const + { + return std::hash()(value); + } +}; + +template +void fill(Set& set, Itter begin, Itter end) +{ + for (; begin != end; ++begin) + { set.insert(*begin); } +} + +template +void test(Values... values) +{ + using set_a = std::unordered_set>; + using set_b = std::unordered_set>; + T ordered[] = { values... }; + std::size_t const size = sizeof(ordered) / sizeof(T); + + { + set_a a; + set_b b; + + fill(a, ordered, ordered + size); + fill(b, ordered, ordered + size); + + assert(a == b); + } + { + set_a a; + set_b b; + + fill(a, ordered, ordered + size - 1); + fill(b, ordered + 1, ordered + size); + + assert(a != b); + } + { + set_a a; + set_b b; + + fill(a, ordered, ordered + size); + fill(b, ordered + 1, ordered + size); + + assert(a != b); + } + { + set_a a; + set_b b; + + fill(a, ordered, ordered + size); + fill(b, ordered, ordered + size); + + // TODO: make `a` and `b` have different order + + // assert(std::is_permutation(std::begin(a), std::end(a), std::begin(b)) == false); + // assert(a != b); + } +} + +int main(int, char**) +{ + test(1, 2, 3, 4, 5); + test(true, false); + test("a", "b", "cde"); + + return 0; +}