Patchwork Fix libstdc++/55043 - issue with nesting unordered_map containing unique_ptr into vector

login
register
mail settings
Submitter Jonathan Wakely
Date Feb. 18, 2013, 10:40 p.m.
Message ID <CAH6eHdRYeDEKwmHaRSUikNjTVPuCWxVjnZ2RTgduU1Z8N8kXBg@mail.gmail.com>
Download mbox | patch
Permalink /patch/221541/
State New
Headers show

Comments

Jonathan Wakely - Feb. 18, 2013, 10:40 p.m.
On 16 January 2013 23:57, Jonathan Wakely wrote:
> Here's another attempt to fix this regression, I hope this time it
> doesn't cause more problems than it solves.
>
> Instead of specializing is_copy_constructible for the unordered
> containers this causes their copy constructors to be deleted if the
> value_type is not CopyInsertable into the container.  This makes
> is_copy_constructible naturally give the right result, and so
> __move_if_noexcept does the right thing and the testcase in the PR
> passes. Yay.
>
> As Daniel pointed out in the PR comments, the unfortunate side effect
> of this approach is that we can no longer support instantiating
> unordered containers with incomplete types. That's undefined
> behaviour, but was allowed as QoI.  Conformance trumps QoI, I'm
> afraid.  If someday we have noexcept move constructors for the
> unordered containers we could allow incomplete types again.
>
>         PR libstdc++/55043 (again)
>         * include/bits/alloc_traits.h (allocator_traits::construct): Disable
>         unless construction would be well-formed.
>         (__allow_copy_cons, __check_copy_constructible): Define.
>         * include/bits/unordered_map.h (__check_copy_constructible): Use as
>         base class so copy constructor will be deleted if appropriate.
>         (is_copy_constructible): Remove specialization.
>         * include/bits/unordered_set.h: Likewise.
>         * include/debug/unordered_map.h: Undo previous commit. Default copy
>         and move constructors.
>         * include/debug/unordered_set.h: Likewise.
>         * include/profile/unordered_map.h: Undo previous commit.
>         * include/profile/unordered_set.h: Likewise.
>         * testsuite/23_containers/unordered_map/55043.cc: Fix test.
>         * testsuite/23_containers/unordered_multimap/55043.cc: Likewise.
>         * testsuite/23_containers/unordered_multiset/55043.cc: Likewise.
>         * testsuite/23_containers/unordered_set/55043.cc: Likewise.
>         * testsuite/23_containers/unordered_map/requirements/53339.cc: XFAIL,
>         cannot support incomplete types.
>         * testsuite/23_containers/unordered_multimap/requirements/53339.cc:
>         Likewise.
>
> Tested x86_86-linux, committed to trunk.

I plan to commit the attached to the 4.7 branch to fix the regression there too.
commit 0162956f34307f5918c0c022485547297e59a1d8
Author: Jonathan Wakely <jwakely.gcc@gmail.com>
Date:   Mon Feb 18 21:26:45 2013 +0000

    	PR libstdc++/55043
    	* include/bits/alloc_traits.h (allocator_traits::construct): Disable
    	unless construction would be well-formed.
    	(__allow_copy_cons, __check_copy_constructible): Define.
    	* include/bits/unordered_map.h (__check_copy_constructible): Use as
    	base class so copy constructor will be deleted if appropriate.
    	* include/bits/unordered_set.h: Likewise.
    	* include/std/unordered_set: Include alloc_traits.h.
    	* include/std/unordered_set: Likewise.
    	* include/debug/unordered_map.h: Default copy and move constructors.
    	* include/debug/unordered_set.h: Likewise.
    	* testsuite/23_containers/unordered_map/55043.cc: Fix test.
    	* testsuite/23_containers/unordered_multimap/55043.cc: Likewise.
    	* testsuite/23_containers/unordered_multiset/55043.cc: Likewise.
    	* testsuite/23_containers/unordered_set/55043.cc: Likewise.
    	* testsuite/23_containers/unordered_map/requirements/53339.cc: XFAIL,
    	cannot support incomplete types.
    	* testsuite/23_containers/unordered_multimap/requirements/53339.cc:
    	Likewise.
    	* testsuite/23_containers/unordered_set/instantiation_neg.cc: Adjust
    	dg-error line number.

Patch

diff --git a/libstdc++-v3/include/bits/alloc_traits.h b/libstdc++-v3/include/bits/alloc_traits.h
index 3b12981..bfa50de 100644
--- a/libstdc++-v3/include/bits/alloc_traits.h
+++ b/libstdc++-v3/include/bits/alloc_traits.h
@@ -1,6 +1,6 @@ 
 // Allocator traits -*- C++ -*-
 
-// Copyright (C) 2011, 2012 Free Software Foundation, Inc.
+// Copyright (C) 2011, 2012, 2013 Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
 // software; you can redistribute it and/or modify it under the
@@ -39,6 +39,9 @@  namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
+  template<typename _Tp>
+    class allocator;
+
   template<typename _Alloc, typename _Tp>
     class __alloctr_rebind_helper
     {
@@ -254,7 +257,8 @@  _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_swap,
 
       template<typename _Tp, typename... _Args>
 	static typename
-       	enable_if<!__construct_helper<_Tp, _Args...>::value, void>::type
+	enable_if<__and_<__not_<__construct_helper<_Tp, _Args...>>,
+			 is_constructible<_Tp, _Args...>>::value, void>::type
        	_S_construct(_Alloc&, _Tp* __p, _Args&&... __args)
 	{ ::new((void*)__p) _Tp(std::forward<_Args>(__args)...); }
 
@@ -386,7 +390,8 @@  _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_swap,
        *  arguments @a __args...
       */
       template<typename _Tp, typename... _Args>
-	static void construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
+	static auto construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
+	-> decltype(_S_construct(__a, __p, std::forward<_Args>(__args)...))
 	{ _S_construct(__a, __p, std::forward<_Args>(__args)...); }
 
       /**
@@ -506,6 +511,56 @@  _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_swap,
       __do_alloc_on_swap(__one, __two, __pocs());
     }
 
+  template<typename _Alloc>
+    class __is_copy_insertable_impl
+    {
+      typedef allocator_traits<_Alloc> _Traits;
+
+      template<typename _Up, typename
+	       = decltype(_Traits::construct(std::declval<_Alloc&>(),
+					     std::declval<_Up*>(),
+					     std::declval<const _Up&>()))>
+	static true_type
+	_M_select(int);
+
+      template<typename _Up>
+	static false_type
+	_M_select(...);
+
+    public:
+      typedef decltype(_M_select<typename _Alloc::value_type>(0)) type;
+    };
+
+  // true if _Alloc::value_type is CopyInsertable into containers using _Alloc
+  template<typename _Alloc>
+    struct __is_copy_insertable
+    : __is_copy_insertable_impl<_Alloc>::type
+    { };
+
+  // std::allocator<_Tp> just requires CopyConstructible
+  template<typename _Tp>
+    struct __is_copy_insertable<allocator<_Tp>>
+    : is_copy_constructible<_Tp>
+    { };
+
+  // Used to allow copy construction of unordered containers
+  template<bool> struct __allow_copy_cons { };
+
+  // Used to delete copy constructor of unordered containers
+  template<>
+    struct __allow_copy_cons<false>
+    {
+      __allow_copy_cons() = default;
+      __allow_copy_cons(const __allow_copy_cons&) = delete;
+      __allow_copy_cons(__allow_copy_cons&&) = default;
+      __allow_copy_cons& operator=(const __allow_copy_cons&) = default;
+      __allow_copy_cons& operator=(__allow_copy_cons&&) = default;
+    };
+
+  template<typename _Alloc>
+    using __check_copy_constructible
+      = __allow_copy_cons<__is_copy_insertable<_Alloc>::value>;
+
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace std
 
diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h
index 95f5657..37e570f 100644
--- a/libstdc++-v3/include/bits/unordered_map.h
+++ b/libstdc++-v3/include/bits/unordered_map.h
@@ -1,6 +1,6 @@ 
 // unordered_map implementation -*- C++ -*-
 
-// Copyright (C) 2010, 2011 Free Software Foundation, Inc.
+// Copyright (C) 2010, 2011, 2013 Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
 // software; you can redistribute it and/or modify it under the
@@ -50,7 +50,8 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 			_Hash, __detail::_Mod_range_hashing,
 			__detail::_Default_ranged_hash,
 			__detail::_Prime_rehash_policy,
-			__cache_hash_code, false, true>
+			__cache_hash_code, false, true>,
+      __check_copy_constructible<_Alloc>
     {
       typedef _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
 			 std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
@@ -123,7 +124,8 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 			_Hash, __detail::_Mod_range_hashing,
 			__detail::_Default_ranged_hash,
 			__detail::_Prime_rehash_policy,
-			__cache_hash_code, false, false>
+			__cache_hash_code, false, false>,
+      __check_copy_constructible<_Alloc>
     {
       typedef _Hashtable<_Key, std::pair<const _Key, _Tp>,
 			 _Alloc,
diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h
index 3d5361d..d65c79c 100644
--- a/libstdc++-v3/include/bits/unordered_set.h
+++ b/libstdc++-v3/include/bits/unordered_set.h
@@ -1,6 +1,6 @@ 
 // unordered_set implementation -*- C++ -*-
 
-// Copyright (C) 2010, 2011 Free Software Foundation, Inc.
+// Copyright (C) 2010, 2011, 2013 Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
 // software; you can redistribute it and/or modify it under the
@@ -50,7 +50,8 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 			_Hash, __detail::_Mod_range_hashing,
 			__detail::_Default_ranged_hash,
 			__detail::_Prime_rehash_policy,
-			__cache_hash_code, true, true>
+			__cache_hash_code, true, true>,
+      __check_copy_constructible<_Alloc>
     {
       typedef _Hashtable<_Value, _Value, _Alloc,
 			 std::_Identity<_Value>, _Pred,
@@ -134,7 +135,8 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 			_Hash, __detail::_Mod_range_hashing,
 			__detail::_Default_ranged_hash,
 			__detail::_Prime_rehash_policy,
-			__cache_hash_code, true, false>
+			__cache_hash_code, true, false>,
+      __check_copy_constructible<_Alloc>
     {
       typedef _Hashtable<_Value, _Value, _Alloc,
 			 std::_Identity<_Value>, _Pred,
diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map
index 1861b86..4c562af 100644
--- a/libstdc++-v3/include/debug/unordered_map
+++ b/libstdc++-v3/include/debug/unordered_map
@@ -1,6 +1,6 @@ 
 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
 
-// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
+// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2013
 // Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
@@ -97,14 +97,12 @@  namespace __debug
 		__gnu_debug::__base(__last), __n,
 		__hf, __eql, __a) { }
 
-      unordered_map(const unordered_map& __x) 
-      : _Base(__x) { }
+      unordered_map(const unordered_map& __x) = default;
 
       unordered_map(const _Base& __x)
       : _Base(__x) { }
 
-      unordered_map(unordered_map&& __x)
-      : _Base(std::move(__x)) { }
+      unordered_map(unordered_map&& __x) = default;
 
       unordered_map(initializer_list<value_type> __l,
 		    size_type __n = 0,
@@ -511,14 +509,12 @@  namespace __debug
 		__gnu_debug::__base(__last), __n,
 		__hf, __eql, __a) { }
 
-      unordered_multimap(const unordered_multimap& __x) 
-      : _Base(__x) { }
+      unordered_multimap(const unordered_multimap& __x) = default;
 
       unordered_multimap(const _Base& __x) 
       : _Base(__x) { }
 
-      unordered_multimap(unordered_multimap&& __x)
-      : _Base(std::move(__x)) { }
+      unordered_multimap(unordered_multimap&& __x) = default;
 
       unordered_multimap(initializer_list<value_type> __l,
 			 size_type __n = 0,
diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set
index 7323184..b91a178 100644
--- a/libstdc++-v3/include/debug/unordered_set
+++ b/libstdc++-v3/include/debug/unordered_set
@@ -1,6 +1,6 @@ 
 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
 
-// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
+// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2013
 // Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
@@ -97,14 +97,12 @@  namespace __debug
 		__gnu_debug::__base(__last), __n,
 		__hf, __eql, __a) { }
 
-      unordered_set(const unordered_set& __x) 
-      : _Base(__x) { }
+      unordered_set(const unordered_set& __x) = default;
 
       unordered_set(const _Base& __x) 
       : _Base(__x) { }
 
-      unordered_set(unordered_set&& __x)
-      : _Base(std::move(__x)) { }
+      unordered_set(unordered_set&& __x) = default;
 
       unordered_set(initializer_list<value_type> __l,
 		    size_type __n = 0,
@@ -506,14 +504,12 @@  namespace __debug
 		__gnu_debug::__base(__last), __n,
 		__hf, __eql, __a) { }
 
-      unordered_multiset(const unordered_multiset& __x) 
-      : _Base(__x) { }
+      unordered_multiset(const unordered_multiset& __x) = default;
 
       unordered_multiset(const _Base& __x) 
       : _Base(__x) { }
 
-      unordered_multiset(unordered_multiset&& __x)
-      : _Base(std::move(__x)) { }
+      unordered_multiset(unordered_multiset&& __x) = default;
 
       unordered_multiset(initializer_list<value_type> __l,
 			 size_type __n = 0,
diff --git a/libstdc++-v3/include/std/unordered_map b/libstdc++-v3/include/std/unordered_map
index e77a297..bfeabec 100644
--- a/libstdc++-v3/include/std/unordered_map
+++ b/libstdc++-v3/include/std/unordered_map
@@ -40,6 +40,7 @@ 
 #include <initializer_list>
 #include <bits/stl_algobase.h>
 #include <bits/allocator.h>
+#include <bits/alloc_traits.h>
 #include <bits/stl_function.h> // equal_to, _Identity, _Select1st
 #include <bits/functional_hash.h>
 #include <bits/hashtable.h>
diff --git a/libstdc++-v3/include/std/unordered_set b/libstdc++-v3/include/std/unordered_set
index 739e0a4..0c75404 100644
--- a/libstdc++-v3/include/std/unordered_set
+++ b/libstdc++-v3/include/std/unordered_set
@@ -40,6 +40,7 @@ 
 #include <initializer_list>
 #include <bits/stl_algobase.h>
 #include <bits/allocator.h>
+#include <bits/alloc_traits.h>
 #include <bits/stl_function.h> // equal_to, _Identity, _Select1st
 #include <bits/functional_hash.h>
 #include <bits/hashtable.h>
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/55043.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/55043.cc
new file mode 100644
index 0000000..50e5437
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/55043.cc
@@ -0,0 +1,69 @@ 
+// { dg-options "-std=gnu++0x" }
+// { dg-do compile }
+
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/55043
+
+#include <unordered_map>
+#include <vector>
+
+struct MoveOnly
+{
+  MoveOnly() = default;
+  MoveOnly(MoveOnly&&) = default;
+};
+
+using hash = std::hash<int>;
+using equal = std::equal_to<int>;
+
+template<typename Alloc>
+  using test_type = std::unordered_map<int, MoveOnly, hash, equal, Alloc>;
+
+void test01()
+{
+  typedef test_type<std::allocator<MoveOnly>> uim;
+  std::vector<uim> v;
+  v.emplace_back(uim());
+}
+
+// Unordered containers don't use allocator_traits yet so need full
+// Allocator interface, derive from std::allocator to get it.
+template<typename T, bool R>
+struct Alloc : std::allocator<T>
+{
+  template<typename U>
+    struct rebind { typedef Alloc<U, R> other; };
+
+  Alloc() = default;
+
+  template<typename U>
+    Alloc(const Alloc<U, R>&) { }
+
+  typedef typename std::conditional<R, T&&, const T&>::type arg_type;
+
+  void construct(T* p, arg_type) const
+  { new((void*)p) T(); }
+};
+
+// verify is_copy_constructible depends on allocator
+typedef test_type<Alloc<MoveOnly, true>> uim_rval;
+static_assert(!std::is_copy_constructible<uim_rval>::value, "is not copyable");
+
+typedef test_type<Alloc<MoveOnly, false>> uim_lval;
+static_assert(std::is_copy_constructible<uim_lval>::value, "is copyable");
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/requirements/53339.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/requirements/53339.cc
new file mode 100644
index 0000000..10404ce
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/requirements/53339.cc
@@ -0,0 +1,36 @@ 
+// XFAIL because of PR libstdc++/55043 fix
+// { dg-do compile { xfail *-*-* } }
+// { dg-excess-errors "" }
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2012-2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <unordered_map>
+
+struct LinkedHashMap
+{
+  struct Entry;
+
+  typedef std::unordered_map<int, Entry> Storage;
+  typedef Storage::iterator EntryPtr;
+
+  struct Entry
+  {
+    EntryPtr prev, next;
+  };
+};
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/55043.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/55043.cc
new file mode 100644
index 0000000..afeecaa
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/55043.cc
@@ -0,0 +1,69 @@ 
+// { dg-options "-std=gnu++0x" }
+// { dg-do compile }
+
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/55043
+
+#include <unordered_map>
+#include <vector>
+
+struct MoveOnly
+{
+  MoveOnly() = default;
+  MoveOnly(MoveOnly&&) = default;
+};
+
+using hash = std::hash<int>;
+using equal = std::equal_to<int>;
+
+template<typename Alloc>
+  using test_type = std::unordered_multimap<int, MoveOnly, hash, equal, Alloc>;
+
+void test01()
+{
+  typedef test_type<std::allocator<MoveOnly>> uim;
+  std::vector<uim> v;
+  v.emplace_back(uim());
+}
+
+// Unordered containers don't use allocator_traits yet so need full
+// Allocator interface, derive from std::allocator to get it.
+template<typename T, bool R>
+struct Alloc : std::allocator<T>
+{
+  template<typename U>
+    struct rebind { typedef Alloc<U, R> other; };
+
+  Alloc() = default;
+
+  template<typename U>
+    Alloc(const Alloc<U, R>&) { }
+
+  typedef typename std::conditional<R, T&&, const T&>::type arg_type;
+
+  void construct(T* p, arg_type) const
+  { new((void*)p) T(); }
+};
+
+// verify is_copy_constructible depends on allocator
+typedef test_type<Alloc<MoveOnly, true>> uim_rval;
+static_assert(!std::is_copy_constructible<uim_rval>::value, "is not copyable");
+
+typedef test_type<Alloc<MoveOnly, false>> uim_lval;
+static_assert(std::is_copy_constructible<uim_lval>::value, "is copyable");
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/requirements/53339.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/requirements/53339.cc
new file mode 100644
index 0000000..cccd2a8
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/requirements/53339.cc
@@ -0,0 +1,36 @@ 
+// XFAIL because of PR libstdc++/55043 fix
+// { dg-do compile { xfail *-*-* } }
+// { dg-excess-errors "" }
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2012-2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <unordered_map>
+
+struct LinkedHashMap
+{
+  struct Entry;
+
+  typedef std::unordered_multimap<int, Entry> Storage;
+  typedef Storage::iterator EntryPtr;
+
+  struct Entry
+  {
+    EntryPtr prev, next;
+  };
+};
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/55043.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/55043.cc
new file mode 100644
index 0000000..9d71cff
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/55043.cc
@@ -0,0 +1,73 @@ 
+// { dg-options "-std=gnu++0x" }
+// { dg-do compile }
+
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/55043
+
+#include <unordered_set>
+#include <vector>
+
+struct MoveOnly
+{
+  MoveOnly() = default;
+  MoveOnly(MoveOnly&&) = default;
+};
+
+struct equal {
+  bool operator()(const MoveOnly&, const MoveOnly) const { return true; }
+};
+struct hash {
+  std::size_t operator()(const MoveOnly&) const { return 0; }
+};
+
+template<typename Alloc>
+  using test_type = std::unordered_multiset<MoveOnly, hash, equal, Alloc>;
+
+void test01()
+{
+  typedef test_type<std::allocator<MoveOnly>> uim;
+  std::vector<uim> v;
+  v.emplace_back(uim());
+}
+
+// Unordered containers don't use allocator_traits yet so need full
+// Allocator interface, derive from std::allocator to get it.
+template<typename T, bool R>
+struct Alloc : std::allocator<T>
+{
+  template<typename U>
+    struct rebind { typedef Alloc<U, R> other; };
+
+  Alloc() = default;
+
+  template<typename U>
+    Alloc(const Alloc<U, R>&) { }
+
+  typedef typename std::conditional<R, T&&, const T&>::type arg_type;
+
+  void construct(T* p, arg_type) const
+  { new((void*)p) T(); }
+};
+
+// verify is_copy_constructible depends on allocator
+typedef test_type<Alloc<MoveOnly, true>> uim_rval;
+static_assert(!std::is_copy_constructible<uim_rval>::value, "is not copyable");
+
+typedef test_type<Alloc<MoveOnly, false>> uim_lval;
+static_assert(std::is_copy_constructible<uim_lval>::value, "is copyable");
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/55043.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/55043.cc
new file mode 100644
index 0000000..1524890
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/55043.cc
@@ -0,0 +1,73 @@ 
+// { dg-options "-std=gnu++0x" }
+// { dg-do compile }
+
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/55043
+
+#include <unordered_set>
+#include <vector>
+
+struct MoveOnly
+{
+  MoveOnly() = default;
+  MoveOnly(MoveOnly&&) = default;
+};
+
+struct equal {
+  bool operator()(const MoveOnly&, const MoveOnly) const { return true; }
+};
+struct hash {
+  std::size_t operator()(const MoveOnly&) const { return 0; }
+};
+
+template<typename Alloc>
+  using test_type = std::unordered_set<MoveOnly, hash, equal, Alloc>;
+
+void test01()
+{
+  typedef test_type<std::allocator<MoveOnly>> uim;
+  std::vector<uim> v;
+  v.emplace_back(uim());
+}
+
+// Unordered containers don't use allocator_traits yet so need full
+// Allocator interface, derive from std::allocator to get it.
+template<typename T, bool R>
+struct Alloc : std::allocator<T>
+{
+  template<typename U>
+    struct rebind { typedef Alloc<U, R> other; };
+
+  Alloc() = default;
+
+  template<typename U>
+    Alloc(const Alloc<U, R>&) { }
+
+  typedef typename std::conditional<R, T&&, const T&>::type arg_type;
+
+  void construct(T* p, arg_type) const
+  { new((void*)p) T(); }
+};
+
+// verify is_copy_constructible depends on allocator
+typedef test_type<Alloc<MoveOnly, true>> uim_rval;
+static_assert(!std::is_copy_constructible<uim_rval>::value, "is not copyable");
+
+typedef test_type<Alloc<MoveOnly, false>> uim_lval;
+static_assert(std::is_copy_constructible<uim_lval>::value, "is copyable");
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc
index 3a6984c..19e5d5e 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc
@@ -19,7 +19,7 @@ 
 // with this library; see the file COPYING3.  If not see
 // <http://www.gnu.org/licenses/>.
 
-// { dg-error "static assertion failed" "" { target *-*-* } 185 }
+// { dg-error "static assertion failed" "" { target *-*-* } 187 }
 
 #include <unordered_set>