diff --git a/libcxx/benchmarks/ContainerBenchmarks.h b/libcxx/benchmarks/ContainerBenchmarks.h --- a/libcxx/benchmarks/ContainerBenchmarks.h +++ b/libcxx/benchmarks/ContainerBenchmarks.h @@ -179,6 +179,38 @@ } } +template +static void BM_Compare_equal_true(benchmark::State& st, Container, GenInputs gen) { + auto in = gen(st.range(0)); + Container c1(in.begin(), in.end()); + Container c2 = c1; + + benchmark::DoNotOptimize(&(*c1.begin())); + benchmark::DoNotOptimize(&(*c2.begin())); + while (st.KeepRunning()) { + bool res = c1 == c2; + benchmark::DoNotOptimize(&res); + benchmark::ClobberMemory(); + } +} + +template +static void BM_Compare_equal_false(benchmark::State& st, Container, GenInputs gen) { + auto in1 = gen(st.range(0)); + auto in2 = gen(st.range(0)); + Container c1(in1.begin(), in1.end()); + Container c2 = c1; + c2.insert(in2.begin(), in2.end()); + + benchmark::DoNotOptimize(&(*c1.begin())); + benchmark::DoNotOptimize(&(*c2.begin())); + while (st.KeepRunning()) { + bool res = c1 == c2; + benchmark::DoNotOptimize(&res); + benchmark::ClobberMemory(); + } +} + } // end namespace ContainerBenchmarks #endif // BENCHMARK_CONTAINER_BENCHMARKS_H diff --git a/libcxx/benchmarks/unordered_set_operations.bench.cpp b/libcxx/benchmarks/unordered_set_operations.bench.cpp --- a/libcxx/benchmarks/unordered_set_operations.bench.cpp +++ b/libcxx/benchmarks/unordered_set_operations.bench.cpp @@ -290,6 +290,22 @@ BENCHMARK_CAPTURE(BM_Rehash, unordered_set_int_arg, std::unordered_set{}, getRandomIntegerInputs) ->Arg(TestNumInputs); +//----------------------------------------------------------------------------// +// BM_Compare +// ---------------------------------------------------------------------------// + +BENCHMARK_CAPTURE(BM_Compare_equal_true, unordered_set_string, std::unordered_set{}, getRandomStringInputs) + ->Arg(TestNumInputs); + +BENCHMARK_CAPTURE(BM_Compare_equal_true, unordered_set_int, std::unordered_set{}, getRandomIntegerInputs) + ->Arg(TestNumInputs); + +BENCHMARK_CAPTURE(BM_Compare_equal_false, unordered_set_string, std::unordered_set{}, getRandomStringInputs) + ->Arg(TestNumInputs); + +BENCHMARK_CAPTURE(BM_Compare_equal_false, unordered_set_int, std::unordered_set{}, getRandomIntegerInputs) + ->Arg(TestNumInputs); + /////////////////////////////////////////////////////////////////////////////// BENCHMARK_CAPTURE(BM_InsertDuplicate, unordered_set_int, std::unordered_set{}, getRandomIntegerInputs) ->Arg(TestNumInputs); diff --git a/libcxx/include/unordered_map b/libcxx/include/unordered_map --- a/libcxx/include/unordered_map +++ b/libcxx/include/unordered_map @@ -584,6 +584,7 @@ */ #include <__algorithm/is_permutation.h> +#include <__algorithm/mismatch.h> #include <__assert> // all public C++ headers provide the assertion handler #include <__availability> #include <__config> @@ -2748,16 +2749,22 @@ { if (__x.size() != __y.size()) return false; - typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::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)) + typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator; + typedef pair _IteratorRange; + + // First advance both sequences until we find a mismatch. If the two unordered maps + // happen to be in the same order, this can be a lot faster than doing repeated lookups. + const_iterator const __xend = __x.end(); + _IteratorRange __mismatch = std::mismatch(__x.begin(), __xend, __y.begin()); + + // Then compare the "tail" of the unordered maps using repeated lookups. + // Note that we need to check with std::is_permutation because equal_range only considers + // the keys, not the values. + for (const_iterator __i = __mismatch.first; __i != __xend;) { + _IteratorRange __xeq = __x.equal_range(__i->first); + _IteratorRange __yeq = __y.equal_range(__i->first); + if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) || + !std::is_permutation(__xeq.first, __xeq.second, __yeq.first)) return false; __i = __xeq.second; } diff --git a/libcxx/include/unordered_set b/libcxx/include/unordered_set --- a/libcxx/include/unordered_set +++ b/libcxx/include/unordered_set @@ -527,7 +527,7 @@ */ -#include <__algorithm/is_permutation.h> +#include <__algorithm/mismatch.h> #include <__assert> // all public C++ headers provide the assertion handler #include <__availability> #include <__config> @@ -1928,16 +1928,19 @@ { if (__x.size() != __y.size()) return false; - typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::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)) + typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator; + typedef pair _IteratorRange; + + // First advance both sequences until we find a mismatch. If the two unordered sets + // happen to be in the same order, this can be a lot faster than doing repeated lookups. + const_iterator const __xend = __x.end(); + _IteratorRange __mismatch = std::mismatch(__x.begin(), __xend, __y.begin()); + + // Then compare the "tail" of the unordered sets using repeated lookups. + for (const_iterator __i = __mismatch.first; __i != __xend;) { + _IteratorRange __xeq = __x.equal_range(*__i); + _IteratorRange __yeq = __y.equal_range(*__i); + if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second)) return false; __i = __xeq.second; } diff --git a/libcxx/test/std/containers/unord/unord.multimap/eq.pass.cpp b/libcxx/test/std/containers/unord/unord.multimap/eq.pass.cpp --- a/libcxx/test/std/containers/unord/unord.multimap/eq.pass.cpp +++ b/libcxx/test/std/containers/unord/unord.multimap/eq.pass.cpp @@ -221,5 +221,30 @@ } #endif - return 0; + // Make sure we take into account the number of times that a key repeats into equality. + { + typedef std::pair P; + P a[] = {{1, 'a'}, {1, 'b'}, {1, 'd'}, {2, 'b'}}; + P b[] = {{1, 'a'}, {1, 'b'}, {1, 'b'}, {1, 'd'}, {2, 'b'}}; + + std::unordered_multimap c1(std::begin(a), std::end(a)); + std::unordered_multimap c2(std::begin(b), std::end(b)); + assert(testEquality(c1, c2, false)); + } + + // Make sure we incorporate the values into the equality of the maps. + // If we were to compare only the keys (including how many time each key repeats), + // the following test would fail cause only the values differ. + { + typedef std::pair P; + P a[] = {{1, 'a'}, {1, 'b'}, {1, 'd'}, {2, 'b'}}; + P b[] = {{1, 'a'}, {1, 'b'}, {1, 'E'}, {2, 'b'}}; + // ^ different here + + std::unordered_multimap c1(std::begin(a), std::end(a)); + std::unordered_multimap c2(std::begin(b), std::end(b)); + assert(testEquality(c1, c2, false)); + } + + return 0; } diff --git a/libcxx/test/std/containers/unord/unord.multiset/eq.pass.cpp b/libcxx/test/std/containers/unord/unord.multiset/eq.pass.cpp --- a/libcxx/test/std/containers/unord/unord.multiset/eq.pass.cpp +++ b/libcxx/test/std/containers/unord/unord.multiset/eq.pass.cpp @@ -24,6 +24,8 @@ #include "test_macros.h" #include "min_allocator.h" +#include "test_comparisons.h" + int main(int, char**) { { @@ -178,5 +180,16 @@ } #endif - return 0; + // Make sure we take into account the number of times that a key repeats into equality. + { + typedef int P; + P a[] = {P(1), P(1), P(1), P(2)}; + P b[] = {P(1), P(1), P(1), P(1), P(2)}; + + std::unordered_multiset c1(std::begin(a), std::end(a)); + std::unordered_multiset c2(std::begin(b), std::end(b)); + assert(testEquality(c1, c2, false)); + } + + return 0; }