Index: benchmarks/unordered_set_comp.bench.cpp
===================================================================
--- /dev/null
+++ benchmarks/unordered_set_comp.bench.cpp
@@ -0,0 +1,136 @@
+// This benchmarks the difference between the old comparison (old_comp)
+// and new comparison (is_permutation) methods for unordered multisets.
+
+#include <unordered_set>
+
+#include "benchmark/benchmark.h"
+
+using namespace std;
+
+unordered_multiset<int> u1;
+unordered_multiset<int> u2;
+
+unordered_multiset<int> u1_small;
+unordered_multiset<int> u2_small;
+
+unordered_multiset<int> u1_small_range;
+unordered_multiset<int> u2_small_range;
+
+template <class V, class H, class P, class A>
+bool
+old_comp(const unordered_multiset<V, H, P, A>& x,
+         const unordered_multiset<V, H, P, A>& y)
+{
+    typedef typename unordered_multiset<V, H, P, A>::const_iterator const_iterator;
+    typedef pair<const_iterator, const_iterator> pair_t;
+    for (const_iterator i = x.begin(), __ex = x.end(); i != __ex;)
+    {
+        pair_t xeq = x.equal_range(*i);
+        pair_t yeq = y.equal_range(*i);
+        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;
+    }
+    return true;
+}
+
+void initialize_data(benchmark::State&)
+{
+    // large set
+    for (unsigned i = 0; i < 1000 * 1000; ++i)
+    {
+        u1.insert(i);
+        u2.insert(i);
+    }
+    for (unsigned i = 0; i < 1000 * 10; ++i)
+    {
+        u1.insert(i % 100);
+        u2.insert(i % 100);
+    }
+
+    // small set
+    for (unsigned i = 0; i < 500; ++i)
+    {
+        u1_small.insert(i);
+        u2_small.insert(i);
+    }
+    for (unsigned i = 0; i < 500; ++i)
+    {
+        u1_small.insert(i % 10);
+        u2_small.insert(i % 10);
+    }
+
+    // small range
+    for (unsigned i = 0; i < 1000; ++i)
+    {
+        u1_small_range.insert(i % 2);
+        u2_small_range.insert(i % 2);
+    }
+}
+
+void test_small_old(benchmark::State& st)
+{
+    while (st.KeepRunning()) {
+        bool val = old_comp(u1_small, u2_small);
+        benchmark::DoNotOptimize(val);
+    }
+}
+
+void test_small_new(benchmark::State& st)
+{
+    while (st.KeepRunning()) {
+        bool val = is_permutation(u1_small.begin(), u1_small.end(), u2_small.begin());
+        benchmark::DoNotOptimize(val);
+    }
+}
+
+void test_small_range_old(benchmark::State& st)
+{
+    while (st.KeepRunning()) {
+        bool val = old_comp(u1_small_range, u2_small_range);
+        benchmark::DoNotOptimize(val);
+    }
+}
+
+void test_small_range_new(benchmark::State& st)
+{
+    while (st.KeepRunning()) {
+        bool val = is_permutation(u1_small_range.begin(),
+                                  u1_small_range.end(),
+                                  u2_small_range.begin());
+        benchmark::DoNotOptimize(val);
+    }
+}
+
+void test_big_old(benchmark::State& st)
+{
+    while (st.KeepRunning()) {
+        bool val = old_comp(u1, u2);
+        benchmark::DoNotOptimize(val);
+    }
+}
+
+void test_big_new(benchmark::State& st)
+{
+    while (st.KeepRunning()) {
+        bool val = is_permutation(u1.begin(), u1.end(), u2.begin());
+        benchmark::DoNotOptimize(val);
+    }
+}
+
+BENCHMARK(initialize_data); // TODO: how do I initialize this?
+
+BENCHMARK(test_small_old);
+BENCHMARK(test_small_new);
+
+BENCHMARK(test_small_range_old);
+BENCHMARK(test_small_range_new);
+
+BENCHMARK(test_big_old);
+BENCHMARK(test_big_new);
+
+BENCHMARK_MAIN();
+
+
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 <class InputIterator>
-      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<value_type> il, size_type n, const allocator_type& a)
       : unordered_map(il, n, hasher(), key_equal(), a) {}  // C++14
-    unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf, 
+    unordered_map(initializer_list<value_type> 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 <class InputIterator>
-      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<value_type> il, size_type n, const allocator_type& a)
       : unordered_multimap(il, n, hasher(), key_equal(), a) {}  // C++14
-    unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf, 
+    unordered_multimap(initializer_list<value_type> 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 <class _InputIterator>
     _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<value_type> __il, size_type __n, const allocator_type& __a)
       : unordered_map(__il, __n, hasher(), key_equal(), __a) {}
     _LIBCPP_INLINE_VISIBILITY
-    unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf, 
+    unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
       const allocator_type& __a)
       : unordered_map(__il, __n, __hf, key_equal(), __a) {}
 #endif
@@ -1644,13 +1644,13 @@
 {
     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;
+    for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex; ++__i)
     {
-        const_iterator __j = __y.find(__i->first);
-        if (__j == __ey || !(*__i == *__j))
+        const_iterator __found = __y.find(__i->first);
+        if (__found == __y.end() || !(*__found == *__i))
             return false;
     }
     return true;
@@ -1778,14 +1778,14 @@
       : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {}
     template <class _InputIterator>
     _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<value_type> __il, size_type __n, const allocator_type& __a)
       : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {}
     _LIBCPP_INLINE_VISIBILITY
-    unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf, 
+    unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
       const allocator_type& __a)
       : unordered_multimap(__il, __n, __hf, key_equal(), __a) {}
 #endif
@@ -2271,20 +2271,7 @@
 {
     if (__x.size() != __y.size())
         return false;
-    typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
-                                                                 const_iterator;
-    typedef pair<const_iterator, const_iterator> _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;
+    return _VSTD::is_permutation(__x.begin(), __x.end(), __y.begin());
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Index: include/unordered_set
===================================================================
--- include/unordered_set
+++ include/unordered_set
@@ -75,7 +75,7 @@
     template <class InputIterator>
       unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
     template <class InputIterator>
-      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<value_type> il, size_type n, const allocator_type& a); // C++14
     unordered_set(initializer_list<value_type> 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<value_type> il, size_type n, const allocator_type& a); // C++14
-    unordered_multiset(initializer_list<value_type> il, size_type n, 
+    unordered_multiset(initializer_list<value_type> 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 <class _InputIterator>
     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 <class _InputIterator>
-        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<value_type> __il, size_type __n, 
+    unordered_set(initializer_list<value_type> __il, size_type __n,
                                   const hasher& __hf, const allocator_type& __a)
         : unordered_set(__il, __n, __hf, key_equal(), __a) {}
 #endif
@@ -957,13 +957,12 @@
 {
     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;
+    for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex; ++__i)
     {
-        const_iterator __j = __y.find(*__i);
-        if (__j == __ey || !(*__i == *__j))
+        if (__y.find(*__i) == __y.end())
             return false;
     }
     return true;
@@ -1052,7 +1051,7 @@
 #if _LIBCPP_STD_VER > 11
     template <class _InputIterator>
     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 <class _InputIterator>
@@ -1530,20 +1529,7 @@
 {
     if (__x.size() != __y.size())
         return false;
-    typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
-                                                                 const_iterator;
-    typedef pair<const_iterator, const_iterator> _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;
+    return _VSTD::is_permutation(__x.begin(), __x.end(), __y.begin());
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>