[libc++] [test] Iterator non-invalidation tests for list and unordered_*

[• Quuxplusone]

Summary

This is a patch series split out of D100595. A few tests over there were verifying that iterators were not invalidated on swap/move of various containers... but they were doing it only in debug-iterator mode. We should do those tests in all modes. These days we can rely on the debug_level=1 CI job to run the tests in debug-iterator mode.
I plan to land this if buildkite is happy with it.

commit 4344af48dced153a47dfc4ccd673279e3071c0a9
Author: Arthur O'Dwyer <[e-mail]>
Date: Thu May 6 12:50:52 2021 -0400

[libc++] [test] Test that unordered_* move-construct/move-assign does not invalidate iterators.

And remove the dedicated debug-iterator tests; we want to test this in all modes.
We have a CI step for testing the whole test suite with `--debug_level=1` now.

commit 64f343334538e762c8be0c947dbc12a28c4430e8
Author: Arthur O'Dwyer <[e-mail]>
Date: Thu May 6 12:18:09 2021 -0400

[libc++] [test] Test that unordered_*::swap does not invalidate iterators.

commit fc90d836c31d781efb6ee73bc5d628949e8bced8
Author: Arthur O'Dwyer <[e-mail]>
Date: Thu May 6 12:05:08 2021 -0400

[libc++] [test] Test that list move-construct/move-assign does not invalidate iterators.

And remove the dedicated debug-iterator test; we want to test this in all modes.
We have a CI step for testing the whole test suite with `--debug_level=1` now.

commit 15f4cf46c1024368d222a34b24886c32dcd6f805
Author: Arthur O'Dwyer <[e-mail]>
Date: Thu May 6 11:53:10 2021 -0400

[libc++] [test] Simplify arithmetic in list.special/swap.pass.cpp. NFCI.

commit 1b731aacd63121eb2243d9a94e6280d81f686d5f
Author: Arthur O'Dwyer <[e-mail]>
Date: Thu May 6 11:42:25 2021 -0400

[libc++] [test] Test that list::swap does not invalidate iterators.

[krisb]

LGTM, thank you!

[• Quuxplusone]

Merged f42355e17c3f3d1d099d028a388796a64724ffdb et prev

libcxx/test/libcxx/containers/sequences/list/list.cons/db_move.pass.cpp

-//===----------------------------------------------------------------------===//
-//
-// 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
-//
-//===----------------------------------------------------------------------===//
-
-// <list>
-
-// list(list&& c);
-
-// UNSUPPORTED: c++03
-// UNSUPPORTED: libcxx-no-debug-mode
-
-// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DEBUG=1
-#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(1))
-
-#include <list>
-#include <cstdlib>
-#include <cassert>
-#include "test_macros.h"
-#include "MoveOnly.h"
-#include "test_allocator.h"
-#include "min_allocator.h"
-
-int main(int, char**)
-{
-    std::list<int> l1 = {1, 2, 3};
-    std::list<int>::iterator i = l1.begin();
-    std::list<int> l2 = std::move(l1);
-    assert(*l2.erase(i) == 2);
-
-  return 0;
-}

libcxx/test/libcxx/containers/unord/unord.map/db_move.pass.cpp

-//===----------------------------------------------------------------------===//
-//
-// 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
-//
-//===----------------------------------------------------------------------===//
-
-// <unordered_map>
-
-// unordered_map(unordered_map&& u);
-
-// UNSUPPORTED: c++03
-// UNSUPPORTED: libcxx-no-debug-mode
-
-// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DEBUG=1
-#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0))
-
-#include <unordered_map>
-#include <cassert>
-#include <utility>
-
-#include "test_macros.h"
-
-int main(int, char**) {
-    std::unordered_map<int, int> s1 = {{1, 1}, {2, 2}, {3, 3}};
-    std::unordered_map<int, int>::iterator i = s1.begin();
-    std::pair<const int, int> k = *i;
-    std::unordered_map<int, int> s2 = std::move(s1);
-    assert(*i == k);
-    s2.erase(i);
-    assert(s2.size() == 2);
-
-    return 0;
-}

libcxx/test/libcxx/containers/unord/unord.multimap/db_move.pass.cpp

-//===----------------------------------------------------------------------===//
-//
-// 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++03
-
-// <unordered_map>
-
-// unordered_multimap(unordered_multimap&& u);
-
-// UNSUPPORTED: libcxx-no-debug-mode
-
-// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DEBUG=1
-#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0))
-
-#include <unordered_map>
-#include <cassert>
-#include <utility>
-
-#include "test_macros.h"
-
-int main(int, char**) {
-    std::unordered_multimap<int, int> s1 = {{1, 1}, {2, 2}, {3, 3}};
-    std::unordered_multimap<int, int>::iterator i = s1.begin();
-    std::pair<const int, int> k = *i;
-    std::unordered_multimap<int, int> s2 = std::move(s1);
-    assert(*i == k);
-    s2.erase(i);
-    assert(s2.size() == 2);
-
-    return 0;
-}

libcxx/test/libcxx/containers/unord/unord.multiset/db_move.pass.cpp

-//===----------------------------------------------------------------------===//
-//
-// 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++03
-
-// <unordered_set>
-
-// unordered_multiset(unordered_multiset&& u);
-
-// UNSUPPORTED: libcxx-no-debug-mode
-
-// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DEBUG=1
-#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0))
-
-#include <unordered_set>
-#include <cassert>
-#include <utility>
-
-#include "test_macros.h"
-
-int main(int, char**) {
-    std::unordered_multiset<int> s1 = {1, 2, 3};
-    std::unordered_multiset<int>::iterator i = s1.begin();
-    int k = *i;
-    std::unordered_multiset<int> s2 = std::move(s1);
-    assert(*i == k);
-    s2.erase(i);
-    assert(s2.size() == 2);
-
-    return 0;
-}

libcxx/test/libcxx/containers/unord/unord.set/db_move.pass.cpp

-//===----------------------------------------------------------------------===//
-//
-// 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++03
-// UNSUPPORTED: libcxx-no-debug-mode
-
-// <unordered_set>
-
-// unordered_set(unordered_set&& u);
-
-// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DEBUG=1
-#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0))
-
-#include <unordered_set>
-#include <cassert>
-#include <utility>
-
-#include "test_macros.h"
-
-int main(int, char**) {
-    std::unordered_set<int> s1 = {1, 2, 3};
-    std::unordered_set<int>::iterator i = s1.begin();
-    int k = *i;
-    std::unordered_set<int> s2 = std::move(s1);
-    assert(*i == k);
-    s2.erase(i);
-    assert(s2.size() == 2);
-
-    return 0;
-}

libcxx/test/std/containers/sequences/list/list.cons/assign_move.pass.cpp

int main(int, char**)
         std::list<MoveOnly, test_allocator<MoveOnly> > l(test_allocator<MoveOnly>(5));
         std::list<MoveOnly, test_allocator<MoveOnly> > lo(test_allocator<MoveOnly>(5));
         for (int i = 1; i <= 3; ++i)
         {
             l.push_back(i);
             lo.push_back(i);
         }
         std::list<MoveOnly, test_allocator<MoveOnly> > l2(test_allocator<MoveOnly>(5));
+        std::list<MoveOnly, test_allocator<MoveOnly> >::iterator it = l.begin();
         l2 = std::move(l);
         assert(l2 == lo);
         assert(l.empty());
         assert(l2.get_allocator() == lo.get_allocator());
+        assert(it == l2.begin());  // Iterators remain valid
     }
     {
         std::list<MoveOnly, test_allocator<MoveOnly> > l(test_allocator<MoveOnly>(5));
         std::list<MoveOnly, test_allocator<MoveOnly> > lo(test_allocator<MoveOnly>(5));
         for (int i = 1; i <= 3; ++i)
         {
             l.push_back(i);
             lo.push_back(i);
         }
         std::list<MoveOnly, test_allocator<MoveOnly> > l2(test_allocator<MoveOnly>(6));
         l2 = std::move(l);
         assert(l2 == lo);
         assert(!l.empty());
         assert(l2.get_allocator() == test_allocator<MoveOnly>(6));
     }
     {
         std::list<MoveOnly, other_allocator<MoveOnly> > l(other_allocator<MoveOnly>(5));
         std::list<MoveOnly, other_allocator<MoveOnly> > lo(other_allocator<MoveOnly>(5));
         for (int i = 1; i <= 3; ++i)
         {
             l.push_back(i);
             lo.push_back(i);
         }
         std::list<MoveOnly, other_allocator<MoveOnly> > l2(other_allocator<MoveOnly>(6));
+        std::list<MoveOnly, other_allocator<MoveOnly> >::iterator it = l.begin();
         l2 = std::move(l);
         assert(l2 == lo);
         assert(l.empty());
         assert(l2.get_allocator() == lo.get_allocator());
+        assert(it == l2.begin());  // Iterators remain valid
     }
     {
         std::list<MoveOnly, min_allocator<MoveOnly> > l(min_allocator<MoveOnly>{});
         std::list<MoveOnly, min_allocator<MoveOnly> > lo(min_allocator<MoveOnly>{});
         for (int i = 1; i <= 3; ++i)
         {
             l.push_back(i);
             lo.push_back(i);
         }
         std::list<MoveOnly, min_allocator<MoveOnly> > l2(min_allocator<MoveOnly>{});
+        std::list<MoveOnly, min_allocator<MoveOnly> >::iterator it = l.begin();
         l2 = std::move(l);
         assert(l2 == lo);
         assert(l.empty());
         assert(l2.get_allocator() == lo.get_allocator());
+        assert(it == l2.begin());  // Iterators remain valid
     }
 
   return 0;
 }

libcxx/test/std/containers/sequences/list/list.cons/move.pass.cpp

int main(int, char**)
     {
         std::list<MoveOnly, test_allocator<MoveOnly> > l(test_allocator<MoveOnly>(5));
         std::list<MoveOnly, test_allocator<MoveOnly> > lo(test_allocator<MoveOnly>(5));
         for (int i = 1; i <= 3; ++i)
         {
             l.push_back(i);
             lo.push_back(i);
         }
+        std::list<MoveOnly, test_allocator<MoveOnly> >::iterator it = l.begin();
         std::list<MoveOnly, test_allocator<MoveOnly> > l2 = std::move(l);
         assert(l2 == lo);
         assert(l.empty());
         assert(l2.get_allocator() == lo.get_allocator());
+        assert(it == l2.begin());  // Iterators remain valid
     }
     {
         std::list<MoveOnly, other_allocator<MoveOnly> > l(other_allocator<MoveOnly>(5));
         std::list<MoveOnly, other_allocator<MoveOnly> > lo(other_allocator<MoveOnly>(5));
         for (int i = 1; i <= 3; ++i)
         {
             l.push_back(i);
             lo.push_back(i);
         }
+        std::list<MoveOnly, other_allocator<MoveOnly> >::iterator it = l.begin();
         std::list<MoveOnly, other_allocator<MoveOnly> > l2 = std::move(l);
         assert(l2 == lo);
         assert(l.empty());
         assert(l2.get_allocator() == lo.get_allocator());
+        assert(it == l2.begin());  // Iterators remain valid
     }
     {
         std::list<MoveOnly, min_allocator<MoveOnly> > l(min_allocator<MoveOnly>{});
         std::list<MoveOnly, min_allocator<MoveOnly> > lo(min_allocator<MoveOnly>{});
         for (int i = 1; i <= 3; ++i)
         {
             l.push_back(i);
             lo.push_back(i);
         }
+        std::list<MoveOnly, min_allocator<MoveOnly> >::iterator it = l.begin();
         std::list<MoveOnly, min_allocator<MoveOnly> > l2 = std::move(l);
         assert(l2 == lo);
         assert(l.empty());
         assert(l2.get_allocator() == lo.get_allocator());
+        assert(it == l2.begin());  // Iterators remain valid
     }
 
   return 0;
 }

libcxx/test/std/containers/sequences/list/list.special/swap.pass.cpp

 #include "test_allocator.h"
 #include "min_allocator.h"
 
 int main(int, char**)
 {
     {
         int a1[] = {1, 3, 7, 9, 10};
         int a2[] = {0, 2, 4, 5, 6, 8, 11};
-        std::list<int> c1(a1, a1+sizeof(a1)/sizeof(a1[0]));
-        std::list<int> c2(a2, a2+sizeof(a2)/sizeof(a2[0]));
+        std::list<int> c1(a1, a1 + 5);
+        std::list<int> c2(a2, a2 + 7);
+        std::list<int>::iterator it1 = c1.begin();
+        std::list<int>::const_iterator it2 = c2.begin();
         swap(c1, c2);
-        assert(c1 == std::list<int>(a2, a2+sizeof(a2)/sizeof(a2[0])));
-        assert(c2 == std::list<int>(a1, a1+sizeof(a1)/sizeof(a1[0])));
+        assert(c1 == std::list<int>(a2, a2 + 7));
+        assert(c2 == std::list<int>(a1, a1 + 5));
+        assert(it1 == c2.begin()); // Iterators remain valid
+        assert(it2 == c1.begin()); // Iterators remain valid
     }
     {
-        int a1[] = {1, 3, 7, 9, 10};
         int a2[] = {0, 2, 4, 5, 6, 8, 11};
-        std::list<int> c1(a1, a1);
-        std::list<int> c2(a2, a2+sizeof(a2)/sizeof(a2[0]));
+        std::list<int> c1;
+        std::list<int> c2(a2, a2 + 7);
         swap(c1, c2);
-        assert(c1 == std::list<int>(a2, a2+sizeof(a2)/sizeof(a2[0])));
+        assert(c1 == std::list<int>(a2, a2 + 7));
         assert(c2.empty());
         assert(distance(c2.begin(), c2.end()) == 0);
     }
     {
         int a1[] = {1, 3, 7, 9, 10};
-        int a2[] = {0, 2, 4, 5, 6, 8, 11};
-        std::list<int> c1(a1, a1+sizeof(a1)/sizeof(a1[0]));
-        std::list<int> c2(a2, a2);
+        std::list<int> c1(a1, a1 + 5);
+        std::list<int> c2;
         swap(c1, c2);
         assert(c1.empty());
         assert(distance(c1.begin(), c1.end()) == 0);
-        assert(c2 == std::list<int>(a1, a1+sizeof(a1)/sizeof(a1[0])));
+        assert(c2 == std::list<int>(a1, a1 + 5));
     }
     {
-        int a1[] = {1, 3, 7, 9, 10};
-        int a2[] = {0, 2, 4, 5, 6, 8, 11};
-        std::list<int> c1(a1, a1);
-        std::list<int> c2(a2, a2);
+        std::list<int> c1;
+        std::list<int> c2;
         swap(c1, c2);
         assert(c1.empty());
         assert(distance(c1.begin(), c1.end()) == 0);
         assert(c2.empty());
         assert(distance(c2.begin(), c2.end()) == 0);
     }
     {
         int a1[] = {1, 3, 7, 9, 10};
         int a2[] = {0, 2, 4, 5, 6, 8, 11};
         typedef test_allocator<int> A;
-        std::list<int, A> c1(a1, a1+sizeof(a1)/sizeof(a1[0]), A(1));
-        std::list<int, A> c2(a2, a2+sizeof(a2)/sizeof(a2[0]), A(1));
+        std::list<int, A> c1(a1, a1 + 5, A(1));
+        std::list<int, A> c2(a2, a2 + 7, A(1));
         swap(c1, c2);
-        assert((c1 == std::list<int, A>(a2, a2+sizeof(a2)/sizeof(a2[0]))));
+        assert((c1 == std::list<int, A>(a2, a2 + 7)));
         assert(c1.get_allocator() == A(1));
-        assert((c2 == std::list<int, A>(a1, a1+sizeof(a1)/sizeof(a1[0]))));
+        assert((c2 == std::list<int, A>(a1, a1 + 5)));
         assert(c2.get_allocator() == A(1));
     }
     {
         int a1[] = {1, 3, 7, 9, 10};
         int a2[] = {0, 2, 4, 5, 6, 8, 11};
         typedef other_allocator<int> A;
-        std::list<int, A> c1(a1, a1+sizeof(a1)/sizeof(a1[0]), A(1));
-        std::list<int, A> c2(a2, a2+sizeof(a2)/sizeof(a2[0]), A(2));
+        std::list<int, A> c1(a1, a1 + 5, A(1));
+        std::list<int, A> c2(a2, a2 + 7, A(2));
         swap(c1, c2);
-        assert((c1 == std::list<int, A>(a2, a2+sizeof(a2)/sizeof(a2[0]))));
+        assert((c1 == std::list<int, A>(a2, a2 + 7)));
         assert(c1.get_allocator() == A(2));
-        assert((c2 == std::list<int, A>(a1, a1+sizeof(a1)/sizeof(a1[0]))));
+        assert((c2 == std::list<int, A>(a1, a1 + 5)));
         assert(c2.get_allocator() == A(1));
     }
 #if TEST_STD_VER >= 11
     {
         int a1[] = {1, 3, 7, 9, 10};
         int a2[] = {0, 2, 4, 5, 6, 8, 11};
-        std::list<int, min_allocator<int>> c1(a1, a1+sizeof(a1)/sizeof(a1[0]));
-        std::list<int, min_allocator<int>> c2(a2, a2+sizeof(a2)/sizeof(a2[0]));
+        std::list<int, min_allocator<int>> c1(a1, a1 + 5);
+        std::list<int, min_allocator<int>> c2(a2, a2 + 7);
         swap(c1, c2);
-        assert((c1 == std::list<int, min_allocator<int>>(a2, a2+sizeof(a2)/sizeof(a2[0]))));
-        assert((c2 == std::list<int, min_allocator<int>>(a1, a1+sizeof(a1)/sizeof(a1[0]))));
+        assert((c1 == std::list<int, min_allocator<int>>(a2, a2 + 7)));
+        assert((c2 == std::list<int, min_allocator<int>>(a1, a1 + 5)));
     }
     {
-        int a1[] = {1, 3, 7, 9, 10};
         int a2[] = {0, 2, 4, 5, 6, 8, 11};
-        std::list<int, min_allocator<int>> c1(a1, a1);
-        std::list<int, min_allocator<int>> c2(a2, a2+sizeof(a2)/sizeof(a2[0]));
+        std::list<int, min_allocator<int>> c1;
+        std::list<int, min_allocator<int>> c2(a2, a2 + 7);
         swap(c1, c2);
-        assert((c1 == std::list<int, min_allocator<int>>(a2, a2+sizeof(a2)/sizeof(a2[0]))));
+        assert((c1 == std::list<int, min_allocator<int>>(a2, a2 + 7)));
         assert(c2.empty());
         assert(distance(c2.begin(), c2.end()) == 0);
     }
     {
         int a1[] = {1, 3, 7, 9, 10};
-        int a2[] = {0, 2, 4, 5, 6, 8, 11};
-        std::list<int, min_allocator<int>> c1(a1, a1+sizeof(a1)/sizeof(a1[0]));
-        std::list<int, min_allocator<int>> c2(a2, a2);
+        std::list<int, min_allocator<int>> c1(a1, a1 + 5);
+        std::list<int, min_allocator<int>> c2;
         swap(c1, c2);
         assert(c1.empty());
         assert(distance(c1.begin(), c1.end()) == 0);
-        assert((c2 == std::list<int, min_allocator<int>>(a1, a1+sizeof(a1)/sizeof(a1[0]))));
+        assert((c2 == std::list<int, min_allocator<int>>(a1, a1 + 5)));
     }
     {
-        int a1[] = {1, 3, 7, 9, 10};
-        int a2[] = {0, 2, 4, 5, 6, 8, 11};
-        std::list<int, min_allocator<int>> c1(a1, a1);
-        std::list<int, min_allocator<int>> c2(a2, a2);
+        std::list<int, min_allocator<int>> c1;
+        std::list<int, min_allocator<int>> c2;
         swap(c1, c2);
         assert(c1.empty());
         assert(distance(c1.begin(), c1.end()) == 0);
         assert(c2.empty());
         assert(distance(c2.begin(), c2.end()) == 0);
     }
     {
         int a1[] = {1, 3, 7, 9, 10};
         int a2[] = {0, 2, 4, 5, 6, 8, 11};
         typedef min_allocator<int> A;
-        std::list<int, A> c1(a1, a1+sizeof(a1)/sizeof(a1[0]), A());
-        std::list<int, A> c2(a2, a2+sizeof(a2)/sizeof(a2[0]), A());
+        std::list<int, A> c1(a1, a1 + 5, A());
+        std::list<int, A> c2(a2, a2 + 7, A());
         swap(c1, c2);
-        assert((c1 == std::list<int, A>(a2, a2+sizeof(a2)/sizeof(a2[0]))));
+        assert((c1 == std::list<int, A>(a2, a2 + 7)));
         assert(c1.get_allocator() == A());
-        assert((c2 == std::list<int, A>(a1, a1+sizeof(a1)/sizeof(a1[0]))));
+        assert((c2 == std::list<int, A>(a1, a1 + 5)));
         assert(c2.get_allocator() == A());
     }
 #endif
 
     return 0;
 }

libcxx/test/std/containers/unord/unord.map/unord.map.cnstr/assign_move.pass.cpp

int main(int, char**)
             A(10)
            );
         C c(a, a + 2,
             7,
             test_hash<std::hash<int> >(2),
             test_compare<std::equal_to<int> >(3),
             A(10)
            );
+        C::iterator it0 = c0.begin();
         c = std::move(c0);
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 4);
         assert(c.at(1) == "one");
         assert(c.at(2) == "two");
         assert(c.at(3) == "three");
         assert(c.at(4) == "four");
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() == A(10));
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);
         assert(c0.size() == 0);
+        assert(it0 == c.begin()); // Iterators remain valid
     }
     {
         typedef other_allocator<std::pair<const int, std::string> > A;
         typedef std::unordered_map<int, std::string,
                                    test_hash<std::hash<int> >,
                                    test_compare<std::equal_to<int> >,
                                    A
                                    > C;
int main(int, char**)
             A(10)
            );
         C c(a, a + 2,
             7,
             test_hash<std::hash<int> >(2),
             test_compare<std::equal_to<int> >(3),
             A(4)
            );
+        C::iterator it0 = c0.begin();
         c = std::move(c0);
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 4);
         assert(c.at(1) == "one");
         assert(c.at(2) == "two");
         assert(c.at(3) == "three");
         assert(c.at(4) == "four");
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() == A(10));
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);
         assert(c0.size() == 0);
+        assert(it0 == c.begin()); // Iterators remain valid
     }
     {
         typedef min_allocator<std::pair<const int, std::string> > A;
         typedef std::unordered_map<int, std::string,
                                    test_hash<std::hash<int> >,
                                    test_compare<std::equal_to<int> >,
                                    A
                                    > C;
int main(int, char**)
             A()
            );
         C c(a, a + 2,
             7,
             test_hash<std::hash<int> >(2),
             test_compare<std::equal_to<int> >(3),
             A()
            );
+        C::iterator it0 = c0.begin();
         c = std::move(c0);
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 4);
         assert(c.at(1) == "one");
         assert(c.at(2) == "two");
         assert(c.at(3) == "three");
         assert(c.at(4) == "four");
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() == A());
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);
         assert(c0.size() == 0);
+        assert(it0 == c.begin()); // Iterators remain valid
     }
 
   return 0;
 }

libcxx/test/std/containers/unord/unord.map/unord.map.cnstr/move.pass.cpp

int main(int, char**)
                                    test_compare<std::equal_to<int> >,
                                    test_allocator<std::pair<const int, std::string> >
                                    > C;
         C c0(7,
             test_hash<std::hash<int> >(8),
             test_compare<std::equal_to<int> >(9),
             test_allocator<std::pair<const int, std::string> >(10)
            );
+        C::iterator it0 = c0.begin();
         C c = std::move(c0);
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 0);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() ==
                (test_allocator<std::pair<const int, std::string> >(10)));
         assert(c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(c.load_factor() == 0);
         assert(c.max_load_factor() == 1);
+        assert(it0 == c.begin()); // Iterators remain valid
 
         assert(c0.empty());
     }
     {
         typedef std::unordered_map<int, std::string,
                                    test_hash<std::hash<int> >,
                                    test_compare<std::equal_to<int> >,
                                    test_allocator<std::pair<const int, std::string> >
int main(int, char**)
             P(2, "four"),
         };
         C c0(a, a + sizeof(a)/sizeof(a[0]),
             7,
             test_hash<std::hash<int> >(8),
             test_compare<std::equal_to<int> >(9),
             test_allocator<std::pair<const int, std::string> >(10)
            );
+        C::iterator it0 = c0.begin();
         C c = std::move(c0);
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 4);
         assert(c.at(1) == "one");
         assert(c.at(2) == "two");
         assert(c.at(3) == "three");
         assert(c.at(4) == "four");
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() ==
                (test_allocator<std::pair<const int, std::string> >(10)));
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(std::fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);
+        assert(it0 == c.begin()); // Iterators remain valid
 
         assert(c0.empty());
     }
     {
         typedef std::unordered_map<int, std::string,
                                    test_hash<std::hash<int> >,
                                    test_compare<std::equal_to<int> >,
                                    min_allocator<std::pair<const int, std::string> >
                                    > C;
         C c0(7,
             test_hash<std::hash<int> >(8),
             test_compare<std::equal_to<int> >(9),
             min_allocator<std::pair<const int, std::string> >()
            );
+        C::iterator it0 = c0.begin();
         C c = std::move(c0);
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 0);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() ==
                (min_allocator<std::pair<const int, std::string> >()));
         assert(c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(c.load_factor() == 0);
         assert(c.max_load_factor() == 1);
+        assert(it0 == c.begin()); // Iterators remain valid
 
         assert(c0.empty());
     }
     {
         typedef std::unordered_map<int, std::string,
                                    test_hash<std::hash<int> >,
                                    test_compare<std::equal_to<int> >,
                                    min_allocator<std::pair<const int, std::string> >
int main(int, char**)
             P(2, "four"),
         };
         C c0(a, a + sizeof(a)/sizeof(a[0]),
             7,
             test_hash<std::hash<int> >(8),
             test_compare<std::equal_to<int> >(9),
             min_allocator<std::pair<const int, std::string> >()
            );
+        C::iterator it0 = c0.begin();
         C c = std::move(c0);
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 4);
         assert(c.at(1) == "one");
         assert(c.at(2) == "two");
         assert(c.at(3) == "three");
         assert(c.at(4) == "four");
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() ==
                (min_allocator<std::pair<const int, std::string> >()));
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(std::fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);
+        assert(it0 == c.begin()); // Iterators remain valid
 
         assert(c0.empty());
     }
 
     return 0;
 }

libcxx/test/std/containers/unord/unord.map/unord.map.swap/swap_non_member.pass.cpp

int main(int, char**)
             P(50, "fifty"),
             P(60, "sixty"),
             P(70, "seventy"),
             P(80, "eighty"),
         };
         C c1(0, Hash(1), Compare(1), Alloc(1, 1));
         C c2(std::begin(a2), std::end(a2), 0, Hash(2), Compare(2), Alloc(1, 2));
         c2.max_load_factor(2);
+        C::iterator it2 = c2.begin();
         swap(c1, c2);
 
         assert(c1.bucket_count() >= 8);
         assert(c1.size() == 8);
         assert(c1.at(10) == "ten");
         assert(c1.at(20) == "twenty");
         assert(c1.at(30) == "thirty");
         assert(c1.at(40) == "forty");
         assert(c1.at(50) == "fifty");
         assert(c1.at(60) == "sixty");
         assert(c1.at(70) == "seventy");
         assert(c1.at(80) == "eighty");
         assert(c1.hash_function() == Hash(2));
         assert(c1.key_eq() == Compare(2));
         assert(c1.get_allocator().get_id() == 1);
         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
         assert(c1.max_load_factor() == 2);
+        assert(it2 == c1.begin()); // Iterators are not invalidated
 
         LIBCPP_ASSERT(c2.bucket_count() == 0);
         assert(c2.size() == 0);
         assert(c2.hash_function() == Hash(1));
         assert(c2.key_eq() == Compare(1));
         assert(c2.get_allocator().get_id() == 2);
         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
int main(int, char**)
             P(3, "three"),
             P(4, "four"),
             P(1, "four"),
             P(2, "four"),
         };
         C c1(std::begin(a1), std::end(a1), 0, Hash(1), Compare(1), Alloc(1, 1));
         C c2(0, Hash(2), Compare(2), Alloc(1, 2));
         c2.max_load_factor(2);
+        C::iterator it1 = c1.begin();
         swap(c1, c2);
 
         LIBCPP_ASSERT(c1.bucket_count() == 0);
         assert(c1.size() == 0);
         assert(c1.hash_function() == Hash(2));
         assert(c1.key_eq() == Compare(2));
         assert(c1.get_allocator().get_id() == 1);
         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
         assert(c1.max_load_factor() == 2);
 
         assert(c2.bucket_count() >= 4);
         assert(c2.size() == 4);
         assert(c2.at(1) == "one");
         assert(c2.at(2) == "two");
         assert(c2.at(3) == "three");
         assert(c2.at(4) == "four");
         assert(c2.hash_function() == Hash(1));
         assert(c2.key_eq() == Compare(1));
         assert(c2.get_allocator().get_id() == 2);
         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
         assert(c2.max_load_factor() == 1);
+        assert(it1 == c2.begin()); // Iterators are not invalidated
     }
     {
         typedef test_hash<std::hash<int> > Hash;
         typedef test_compare<std::equal_to<int> > Compare;
         typedef test_allocator<std::pair<const int, std::string> > Alloc;
         typedef std::unordered_map<int, std::string, Hash, Compare, Alloc> C;
         typedef std::pair<int, std::string> P;
         P a1[] =
int main(int, char**)
             P(50, "fifty"),
             P(60, "sixty"),
             P(70, "seventy"),
             P(80, "eighty"),
         };
         C c1(std::begin(a1), std::end(a1), 0, Hash(1), Compare(1), Alloc(1, 1));
         C c2(std::begin(a2), std::end(a2), 0, Hash(2), Compare(2), Alloc(1, 2));
         c2.max_load_factor(2);
+        C::iterator it1 = c1.begin();
+        C::iterator it2 = c2.begin();
         swap(c1, c2);
 
         assert(c1.bucket_count() >= 8);
         assert(c1.size() == 8);
         assert(c1.at(10) == "ten");
         assert(c1.at(20) == "twenty");
         assert(c1.at(30) == "thirty");
         assert(c1.at(40) == "forty");
         assert(c1.at(50) == "fifty");
         assert(c1.at(60) == "sixty");
         assert(c1.at(70) == "seventy");
         assert(c1.at(80) == "eighty");
         assert(c1.hash_function() == Hash(2));
         assert(c1.key_eq() == Compare(2));
         assert(c1.get_allocator().get_id() == 1);
         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
         assert(c1.max_load_factor() == 2);
+        assert(it2 == c1.begin()); // Iterators are not invalidated
 
         assert(c2.bucket_count() >= 4);
         assert(c2.size() == 4);
         assert(c2.at(1) == "one");
         assert(c2.at(2) == "two");
         assert(c2.at(3) == "three");
         assert(c2.at(4) == "four");
         assert(c2.hash_function() == Hash(1));
         assert(c2.key_eq() == Compare(1));
         assert(c2.get_allocator().get_id() == 2);
         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
         assert(c2.max_load_factor() == 1);
+        assert(it1 == c2.begin()); // Iterators are not invalidated
     }
 
     {
         typedef test_hash<std::hash<int> > Hash;
         typedef test_compare<std::equal_to<int> > Compare;
         typedef other_allocator<std::pair<const int, std::string> > Alloc;
         typedef std::unordered_map<int, std::string, Hash, Compare, Alloc> C;
         C c1(0, Hash(1), Compare(1), Alloc(1));

libcxx/test/std/containers/unord/unord.multimap/unord.multimap.cnstr/assign_move.pass.cpp

int main(int, char**)
             A(10)
            );
         C c(a, a + 2,
             7,
             test_hash<std::hash<int> >(2),
             test_compare<std::equal_to<int> >(3),
             A(10)
            );
+        C::iterator it0 = c0.begin();
         c = std::move(c0);
+        assert(it0 == c.begin()); // Iterators remain valid
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 6);
         typedef std::pair<C::const_iterator, C::const_iterator> Eq;
         Eq eq = c.equal_range(1);
         assert(std::distance(eq.first, eq.second) == 2);
         std::multiset<std::string> s;
         s.insert("one");
         s.insert("four");
int main(int, char**)
             A(10)
            );
         C c(a, a + 2,
             7,
             test_hash<std::hash<int> >(2),
             test_compare<std::equal_to<int> >(3),
             A(4)
            );
+        C::iterator it0 = c0.begin();
         c = std::move(c0);
+        assert(it0 == c.begin()); // Iterators remain valid
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 6);
         typedef std::pair<C::const_iterator, C::const_iterator> Eq;
         Eq eq = c.equal_range(1);
         assert(std::distance(eq.first, eq.second) == 2);
         std::multiset<std::string> s;
         s.insert("one");
         s.insert("four");
int main(int, char**)
             A()
            );
         C c(a, a + 2,
             7,
             test_hash<std::hash<int> >(2),
             test_compare<std::equal_to<int> >(3),
             A()
            );
+        C::iterator it0 = c0.begin();
         c = std::move(c0);
+        assert(it0 == c.begin()); // Iterators remain valid
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 6);
         typedef std::pair<C::const_iterator, C::const_iterator> Eq;
         Eq eq = c.equal_range(1);
         assert(std::distance(eq.first, eq.second) == 2);
         std::multiset<std::string> s;
         s.insert("one");
         s.insert("four");

libcxx/test/std/containers/unord/unord.multimap/unord.multimap.cnstr/move.pass.cpp

int main(int, char**)
             P(2, "four"),
         };
         C c0(a, a + sizeof(a)/sizeof(a[0]),
             7,
             test_hash<std::hash<int> >(8),
             test_compare<std::equal_to<int> >(9),
             test_allocator<std::pair<const int, std::string> >(10)
            );
+        C::iterator it0 = c0.begin();
         C c = std::move(c0);
+        assert(it0 == c.begin()); // Iterators remain valid
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 6);
         typedef std::pair<C::const_iterator, C::const_iterator> Eq;
         Eq eq = c.equal_range(1);
         assert(std::distance(eq.first, eq.second) == 2);
         std::multiset<std::string> s;
         s.insert("one");
         s.insert("four");
int main(int, char**)
             P(2, "four"),
         };
         C c0(a, a + sizeof(a)/sizeof(a[0]),
             7,
             test_hash<std::hash<int> >(8),
             test_compare<std::equal_to<int> >(9),
             min_allocator<std::pair<const int, std::string> >()
            );
+        C::iterator it0 = c0.begin();
         C c = std::move(c0);
+        assert(it0 == c.begin()); // Iterators remain valid
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 6);
         typedef std::pair<C::const_iterator, C::const_iterator> Eq;
         Eq eq = c.equal_range(1);
         assert(std::distance(eq.first, eq.second) == 2);
         std::multiset<std::string> s;
         s.insert("one");
         s.insert("four");

libcxx/test/std/containers/unord/unord.multimap/unord.multimap.swap/swap_non_member.pass.cpp

int main(int, char**)
             P(50, "fifty"),
             P(60, "sixty"),
             P(70, "seventy"),
             P(80, "eighty"),
         };
         C c1(0, Hash(1), Compare(1), Alloc(1, 1));
         C c2(std::begin(a2), std::end(a2), 0, Hash(2), Compare(2), Alloc(1, 2));
         c2.max_load_factor(2);
+        C::iterator it2 = c2.begin();
         swap(c1, c2);
 
         assert(c1.bucket_count() >= 8);
         assert(c1.size() == 8);
         assert(c1.find(10)->second == "ten");
         assert(c1.find(20)->second == "twenty");
         assert(c1.find(30)->second == "thirty");
         assert(c1.find(40)->second == "forty");
         assert(c1.find(50)->second == "fifty");
         assert(c1.find(60)->second == "sixty");
         assert(c1.find(70)->second == "seventy");
         assert(c1.find(80)->second == "eighty");
         assert(c1.hash_function() == Hash(2));
         assert(c1.key_eq() == Compare(2));
         assert(c1.get_allocator().get_id() == 1);
         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
         assert(c1.max_load_factor() == 2);
+        assert(it2 == c1.begin()); // Iterators are not invalidated
 
         LIBCPP_ASSERT(c2.bucket_count() == 0);
         assert(c2.size() == 0);
         assert(c2.hash_function() == Hash(1));
         assert(c2.key_eq() == Compare(1));
         assert(c2.get_allocator().get_id() == 2);
         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
int main(int, char**)
             P(3, "three"),
             P(4, "four"),
             P(1, "four"),
             P(2, "four"),
         };
         C c1(std::begin(a1), std::end(a1), 0, Hash(1), Compare(1), Alloc(1, 1));
         C c2(0, Hash(2), Compare(2), Alloc(1, 2));
         c2.max_load_factor(2);
+        C::iterator it1 = c1.begin();
         swap(c1, c2);
 
         LIBCPP_ASSERT(c1.bucket_count() == 0);
         assert(c1.size() == 0);
         assert(c1.hash_function() == Hash(2));
         assert(c1.key_eq() == Compare(2));
         assert(c1.get_allocator().get_id() == 1);
         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
int main(int, char**)
         assert(c2.find(3)->second == "three");
         assert(c2.find(4)->second == "four");
         assert(c2.hash_function() == Hash(1));
         assert(c2.key_eq() == Compare(1));
         assert(c2.get_allocator().get_id() == 2);
         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
         assert(c2.max_load_factor() == 1);
+        assert(it1 == c2.begin()); // Iterators are not invalidated
     }
     {
         typedef test_hash<std::hash<int> > Hash;
         typedef test_compare<std::equal_to<int> > Compare;
         typedef test_allocator<std::pair<const int, std::string> > Alloc;
         typedef std::unordered_multimap<int, std::string, Hash, Compare, Alloc> C;
         typedef std::pair<int, std::string> P;
         P a1[] =
int main(int, char**)
             P(50, "fifty"),
             P(60, "sixty"),
             P(70, "seventy"),
             P(80, "eighty"),
         };
         C c1(std::begin(a1), std::end(a1), 0, Hash(1), Compare(1), Alloc(1, 1));
         C c2(std::begin(a2), std::end(a2), 0, Hash(2), Compare(2), Alloc(1, 2));
         c2.max_load_factor(2);
+        C::iterator it1 = c1.begin();
+        C::iterator it2 = c2.begin();
         swap(c1, c2);
 
         assert(c1.bucket_count() >= 8);
         assert(c1.size() == 8);
         assert(c1.find(10)->second == "ten");
         assert(c1.find(20)->second == "twenty");
         assert(c1.find(30)->second == "thirty");
         assert(c1.find(40)->second == "forty");
         assert(c1.find(50)->second == "fifty");
         assert(c1.find(60)->second == "sixty");
         assert(c1.find(70)->second == "seventy");
         assert(c1.find(80)->second == "eighty");
         assert(c1.hash_function() == Hash(2));
         assert(c1.key_eq() == Compare(2));
         assert(c1.get_allocator().get_id() == 1);
         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
         assert(c1.max_load_factor() == 2);
+        assert(it2 == c1.begin()); // Iterators are not invalidated
 
         assert(c2.bucket_count() >= 6);
         assert(c2.size() == 6);
         std::multiset<std::string> s;
         s.insert("one");
         s.insert("four");
         CheckConsecutiveKeys<C::const_iterator>(c2.find(1), c2.end(), 1, s);
         s.insert("two");
         s.insert("four");
         CheckConsecutiveKeys<C::const_iterator>(c2.find(2), c2.end(), 2, s);
         assert(c2.find(3)->second == "three");
         assert(c2.find(4)->second == "four");
         assert(c2.hash_function() == Hash(1));
         assert(c2.key_eq() == Compare(1));
         assert(c2.get_allocator().get_id() == 2);
         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
         assert(c2.max_load_factor() == 1);
+        assert(it1 == c2.begin()); // Iterators are not invalidated
     }
 
     {
         typedef test_hash<std::hash<int> > Hash;
         typedef test_compare<std::equal_to<int> > Compare;
         typedef other_allocator<std::pair<const int, std::string> > Alloc;
         typedef std::unordered_multimap<int, std::string, Hash, Compare, Alloc> C;
         C c1(0, Hash(1), Compare(1), Alloc(1));

libcxx/test/std/containers/unord/unord.multiset/unord.multiset.cnstr/assign_move.pass.cpp

int main(int, char**)
             A(10)
            );
         C c(a, a + 2,
             7,
             test_hash<std::hash<int> >(2),
             test_compare<std::equal_to<int> >(3),
             A(10)
            );
+        C::iterator it0 = c0.begin();
         c = std::move(c0);
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 6);
         assert(c.count(1) == 2);
         assert(c.count(2) == 2);
         assert(c.count(3) == 1);
         assert(c.count(4) == 1);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() == A(10));
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);
+        assert(it0 == c.begin()); // Iterators remain valid
     }
     {
         typedef other_allocator<int> A;
         typedef std::unordered_multiset<int,
                                    test_hash<std::hash<int> >,
                                    test_compare<std::equal_to<int> >,
                                    A
                                    > C;
int main(int, char**)
             A(10)
            );
         C c(a, a + 2,
             7,
             test_hash<std::hash<int> >(2),
             test_compare<std::equal_to<int> >(3),
             A(4)
            );
+        C::iterator it0 = c0.begin();
         c = std::move(c0);
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 6);
         assert(c.count(1) == 2);
         assert(c.count(2) == 2);
         assert(c.count(3) == 1);
         assert(c.count(4) == 1);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() == A(10));
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);
+        assert(it0 == c.begin()); // Iterators remain valid
     }
     {
         typedef test_allocator<int> A;
         typedef std::unordered_multiset<int,
                                    test_hash<std::hash<int> >,
                                    test_compare<std::equal_to<int> >,
                                    A
                                    > C;
int main(int, char**)
             A()
            );
         C c(a, a + 2,
             7,
             test_hash<std::hash<int> >(2),
             test_compare<std::equal_to<int> >(3),
             A()
            );
+        C::iterator it0 = c0.begin();
         c = std::move(c0);
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 6);
         assert(c.count(1) == 2);
         assert(c.count(2) == 2);
         assert(c.count(3) == 1);
         assert(c.count(4) == 1);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() == A());
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);
+        assert(it0 == c.begin()); // Iterators remain valid
     }
     {
         typedef min_allocator<int> A;
         typedef std::unordered_multiset<int,
                                    test_hash<std::hash<int> >,
                                    test_compare<std::equal_to<int> >,
                                    A
                                    > C;
int main(int, char**)
             A()
            );
         C c(a, a + 2,
             7,
             test_hash<std::hash<int> >(2),
             test_compare<std::equal_to<int> >(3),
             A()
            );
+        C::iterator it0 = c0.begin();
         c = std::move(c0);
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 6);
         assert(c.count(1) == 2);
         assert(c.count(2) == 2);
         assert(c.count(3) == 1);
         assert(c.count(4) == 1);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() == A());
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);
+        assert(it0 == c.begin()); // Iterators remain valid
     }
 
   return 0;
 }

libcxx/test/std/containers/unord/unord.multiset/unord.multiset.cnstr/move.pass.cpp

int main(int, char**)
             P(2)
         };
         C c0(a, a + sizeof(a)/sizeof(a[0]),
             7,
             test_hash<std::hash<int> >(8),
             test_compare<std::equal_to<int> >(9),
             test_allocator<int>(10)
            );
+        C::iterator it0 = c0.begin();
         C c = std::move(c0);
+        assert(it0 == c.begin()); // Iterators remain valid
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 6);
         assert(c.count(1) == 2);
         assert(c.count(2) == 2);
         assert(c.count(3) == 1);
         assert(c.count(4) == 1);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
int main(int, char**)
             P(2)
         };
         C c0(a, a + sizeof(a)/sizeof(a[0]),
             7,
             test_hash<std::hash<int> >(8),
             test_compare<std::equal_to<int> >(9),
             min_allocator<int>()
            );
+        C::iterator it0 = c0.begin();
         C c = std::move(c0);
+        assert(it0 == c.begin()); // Iterators remain valid
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 6);
         assert(c.count(1) == 2);
         assert(c.count(2) == 2);
         assert(c.count(3) == 1);
         assert(c.count(4) == 1);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));

libcxx/test/std/containers/unord/unord.multiset/unord.multiset.swap/swap_non_member.pass.cpp

int main(int, char**)
             P(50),
             P(60),
             P(70),
             P(80)
         };
         C c1(0, Hash(1), Compare(1), Alloc(1, 1));
         C c2(std::begin(a2), std::end(a2), 0, Hash(2), Compare(2), Alloc(1, 2));
         c2.max_load_factor(2);
+        C::iterator it2 = c2.begin();
         swap(c1, c2);
 
         assert(c1.bucket_count() >= 8);
         assert(c1.size() == 8);
         assert(*c1.find(10) == 10);
         assert(*c1.find(20) == 20);
         assert(*c1.find(30) == 30);
         assert(*c1.find(40) == 40);
         assert(*c1.find(50) == 50);
         assert(*c1.find(60) == 60);
         assert(*c1.find(70) == 70);
         assert(*c1.find(80) == 80);
         assert(c1.hash_function() == Hash(2));
         assert(c1.key_eq() == Compare(2));
         assert(c1.get_allocator().get_id() == 1);
         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
         assert(c1.max_load_factor() == 2);
+        assert(it2 == c1.begin()); // Iterators are not invalidated
 
         LIBCPP_ASSERT(c2.bucket_count() == 0);
         assert(c2.size() == 0);
         assert(c2.hash_function() == Hash(1));
         assert(c2.key_eq() == Compare(1));
         assert(c2.get_allocator().get_id() == 2);
         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
int main(int, char**)
             P(3),
             P(4),
             P(1),
             P(2)
         };
         C c1(std::begin(a1), std::end(a1), 0, Hash(1), Compare(1), Alloc(1, 1));
         C c2(0, Hash(2), Compare(2), Alloc(1, 2));
         c2.max_load_factor(2);
+        C::iterator it1 = c1.begin();
         swap(c1, c2);
 
         LIBCPP_ASSERT(c1.bucket_count() == 0);
         assert(c1.size() == 0);
         assert(c1.hash_function() == Hash(2));
         assert(c1.key_eq() == Compare(2));
         assert(c1.get_allocator().get_id() == 1);
         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
         assert(c1.max_load_factor() == 2);
 
         assert(c2.bucket_count() >= 6);
         assert(c2.size() == 6);
         assert(c2.count(1) == 2);
         assert(c2.count(2) == 2);
         assert(c2.count(3) == 1);
         assert(c2.count(4) == 1);
         assert(c2.hash_function() == Hash(1));
         assert(c2.key_eq() == Compare(1));
         assert(c2.get_allocator().get_id() == 2);
         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
         assert(c2.max_load_factor() == 1);
+        assert(it1 == c2.begin()); // Iterators are not invalidated
     }
     {
         typedef test_hash<std::hash<int> > Hash;
         typedef test_compare<std::equal_to<int> > Compare;
         typedef test_allocator<int> Alloc;
         typedef std::unordered_multiset<int, Hash, Compare, Alloc> C;
         typedef int P;
         P a1[] =
int main(int, char**)
             P(50),
             P(60),
             P(70),
             P(80)
         };
         C c1(std::begin(a1), std::end(a1), 0, Hash(1), Compare(1), Alloc(1, 1));
         C c2(std::begin(a2), std::end(a2), 0, Hash(2), Compare(2), Alloc(1, 2));
         c2.max_load_factor(2);
+        C::iterator it1 = c1.begin();
+        C::iterator it2 = c2.begin();
         swap(c1, c2);
 
         assert(c1.bucket_count() >= 8);
         assert(c1.size() == 8);
         assert(*c1.find(10) == 10);
         assert(*c1.find(20) == 20);
         assert(*c1.find(30) == 30);
         assert(*c1.find(40) == 40);
         assert(*c1.find(50) == 50);
         assert(*c1.find(60) == 60);
         assert(*c1.find(70) == 70);
         assert(*c1.find(80) == 80);
         assert(c1.hash_function() == Hash(2));
         assert(c1.key_eq() == Compare(2));
         assert(c1.get_allocator().get_id() == 1);
         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
         assert(c1.max_load_factor() == 2);
+        assert(it2 == c1.begin()); // Iterators are not invalidated
 
         assert(c2.bucket_count() >= 6);
         assert(c2.size() == 6);
         assert(c2.count(1) == 2);
         assert(c2.count(2) == 2);
         assert(c2.count(3) == 1);
         assert(c2.count(4) == 1);
         assert(c2.hash_function() == Hash(1));
         assert(c2.key_eq() == Compare(1));
         assert(c2.get_allocator().get_id() == 2);
         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
         assert(c2.max_load_factor() == 1);
+        assert(it1 == c2.begin()); // Iterators are not invalidated
     }
 
     {
         typedef test_hash<std::hash<int> > Hash;
         typedef test_compare<std::equal_to<int> > Compare;
         typedef other_allocator<int> Alloc;
         typedef std::unordered_multiset<int, Hash, Compare, Alloc> C;
         C c1(0, Hash(1), Compare(1), Alloc(1));

libcxx/test/std/containers/unord/unord.set/unord.set.cnstr/assign_move.pass.cpp

int main(int, char**)
             A(10)
            );
         C c(a, a + 2,
             7,
             test_hash<std::hash<int> >(2),
             test_compare<std::equal_to<int> >(3),
             A(10)
            );
+        C::iterator it0 = c0.begin();
         c = std::move(c0);
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 4);
         assert(c.count(1) == 1);
         assert(c.count(2) == 1);
         assert(c.count(3) == 1);
         assert(c.count(4) == 1);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() == A(10));
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);
+        assert(it0 == c.begin()); // Iterators remain valid
     }
     {
         typedef other_allocator<int> A;
         typedef std::unordered_set<int,
                                    test_hash<std::hash<int> >,
                                    test_compare<std::equal_to<int> >,
                                    A
                                    > C;
int main(int, char**)
             A(10)
            );
         C c(a, a + 2,
             7,
             test_hash<std::hash<int> >(2),
             test_compare<std::equal_to<int> >(3),
             A(4)
            );
+        C::iterator it0 = c0.begin();
         c = std::move(c0);
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 4);
         assert(c.count(1) == 1);
         assert(c.count(2) == 1);
         assert(c.count(3) == 1);
         assert(c.count(4) == 1);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() == A(10));
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);
+        assert(it0 == c.begin()); // Iterators remain valid
     }
     {
         typedef min_allocator<int> A;
         typedef std::unordered_set<int,
                                    test_hash<std::hash<int> >,
                                    test_compare<std::equal_to<int> >,
                                    A
                                    > C;
int main(int, char**)
             A()
            );
         C c(a, a + 2,
             7,
             test_hash<std::hash<int> >(2),
             test_compare<std::equal_to<int> >(3),
             A()
            );
+        C::iterator it0 = c0.begin();
         c = std::move(c0);
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 4);
         assert(c.count(1) == 1);
         assert(c.count(2) == 1);
         assert(c.count(3) == 1);
         assert(c.count(4) == 1);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() == A());
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);
+        assert(it0 == c.begin()); // Iterators remain valid
     }
 
   return 0;
 }

libcxx/test/std/containers/unord/unord.set/unord.set.cnstr/move.pass.cpp

int main(int, char**)
             P(2)
         };
         C c0(a, a + sizeof(a)/sizeof(a[0]),
             7,
             test_hash<std::hash<int> >(8),
             test_compare<std::equal_to<int> >(9),
             test_allocator<int>(10)
            );
+        C::iterator it0 = c0.begin();
         C c = std::move(c0);
+        assert(it0 == c.begin()); // Iterators remain valid
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 4);
         assert(c.count(1) == 1);
         assert(c.count(2) == 1);
         assert(c.count(3) == 1);
         assert(c.count(4) == 1);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
int main(int, char**)
             P(2)
         };
         C c0(a, a + sizeof(a)/sizeof(a[0]),
             7,
             test_hash<std::hash<int> >(8),
             test_compare<std::equal_to<int> >(9),
             min_allocator<int>()
            );
+        C::iterator it0 = c0.begin();
         C c = std::move(c0);
+        assert(it0 == c.begin()); // Iterators remain valid
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 4);
         assert(c.count(1) == 1);
         assert(c.count(2) == 1);
         assert(c.count(3) == 1);
         assert(c.count(4) == 1);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));

libcxx/test/std/containers/unord/unord.set/unord.set.swap/swap_non_member.pass.cpp

int main(int, char**)
             P(50),
             P(60),
             P(70),
             P(80)
         };
         C c1(0, Hash(1), Compare(1), Alloc(1, 1));
         C c2(std::begin(a2), std::end(a2), 0, Hash(2), Compare(2), Alloc(1, 2));
         c2.max_load_factor(2);
+        C::iterator it2 = c2.begin();
         swap(c1, c2);
 
         assert(c1.bucket_count() >= 8);
         assert(c1.size() == 8);
         assert(*c1.find(10) == 10);
         assert(*c1.find(20) == 20);
         assert(*c1.find(30) == 30);
         assert(*c1.find(40) == 40);
         assert(*c1.find(50) == 50);
         assert(*c1.find(60) == 60);
         assert(*c1.find(70) == 70);
         assert(*c1.find(80) == 80);
         assert(c1.hash_function() == Hash(2));
         assert(c1.key_eq() == Compare(2));
         assert(c1.get_allocator().get_id() == 1);
         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
         assert(c1.max_load_factor() == 2);
+        assert(it2 == c1.begin()); // Iterators are not invalidated
 
         LIBCPP_ASSERT(c2.bucket_count() == 0);
         assert(c2.size() == 0);
         assert(c2.hash_function() == Hash(1));
         assert(c2.key_eq() == Compare(1));
         assert(c2.get_allocator().get_id() == 2);
         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
int main(int, char**)
             P(3),
             P(4),
             P(1),
             P(2)
         };
         C c1(std::begin(a1), std::end(a1), 0, Hash(1), Compare(1), Alloc(1, 1));
         C c2(0, Hash(2), Compare(2), Alloc(1, 2));
         c2.max_load_factor(2);
+        C::iterator it1 = c1.begin();
         swap(c1, c2);
 
         LIBCPP_ASSERT(c1.bucket_count() == 0);
         assert(c1.size() == 0);
         assert(c1.hash_function() == Hash(2));
         assert(c1.key_eq() == Compare(2));
         assert(c1.get_allocator().get_id() == 1);
         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
         assert(c1.max_load_factor() == 2);
 
         assert(c2.bucket_count() >= 4);
         assert(c2.size() == 4);
         assert(c2.count(1) == 1);
         assert(c2.count(2) == 1);
         assert(c2.count(3) == 1);
         assert(c2.count(4) == 1);
         assert(c2.hash_function() == Hash(1));
         assert(c2.key_eq() == Compare(1));
         assert(c2.get_allocator().get_id() == 2);
         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
         assert(c2.max_load_factor() == 1);
+        assert(it1 == c2.begin()); // Iterators are not invalidated
     }
     {
         typedef test_hash<std::hash<int> > Hash;
         typedef test_compare<std::equal_to<int> > Compare;
         typedef test_allocator<int> Alloc;
         typedef std::unordered_set<int, Hash, Compare, Alloc> C;
         typedef int P;
         P a1[] =
int main(int, char**)
             P(50),
             P(60),
             P(70),
             P(80)
         };
         C c1(std::begin(a1), std::end(a1), 0, Hash(1), Compare(1), Alloc(1, 1));
         C c2(std::begin(a2), std::end(a2), 0, Hash(2), Compare(2), Alloc(1, 2));
         c2.max_load_factor(2);
+        C::iterator it1 = c1.begin();
+        C::iterator it2 = c2.begin();
         swap(c1, c2);
 
         assert(c1.bucket_count() >= 8);
         assert(c1.size() == 8);
         assert(*c1.find(10) == 10);
         assert(*c1.find(20) == 20);
         assert(*c1.find(30) == 30);
         assert(*c1.find(40) == 40);
         assert(*c1.find(50) == 50);
         assert(*c1.find(60) == 60);
         assert(*c1.find(70) == 70);
         assert(*c1.find(80) == 80);
         assert(c1.hash_function() == Hash(2));
         assert(c1.key_eq() == Compare(2));
         assert(c1.get_allocator().get_id() == 1);
         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
         assert(c1.max_load_factor() == 2);
+        assert(it2 == c1.begin()); // Iterators are not invalidated
 
         assert(c2.bucket_count() >= 4);
         assert(c2.size() == 4);
         assert(c2.count(1) == 1);
         assert(c2.count(2) == 1);
         assert(c2.count(3) == 1);
         assert(c2.count(4) == 1);
         assert(c2.hash_function() == Hash(1));
         assert(c2.key_eq() == Compare(1));
         assert(c2.get_allocator().get_id() == 2);
         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
         assert(c2.max_load_factor() == 1);
+        assert(it1 == c2.begin()); // Iterators are not invalidated
     }
 
     {
         typedef test_hash<std::hash<int> > Hash;
         typedef test_compare<std::equal_to<int> > Compare;
         typedef other_allocator<int> Alloc;
         typedef std::unordered_set<int, Hash, Compare, Alloc> C;
         C c1(0, Hash(1), Compare(1), Alloc(1));