re PR libstdc++/44436 ([C++0x] Implement emplace* in associative containers)

2012-09-24  François Dumont  <fdumont@gcc.gnu.org>

	PR libstdc++/44436
	* include/bits/stl_tree.h
	(_Rb_tree<>::_M_insert_): Take _Base_ptr rather than
	_Const_Base_ptr.
	(_Rb_tree<>::_M_insert_node): New.
	(_Rb_tree<>::_M_get_insert_unique_pos): New, search code of
	_M_insert_unique method.
	(_Rb_tree<>::_M_insert_unique): Use latter.
	(_Rb_tree<>::_M_emplace_unique): New, likewise.
	(_Rb_tree<>::_M_get_insert_equal_pos): New, search code of
	_M_insert_equal method.
	(_Rb_tree<>::_M_insert_equal): Use latter.
	(_Rb_tree<>::_M_emplace_equal): New, likewise.
	(_Rb_tree<>::_M_get_insert_hint_unique_pos): New, search code of
	_M_insert_unique_ method.
	(_Rb_tree<>::_M_insert_unique_): Use latter.
	(_Rb_tree<>::_M_emplace_hint_unique): New, likewise.
	(_Rb_tree<>::_M_get_insert_hint_equal_pos): New, search code of
	_M_insert_equal_ method.
	(_Rb_tree<>::_M_insert_equal_): Use latter.
	(_Rb_tree<>::_M_emplace_hint_equal): New, likewise.
	(_Rb_tree<>::_M_insert_lower): Remove first _Base_ptr parameter,
	useless as always null.
	* include/bits/stl_map.h: Include <tuple> in C++11.
	(map<>::operator[](const key_type&)): Use
	_Rb_tree<>::_M_emplace_hint_unique in C++11.
	(map<>::operator[](key_type&&)): Likewise.
	(map<>::emplace): New.
	(map<>::emplace_hint): New.
	* include/bits/stl_multimap.h (multimap<>::emplace): New.
	(multimap<>::emplace_hint): New.
	* include/bits/stl_set.h (set<>::emplace): New.
	(set<>::emplace_hint): New.
	* include/bits/stl_multiset.h (multiset<>::emplace): New.
	(multiset<>::emplace_hint): New.
	* include/debug/map.h (std::__debug::map<>::emplace): New.
	(std::__debug::map<>::emplace_hint): New.
	* include/debug/multimap.h (std::__debug::multimap<>::emplace):
	New.
	(std::__debug::multimap<>::emplace_hint): New.
	* include/debug/set.h (std::__debug::set<>::emplace): New.
	(std::__debug::set<>::emplace_hint): New.
	* include/debug/multiset.h (std::__debug::multiset<>::emplace):
	New.
	(std::__debug::multiset<>::emplace_hint): New.
	* include/profile/map.h (std::__profile::map<>::emplace): New.
	(std::__profile::map<>::emplace_hint): New.
	* include/profile/multimap.h (std::__profile::multimap<>::emplace):
	New.
	(std::__profile::multimap<>::emplace_hint): New.
	* include/profile/set.h (std::__profile::set<>::emplace): New.
	(std::__profile::set<>::emplace_hint): New.
	* include/profile/multiset.h (std::__profile::multiset<>::emplace):
	New.
	(std::__profile::multiset<>::emplace_hint): New.
	* testsuite/util/testsuite_container_traits.h: Signal that emplace
	and emplace_hint are available on std::map, std::multimap,
	std::set and std::multiset in C++11.
	* testsuite/23_containers/map/operators/2.cc: New.
	* testsuite/23_containers/map/modifiers/emplace/1.cc: New.
	* testsuite/23_containers/multimap/modifiers/emplace/1.cc: New.
	* testsuite/23_containers/set/modifiers/emplace/1.cc: New.
	* testsuite/23_containers/multiset/modifiers/emplace/1.cc: New.

From-SVN: r191679

20 files changed, 1277 insertions, 116 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 920bd33..98d3551 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,5 +1,71 @@
 2012-09-24  François Dumont  <fdumont@gcc.gnu.org>
 
+	PR libstdc++/44436
+	* include/bits/stl_tree.h
+	(_Rb_tree<>::_M_insert_): Take _Base_ptr rather than
+	_Const_Base_ptr.
+	(_Rb_tree<>::_M_insert_node): New.
+	(_Rb_tree<>::_M_get_insert_unique_pos): New, search code of
+	_M_insert_unique method.
+	(_Rb_tree<>::_M_insert_unique): Use latter.
+	(_Rb_tree<>::_M_emplace_unique): New, likewise.
+	(_Rb_tree<>::_M_get_insert_equal_pos): New, search code of
+	_M_insert_equal method.
+	(_Rb_tree<>::_M_insert_equal): Use latter.
+	(_Rb_tree<>::_M_emplace_equal): New, likewise.
+	(_Rb_tree<>::_M_get_insert_hint_unique_pos): New, search code of
+	_M_insert_unique_ method.
+	(_Rb_tree<>::_M_insert_unique_): Use latter.
+	(_Rb_tree<>::_M_emplace_hint_unique): New, likewise.
+	(_Rb_tree<>::_M_get_insert_hint_equal_pos): New, search code of
+	_M_insert_equal_ method.
+	(_Rb_tree<>::_M_insert_equal_): Use latter.
+	(_Rb_tree<>::_M_emplace_hint_equal): New, likewise.
+	(_Rb_tree<>::_M_insert_lower): Remove first _Base_ptr parameter,
+	useless as always null.
+	* include/bits/stl_map.h: Include <tuple> in C++11.
+	(map<>::operator[](const key_type&)): Use
+	_Rb_tree<>::_M_emplace_hint_unique in C++11.
+	(map<>::operator[](key_type&&)): Likewise.
+	(map<>::emplace): New.
+	(map<>::emplace_hint): New.
+	* include/bits/stl_multimap.h (multimap<>::emplace): New.
+	(multimap<>::emplace_hint): New.
+	* include/bits/stl_set.h (set<>::emplace): New.
+	(set<>::emplace_hint): New.
+	* include/bits/stl_multiset.h (multiset<>::emplace): New.
+	(multiset<>::emplace_hint): New.
+	* include/debug/map.h (std::__debug::map<>::emplace): New.
+	(std::__debug::map<>::emplace_hint): New.
+	* include/debug/multimap.h (std::__debug::multimap<>::emplace):
+	New.
+	(std::__debug::multimap<>::emplace_hint): New.
+	* include/debug/set.h (std::__debug::set<>::emplace): New.
+	(std::__debug::set<>::emplace_hint): New.
+	* include/debug/multiset.h (std::__debug::multiset<>::emplace):
+	New.
+	(std::__debug::multiset<>::emplace_hint): New.
+	* include/profile/map.h (std::__profile::map<>::emplace): New.
+	(std::__profile::map<>::emplace_hint): New.
+	* include/profile/multimap.h (std::__profile::multimap<>::emplace):
+	New.
+	(std::__profile::multimap<>::emplace_hint): New.
+	* include/profile/set.h (std::__profile::set<>::emplace): New.
+	(std::__profile::set<>::emplace_hint): New.
+	* include/profile/multiset.h (std::__profile::multiset<>::emplace):
+	New.
+	(std::__profile::multiset<>::emplace_hint): New.
+	* testsuite/util/testsuite_container_traits.h: Signal that emplace
+	and emplace_hint are available on std::map, std::multimap,
+	std::set and std::multiset in C++11.
+	* testsuite/23_containers/map/operators/2.cc: New.
+	* testsuite/23_containers/map/modifiers/emplace/1.cc: New.
+	* testsuite/23_containers/multimap/modifiers/emplace/1.cc: New.
+	* testsuite/23_containers/set/modifiers/emplace/1.cc: New.
+	* testsuite/23_containers/multiset/modifiers/emplace/1.cc: New.
+
+2012-09-24  François Dumont  <fdumont@gcc.gnu.org>
+
 	* testsuite/performance/23_containers/insert_erase/41975.cc: Use
 	__uset_hashtable rather than removed __unordered_set.
 
diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h
index cfd478a..14f4457 100644
--- a/libstdc++-v3/include/bits/stl_map.h
+++ b/libstdc++-v3/include/bits/stl_map.h
@@ -61,6 +61,7 @@
 #include <bits/concept_check.h>
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 #include <initializer_list>
+#include <tuple>
 #endif
 
 namespace std _GLIBCXX_VISIBILITY(default)
@@ -461,7 +462,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	iterator __i = lower_bound(__k);
 	// __i->first is greater than or equivalent to __k.
 	if (__i == end() || key_comp()(__k, (*__i).first))
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+	  __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
+					    std::tuple<const key_type&>(__k),
+					    std::tuple<>());
+#else
           __i = insert(__i, value_type(__k, mapped_type()));
+#endif
 	return (*__i).second;
       }
 
@@ -475,7 +482,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	iterator __i = lower_bound(__k);
 	// __i->first is greater than or equivalent to __k.
 	if (__i == end() || key_comp()(__k, (*__i).first))
-          __i = insert(__i, std::make_pair(std::move(__k), mapped_type()));
+	  __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
+					std::forward_as_tuple(std::move(__k)),
+					std::tuple<>());
 	return (*__i).second;
       }
 #endif
@@ -508,6 +517,64 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       }
 
       // modifiers
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+      /**
+       *  @brief Attempts to build and insert a std::pair into the %map.
+       *
+       *  @param __args  Arguments used to generate a new pair instance (see
+       *	        std::piecewise_contruct for passing arguments to each
+       *	        part of the pair constructor).
+       *
+       *  @return  A pair, of which the first element is an iterator that points
+       *           to the possibly inserted pair, and the second is a bool that
+       *           is true if the pair was actually inserted.
+       *
+       *  This function attempts to build and insert a (key, value) %pair into
+       *  the %map.
+       *  A %map relies on unique keys and thus a %pair is only inserted if its
+       *  first element (the key) is not already present in the %map.
+       *
+       *  Insertion requires logarithmic time.
+       */
+      template<typename... _Args>
+	std::pair<iterator, bool>
+	emplace(_Args&&... __args)
+	{ return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); }
+
+      /**
+       *  @brief Attempts to build and insert a std::pair into the %map.
+       *
+       *  @param  __pos  An iterator that serves as a hint as to where the pair
+       *                should be inserted.
+       *  @param  __args  Arguments used to generate a new pair instance (see
+       *	         std::piecewise_contruct for passing arguments to each
+       *	         part of the pair constructor).
+       *  @return An iterator that points to the element with key of the
+       *          std::pair built from @a __args (may or may not be that
+       *          std::pair).
+       *
+       *  This function is not concerned about whether the insertion took place,
+       *  and thus does not return a boolean like the single-argument emplace()
+       *  does.
+       *  Note that the first parameter is only a hint and can potentially
+       *  improve the performance of the insertion process. A bad hint would
+       *  cause no gains in efficiency.
+       *
+       *  See
+       *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
+       *  for more on @a hinting.
+       *
+       *  Insertion requires logarithmic time (if the hint is not taken).
+       */
+      template<typename... _Args>
+	iterator
+	emplace_hint(const_iterator __pos, _Args&&... __args)
+	{
+	  return _M_t._M_emplace_hint_unique(__pos,
+					     std::forward<_Args>(__args)...);
+	}
+#endif
+
       /**
        *  @brief Attempts to insert a std::pair into the %map.
 
diff --git a/libstdc++-v3/include/bits/stl_multimap.h b/libstdc++-v3/include/bits/stl_multimap.h
index 6fc4787..a0fb27e2 100644
--- a/libstdc++-v3/include/bits/stl_multimap.h
+++ b/libstdc++-v3/include/bits/stl_multimap.h
@@ -108,7 +108,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
       __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
 				_BinaryFunctionConcept)
-      __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)	
+      __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)
 
     public:
       class value_compare
@@ -433,6 +433,59 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       { return _M_t.max_size(); }
 
       // modifiers
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+      /**
+       *  @brief Build and insert a std::pair into the %multimap.
+       *
+       *  @param __args  Arguments used to generate a new pair instance (see
+       *	        std::piecewise_contruct for passing arguments to each
+       *	        part of the pair constructor).
+       *
+       *  @return An iterator that points to the inserted (key,value) pair.
+       *
+       *  This function builds and inserts a (key, value) %pair into the
+       *  %multimap.
+       *  Contrary to a std::map the %multimap does not rely on unique keys and
+       *  thus multiple pairs with the same key can be inserted.
+       *
+       *  Insertion requires logarithmic time.
+       */
+      template<typename... _Args>
+	iterator
+	emplace(_Args&&... __args)
+	{ return _M_t._M_emplace_equal(std::forward<_Args>(__args)...); }
+
+      /**
+       *  @brief Builds and inserts a std::pair into the %multimap.
+       *
+       *  @param  __pos  An iterator that serves as a hint as to where the pair
+       *                should be inserted.
+       *  @param  __args  Arguments used to generate a new pair instance (see
+       *	         std::piecewise_contruct for passing arguments to each
+       *	         part of the pair constructor).
+       *  @return An iterator that points to the inserted (key,value) pair.
+       *
+       *  This function inserts a (key, value) pair into the %multimap.
+       *  Contrary to a std::map the %multimap does not rely on unique keys and
+       *  thus multiple pairs with the same key can be inserted.
+       *  Note that the first parameter is only a hint and can potentially
+       *  improve the performance of the insertion process.  A bad hint would
+       *  cause no gains in efficiency.
+       *
+       *  For more on @a hinting, see:
+       *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
+       *
+       *  Insertion requires logarithmic time (if the hint is not taken).
+       */
+      template<typename... _Args>
+	iterator
+	emplace_hint(const_iterator __pos, _Args&&... __args)
+	{
+	  return _M_t._M_emplace_hint_equal(__pos,
+					    std::forward<_Args>(__args)...);
+	}
+#endif
+
       /**
        *  @brief Inserts a std::pair into the %multimap.
        *  @param  __x  Pair to be inserted (see std::make_pair for easy creation
diff --git a/libstdc++-v3/include/bits/stl_multiset.h b/libstdc++-v3/include/bits/stl_multiset.h
index ecf9e54..2448742 100644
--- a/libstdc++-v3/include/bits/stl_multiset.h
+++ b/libstdc++-v3/include/bits/stl_multiset.h
@@ -1,7 +1,7 @@
 // Multiset implementation -*- C++ -*-
 
 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
-// 2011 Free Software Foundation, Inc.
+// 2011, 2012 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
@@ -392,6 +392,54 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       { _M_t.swap(__x._M_t); }
 
       // insert/erase
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+      /**
+       *  @brief Builds and inserts an element into the %multiset.
+       *  @param  __args  Arguments used to generate the element instance to be
+       *                 inserted.
+       *  @return An iterator that points to the inserted element.
+       *
+       *  This function inserts an element into the %multiset.  Contrary
+       *  to a std::set the %multiset does not rely on unique keys and thus
+       *  multiple copies of the same element can be inserted.
+       *
+       *  Insertion requires logarithmic time.
+       */
+      template<typename... _Args>
+	iterator
+	emplace(_Args&&... __args)
+	{ return _M_t._M_emplace_equal(std::forward<_Args>(__args)...); }
+
+      /**
+       *  @brief Builds and inserts an element into the %multiset.
+       *  @param  __pos  An iterator that serves as a hint as to where the
+       *                element should be inserted.
+       *  @param  __args  Arguments used to generate the element instance to be
+       *                 inserted.
+       *  @return An iterator that points to the inserted element.
+       *
+       *  This function inserts an element into the %multiset.  Contrary
+       *  to a std::set the %multiset does not rely on unique keys and thus
+       *  multiple copies of the same element can be inserted.
+       *
+       *  Note that the first parameter is only a hint and can potentially
+       *  improve the performance of the insertion process.  A bad hint would
+       *  cause no gains in efficiency.
+       *
+       *  See http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
+       *  for more on @a hinting.
+       *
+       *  Insertion requires logarithmic time (if the hint is not taken).
+       */
+      template<typename... _Args>
+	iterator
+	emplace_hint(const_iterator __pos, _Args&&... __args)
+	{
+	  return _M_t._M_emplace_hint_equal(__pos,
+					    std::forward<_Args>(__args)...);
+	}
+#endif
+
       /**
        *  @brief Inserts an element into the %multiset.
        *  @param  __x  Element to be inserted.
diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h
index 312e57a..c3c1870 100644
--- a/libstdc++-v3/include/bits/stl_set.h
+++ b/libstdc++-v3/include/bits/stl_set.h
@@ -1,7 +1,7 @@
 // Set implementation -*- C++ -*-
 
 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
-// 2011 Free Software Foundation, Inc.
+// 2011, 2012 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
@@ -395,6 +395,55 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       { _M_t.swap(__x._M_t); }
 
       // insert/erase
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+      /**
+       *  @brief Attempts to build and insert an element into the %set.
+       *  @param __args  Arguments used to generate an element.
+       *  @return  A pair, of which the first element is an iterator that points
+       *           to the possibly inserted element, and the second is a bool
+       *           that is true if the element was actually inserted.
+       *
+       *  This function attempts to build and insert an element into the %set.
+       *  A %set relies on unique keys and thus an element is only inserted if
+       *  it is not already present in the %set.
+       *
+       *  Insertion requires logarithmic time.
+       */
+      template<typename... _Args>
+	std::pair<iterator, bool>
+	emplace(_Args&&... __args)
+	{ return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); }
+
+      /**
+       *  @brief Attempts to insert an element into the %set.
+       *  @param  __pos  An iterator that serves as a hint as to where the
+       *                element should be inserted.
+       *  @param  __args  Arguments used to generate the element to be
+       *                 inserted.
+       *  @return An iterator that points to the element with key equivalent to
+       *          the one generated from @a __args (may or may not be the
+       *          element itself).
+       *
+       *  This function is not concerned about whether the insertion took place,
+       *  and thus does not return a boolean like the single-argument emplace()
+       *  does.  Note that the first parameter is only a hint and can
+       *  potentially improve the performance of the insertion process.  A bad
+       *  hint would cause no gains in efficiency.
+       *
+       *  For more on @a hinting, see:
+       *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
+       *
+       *  Insertion requires logarithmic time (if the hint is not taken).
+       */
+      template<typename... _Args>
+	iterator
+	emplace_hint(const_iterator __pos, _Args&&... __args)
+	{
+	  return _M_t._M_emplace_hint_unique(__pos,
+					     std::forward<_Args>(__args)...);
+	}
+#endif
+
       /**
        *  @brief Attempts to insert an element into the %set.
        *  @param  __x  Element to be inserted.
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index ee56bbc..f2adb96 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -570,27 +570,50 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 
     private:
+      pair<_Base_ptr, _Base_ptr>
+      _M_get_insert_unique_pos(const key_type& __k);
+
+      pair<_Base_ptr, _Base_ptr>
+      _M_get_insert_equal_pos(const key_type& __k);
+
+      pair<_Base_ptr, _Base_ptr>
+      _M_get_insert_hint_unique_pos(const_iterator __pos,
+				    const key_type& __k);
+
+      pair<_Base_ptr, _Base_ptr>
+      _M_get_insert_hint_equal_pos(const_iterator __pos,
+				   const key_type& __k);
+
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
       template<typename _Arg>
         iterator
-        _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y, _Arg&& __v);
+        _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v);
+
+      iterator
+      _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
 
       template<typename _Arg>
         iterator
-        _M_insert_lower(_Base_ptr __x, _Base_ptr __y, _Arg&& __v);
+        _M_insert_lower(_Base_ptr __y, _Arg&& __v);
 
       template<typename _Arg>
         iterator
         _M_insert_equal_lower(_Arg&& __x);
+
+      iterator
+      _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
+
+      iterator
+      _M_insert_equal_lower_node(_Link_type __z);
 #else
       iterator
-      _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y,
+      _M_insert_(_Base_ptr __x, _Base_ptr __y,
 		 const value_type& __v);
 
       // _GLIBCXX_RESOLVE_LIB_DEFECTS
       // 233. Insertion hints in associative containers.
       iterator
-      _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
+      _M_insert_lower(_Base_ptr __y, const value_type& __v);
 
       iterator
       _M_insert_equal_lower(const value_type& __x);
@@ -726,6 +749,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       template<typename _Arg>
         iterator
         _M_insert_equal_(const_iterator __position, _Arg&& __x);
+
+      template<typename... _Args>
+	pair<iterator, bool>
+	_M_emplace_unique(_Args&&... __args);
+
+      template<typename... _Args>
+	iterator
+	_M_emplace_equal(_Args&&... __args);
+
+      template<typename... _Args>
+	iterator
+	_M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
+
+      template<typename... _Args>
+	iterator
+	_M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
 #else
       pair<iterator, bool>
       _M_insert_unique(const value_type& __x);
@@ -967,19 +1006,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
-    _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, _Arg&& __v)
+    _M_insert_(_Base_ptr __x, _Base_ptr __p, _Arg&& __v)
 #else
-    _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
+    _M_insert_(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
 #endif
     {
       bool __insert_left = (__x != 0 || __p == _M_end()
-			    || _M_impl._M_key_compare(_KeyOfValue()(__v), 
+			    || _M_impl._M_key_compare(_KeyOfValue()(__v),
 						      _S_key(__p)));
 
       _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
 
-      _Rb_tree_insert_and_rebalance(__insert_left, __z,
-				    const_cast<_Base_ptr>(__p),  
+      _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
 				    this->_M_impl._M_header);
       ++_M_impl._M_node_count;
       return iterator(__z);
@@ -993,18 +1031,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
-    _M_insert_lower(_Base_ptr __x, _Base_ptr __p, _Arg&& __v)
+    _M_insert_lower(_Base_ptr __p, _Arg&& __v)
 #else
-    _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
+    _M_insert_lower(_Base_ptr __p, const _Val& __v)
 #endif
     {
-      bool __insert_left = (__x != 0 || __p == _M_end()
+      bool __insert_left = (__p == _M_end()
 			    || !_M_impl._M_key_compare(_S_key(__p),
 						       _KeyOfValue()(__v)));
 
       _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
 
-      _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,  
+      _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
 				    this->_M_impl._M_header);
       ++_M_impl._M_node_count;
       return iterator(__z);
@@ -1031,7 +1069,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
 	        _S_left(__x) : _S_right(__x);
 	}
-      return _M_insert_lower(__x, __y, _GLIBCXX_FORWARD(_Arg, __v));
+      return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
     }
 
   template<typename _Key, typename _Val, typename _KoV,
@@ -1264,64 +1302,81 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
-    template<typename _Arg>
-#endif
     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
-			   _Compare, _Alloc>::iterator, bool>
+			   _Compare, _Alloc>::_Base_ptr,
+	 typename _Rb_tree<_Key, _Val, _KeyOfValue,
+			   _Compare, _Alloc>::_Base_ptr>
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
-    _M_insert_unique(_Arg&& __v)
-#else
-    _M_insert_unique(const _Val& __v)
-#endif
+    _M_get_insert_unique_pos(const key_type& __k)
     {
+      typedef pair<_Base_ptr, _Base_ptr> _Res;
       _Link_type __x = _M_begin();
       _Link_type __y = _M_end();
       bool __comp = true;
       while (__x != 0)
 	{
 	  __y = __x;
-	  __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
+	  __comp = _M_impl._M_key_compare(__k, _S_key(__x));
 	  __x = __comp ? _S_left(__x) : _S_right(__x);
 	}
       iterator __j = iterator(__y);
       if (__comp)
 	{
 	  if (__j == begin())
-	    return pair<iterator, bool>
-	      (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true);
+	    return _Res(__x, __y);
 	  else
 	    --__j;
 	}
-      if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
-	return pair<iterator, bool>
-	  (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true);
-      return pair<iterator, bool>(__j, false);
+      if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
+	return _Res(__x, __y);
+      return _Res(__j._M_node, 0);
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
-    template<typename _Arg>
-#endif
-    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+    pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
+			   _Compare, _Alloc>::_Base_ptr,
+	 typename _Rb_tree<_Key, _Val, _KeyOfValue,
+			   _Compare, _Alloc>::_Base_ptr>
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
-    _M_insert_equal(_Arg&& __v)
-#else
-    _M_insert_equal(const _Val& __v)
-#endif
+    _M_get_insert_equal_pos(const key_type& __k)
     {
+      typedef pair<_Base_ptr, _Base_ptr> _Res;
       _Link_type __x = _M_begin();
       _Link_type __y = _M_end();
       while (__x != 0)
 	{
 	  __y = __x;
-	  __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
+	  __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
 	        _S_left(__x) : _S_right(__x);
 	}
-      return _M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v));
+      return _Res(__x, __y);
+    }
+
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+           typename _Compare, typename _Alloc>
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+    template<typename _Arg>
+#endif
+    pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
+			   _Compare, _Alloc>::iterator, bool>
+    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+    _M_insert_unique(_Arg&& __v)
+#else
+    _M_insert_unique(const _Val& __v)
+#endif
+    {
+      typedef pair<iterator, bool> _Res;
+      pair<_Base_ptr, _Base_ptr> __res
+	= _M_get_insert_unique_pos(_KeyOfValue()(__v));
+
+      if (__res.second)
+	return _Res(_M_insert_(__res.first, __res.second,
+			       _GLIBCXX_FORWARD(_Arg, __v)),
+		    true);
+
+      return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1332,67 +1387,73 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
-    _M_insert_unique_(const_iterator __position, _Arg&& __v)
+    _M_insert_equal(_Arg&& __v)
 #else
-    _M_insert_unique_(const_iterator __position, const _Val& __v)
+    _M_insert_equal(const _Val& __v)
 #endif
     {
+      pair<_Base_ptr, _Base_ptr> __res
+	= _M_get_insert_equal_pos(_KeyOfValue()(__v));
+      return _M_insert_(__res.first, __res.second, _GLIBCXX_FORWARD(_Arg, __v));
+    }
+
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+           typename _Compare, typename _Alloc>
+    pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
+			   _Compare, _Alloc>::_Base_ptr,
+         typename _Rb_tree<_Key, _Val, _KeyOfValue,
+			   _Compare, _Alloc>::_Base_ptr>
+    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    _M_get_insert_hint_unique_pos(const_iterator __position,
+				  const key_type& __k)
+    {
+      iterator __pos = __position._M_const_cast();
+      typedef pair<_Base_ptr, _Base_ptr> _Res;
+
       // end()
-      if (__position._M_node == _M_end())
+      if (__pos._M_node == _M_end())
 	{
 	  if (size() > 0
-	      && _M_impl._M_key_compare(_S_key(_M_rightmost()), 
-					_KeyOfValue()(__v)))
-	    return _M_insert_(0, _M_rightmost(), _GLIBCXX_FORWARD(_Arg, __v));
+	      && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
+	    return _Res(0, _M_rightmost());
 	  else
-	    return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
+	    return _M_get_insert_unique_pos(__k);
 	}
-      else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
-				      _S_key(__position._M_node)))
+      else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
 	{
 	  // First, try before...
-	  const_iterator __before = __position;
-	  if (__position._M_node == _M_leftmost()) // begin()
-	    return _M_insert_(_M_leftmost(), _M_leftmost(),
-			      _GLIBCXX_FORWARD(_Arg, __v));
-	  else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), 
-					  _KeyOfValue()(__v)))
+	  iterator __before = __pos;
+	  if (__pos._M_node == _M_leftmost()) // begin()
+	    return _Res(_M_leftmost(), _M_leftmost());
+	  else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
 	    {
 	      if (_S_right(__before._M_node) == 0)
-		return _M_insert_(0, __before._M_node,
-				  _GLIBCXX_FORWARD(_Arg, __v));
+		return _Res(0, __before._M_node);
 	      else
-		return _M_insert_(__position._M_node,
-				  __position._M_node,
-				  _GLIBCXX_FORWARD(_Arg, __v));
+		return _Res(__pos._M_node, __pos._M_node);
 	    }
 	  else
-	    return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
+	    return _M_get_insert_unique_pos(__k);
 	}
-      else if (_M_impl._M_key_compare(_S_key(__position._M_node),
-				      _KeyOfValue()(__v)))
+      else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
 	{
 	  // ... then try after.
-	  const_iterator __after = __position;
-	  if (__position._M_node == _M_rightmost())
-	    return _M_insert_(0, _M_rightmost(),
-			      _GLIBCXX_FORWARD(_Arg, __v));
-	  else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
-					  _S_key((++__after)._M_node)))
+	  iterator __after = __pos;
+	  if (__pos._M_node == _M_rightmost())
+	    return _Res(0, _M_rightmost());
+	  else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
 	    {
-	      if (_S_right(__position._M_node) == 0)
-		return _M_insert_(0, __position._M_node,
-				  _GLIBCXX_FORWARD(_Arg, __v));
+	      if (_S_right(__pos._M_node) == 0)
+		return _Res(0, __pos._M_node);
 	      else
-		return _M_insert_(__after._M_node, __after._M_node,
-				  _GLIBCXX_FORWARD(_Arg, __v));
+		return _Res(__after._M_node, __after._M_node);
 	    }
 	  else
-	    return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
+	    return _M_get_insert_unique_pos(__k);
 	}
       else
 	// Equivalent keys.
-	return __position._M_const_cast();
+	return _Res(__pos._M_node, 0);
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1403,66 +1464,248 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
-    _M_insert_equal_(const_iterator __position, _Arg&& __v)
+    _M_insert_unique_(const_iterator __position, _Arg&& __v)
 #else
-    _M_insert_equal_(const_iterator __position, const _Val& __v)
+    _M_insert_unique_(const_iterator __position, const _Val& __v)
 #endif
     {
+      pair<_Base_ptr, _Base_ptr> __res
+	= _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
+
+      if (__res.second)
+	return _M_insert_(__res.first, __res.second,
+			  _GLIBCXX_FORWARD(_Arg, __v));
+      return iterator(static_cast<_Link_type>(__res.first));
+    }
+
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+           typename _Compare, typename _Alloc>
+    pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
+			   _Compare, _Alloc>::_Base_ptr,
+         typename _Rb_tree<_Key, _Val, _KeyOfValue,
+			   _Compare, _Alloc>::_Base_ptr>
+    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
+    {
+      iterator __pos = __position._M_const_cast();
+      typedef pair<_Base_ptr, _Base_ptr> _Res;
+
       // end()
-      if (__position._M_node == _M_end())
+      if (__pos._M_node == _M_end())
 	{
 	  if (size() > 0
-	      && !_M_impl._M_key_compare(_KeyOfValue()(__v),
-					 _S_key(_M_rightmost())))
-	    return _M_insert_(0, _M_rightmost(),
-			      _GLIBCXX_FORWARD(_Arg, __v));
+	      && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
+	    return _Res(0, _M_rightmost());
 	  else
-	    return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v));
+	    return _M_get_insert_equal_pos(__k);
 	}
-      else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
-				       _KeyOfValue()(__v)))
+      else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
 	{
 	  // First, try before...
-	  const_iterator __before = __position;
-	  if (__position._M_node == _M_leftmost()) // begin()
-	    return _M_insert_(_M_leftmost(), _M_leftmost(),
-			      _GLIBCXX_FORWARD(_Arg, __v));
-	  else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
-					   _S_key((--__before)._M_node)))
+	  iterator __before = __pos;
+	  if (__pos._M_node == _M_leftmost()) // begin()
+	    return _Res(_M_leftmost(), _M_leftmost());
+	  else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
 	    {
 	      if (_S_right(__before._M_node) == 0)
-		return _M_insert_(0, __before._M_node,
-				  _GLIBCXX_FORWARD(_Arg, __v));
+		return _Res(0, __before._M_node);
 	      else
-		return _M_insert_(__position._M_node,
-				  __position._M_node,
-				  _GLIBCXX_FORWARD(_Arg, __v));
+		return _Res(__pos._M_node, __pos._M_node);
 	    }
 	  else
-	    return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v));
+	    return _M_get_insert_equal_pos(__k);
 	}
       else
 	{
 	  // ... then try after.  
-	  const_iterator __after = __position;
-	  if (__position._M_node == _M_rightmost())
-	    return _M_insert_(0, _M_rightmost(),
-			      _GLIBCXX_FORWARD(_Arg, __v));
-	  else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
-					   _KeyOfValue()(__v)))
+	  iterator __after = __pos;
+	  if (__pos._M_node == _M_rightmost())
+	    return _Res(0, _M_rightmost());
+	  else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
 	    {
-	      if (_S_right(__position._M_node) == 0)
-		return _M_insert_(0, __position._M_node,
-				  _GLIBCXX_FORWARD(_Arg, __v));
+	      if (_S_right(__pos._M_node) == 0)
+		return _Res(0, __pos._M_node);
 	      else
-		return _M_insert_(__after._M_node, __after._M_node,
-				  _GLIBCXX_FORWARD(_Arg, __v));
+		return _Res(__after._M_node, __after._M_node);
 	    }
 	  else
-	    return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
+	    return _Res(0, 0);
 	}
     }
 
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+           typename _Compare, typename _Alloc>
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+    template<typename _Arg>
+#endif
+    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+    _M_insert_equal_(const_iterator __position, _Arg&& __v)
+#else
+    _M_insert_equal_(const_iterator __position, const _Val& __v)
+#endif
+    {
+      pair<_Base_ptr, _Base_ptr> __res
+	= _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
+
+      if (__res.second)
+	return _M_insert_(__res.first, __res.second,
+			  _GLIBCXX_FORWARD(_Arg, __v));
+
+      return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
+    }
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+           typename _Compare, typename _Alloc>
+    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
+    {
+      bool __insert_left = (__x != 0 || __p == _M_end()
+			    || _M_impl._M_key_compare(_S_key(__z),
+						      _S_key(__p)));
+
+      _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
+				    this->_M_impl._M_header);
+      ++_M_impl._M_node_count;
+      return iterator(__z);
+    }
+
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+           typename _Compare, typename _Alloc>
+    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
+    {
+      bool __insert_left = (__p == _M_end()
+			    || !_M_impl._M_key_compare(_S_key(__p),
+						       _S_key(__z)));
+
+      _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
+				    this->_M_impl._M_header);
+      ++_M_impl._M_node_count;
+      return iterator(__z);
+    }
+
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+           typename _Compare, typename _Alloc>
+    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    _M_insert_equal_lower_node(_Link_type __z)
+    {
+      _Link_type __x = _M_begin();
+      _Link_type __y = _M_end();
+      while (__x != 0)
+	{
+	  __y = __x;
+	  __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
+	        _S_left(__x) : _S_right(__x);
+	}
+      return _M_insert_lower_node(__y, __z);
+    }
+
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+           typename _Compare, typename _Alloc>
+    template<typename... _Args>
+      pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
+			     _Compare, _Alloc>::iterator, bool>
+      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      _M_emplace_unique(_Args&&... __args)
+      {
+	_Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
+
+	__try
+	  {
+	    typedef pair<iterator, bool> _Res;
+	    auto __res = _M_get_insert_unique_pos(_S_key(__z));
+	    if (__res.second)
+	      return _Res(_M_insert_node(__res.first, __res.second, __z), true);
+	
+	    _M_destroy_node(__z);
+	    return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
+	  }
+	__catch(...)
+	  {
+	    _M_destroy_node(__z);
+	    __throw_exception_again;
+	  }
+      }
+
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+           typename _Compare, typename _Alloc>
+    template<typename... _Args>
+      typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      _M_emplace_equal(_Args&&... __args)
+      {
+	_Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
+
+	__try
+	  {
+	    auto __res = _M_get_insert_equal_pos(_S_key(__z));
+	    return _M_insert_node(__res.first, __res.second, __z);
+	  }
+	__catch(...)
+	  {
+	    _M_destroy_node(__z);
+	    __throw_exception_again;
+	  }
+      }
+
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+           typename _Compare, typename _Alloc>
+    template<typename... _Args>
+      typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
+      {
+	_Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
+
+	__try
+	  {
+	    auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
+
+	    if (__res.second)
+	      return _M_insert_node(__res.first, __res.second, __z);
+
+	    _M_destroy_node(__z);
+	    return iterator(static_cast<_Link_type>(__res.first));
+	  }
+	__catch(...)
+	  {
+	    _M_destroy_node(__z);
+	    __throw_exception_again;
+	  }
+      }
+
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+           typename _Compare, typename _Alloc>
+    template<typename... _Args>
+      typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
+      {
+	_Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
+
+	__try
+	  {
+	    auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
+
+	    if (__res.second)
+	      return _M_insert_node(__res.first, __res.second, __z);
+
+	    return _M_insert_equal_lower_node(__z);
+	  }
+	__catch(...)
+	  {
+	    _M_destroy_node(__z);
+	    __throw_exception_again;
+	  }
+      }
+#endif
+
   template<typename _Key, typename _Val, typename _KoV,
            typename _Cmp, typename _Alloc>
     template<class _II>
diff --git a/libstdc++-v3/include/debug/map.h b/libstdc++-v3/include/debug/map.h
index 95871ac..254988c 100644
--- a/libstdc++-v3/include/debug/map.h
+++ b/libstdc++-v3/include/debug/map.h
@@ -203,6 +203,27 @@ namespace __debug
       using _Base::at;
 
       // modifiers:
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+      template<typename... _Args>
+	std::pair<iterator, bool>
+	emplace(_Args&&... __args)
+	{
+	  auto __res = _Base::emplace(std::forward<_Args>(__args)...);
+	  return std::pair<iterator, bool>(iterator(__res.first, this),
+					   __res.second);
+	}
+
+      template<typename... _Args>
+	iterator
+	emplace_hint(const_iterator __pos, _Args&&... __args)
+	{
+	  __glibcxx_check_insert(__pos);
+	  return iterator(_Base::emplace_hint(__pos.base(),
+					      std::forward<_Args>(__args)...),
+			  this);
+	}
+#endif
+
       std::pair<iterator, bool>
       insert(const value_type& __x)
       {
diff --git a/libstdc++-v3/include/debug/multimap.h b/libstdc++-v3/include/debug/multimap.h
index e1e09bc..e46a742 100644
--- a/libstdc++-v3/include/debug/multimap.h
+++ b/libstdc++-v3/include/debug/multimap.h
@@ -195,6 +195,25 @@ namespace __debug
       using _Base::max_size;
 
       // modifiers:
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+      template<typename... _Args>
+	iterator
+	emplace(_Args&&... __args)
+	{
+	  return iterator(_Base::emplace(std::forward<_Args>(__args)...), this);
+	}
+
+      template<typename... _Args>
+	iterator
+	emplace_hint(const_iterator __pos, _Args&&... __args)
+	{
+	  __glibcxx_check_insert(__pos);
+	  return iterator(_Base::emplace_hint(__pos.base(),
+					      std::forward<_Args>(__args)...),
+			  this);
+	}
+#endif
+      
       iterator
       insert(const value_type& __x)
       { return iterator(_Base::insert(__x), this); }
diff --git a/libstdc++-v3/include/debug/multiset.h b/libstdc++-v3/include/debug/multiset.h
index c7f38ea..0459846 100644
--- a/libstdc++-v3/include/debug/multiset.h
+++ b/libstdc++-v3/include/debug/multiset.h
@@ -194,6 +194,25 @@ namespace __debug
       using _Base::max_size;
 
       // modifiers:
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+      template<typename... _Args>
+	iterator
+	emplace(_Args&&... __args)
+	{
+	  return iterator(_Base::emplace(std::forward<_Args>(__args)...), this);
+	}
+
+      template<typename... _Args>
+	iterator
+	emplace_hint(const_iterator __pos, _Args&&... __args)
+	{
+	  __glibcxx_check_insert(__pos);
+	  return iterator(_Base::emplace_hint(__pos.base(),
+					      std::forward<_Args>(__args)...),
+			  this);
+	}
+#endif
+
       iterator
       insert(const value_type& __x)
       { return iterator(_Base::insert(__x), this); }
diff --git a/libstdc++-v3/include/debug/set.h b/libstdc++-v3/include/debug/set.h
index d6dc06f..44cbe94 100644
--- a/libstdc++-v3/include/debug/set.h
+++ b/libstdc++-v3/include/debug/set.h
@@ -194,6 +194,27 @@ namespace __debug
       using _Base::max_size;
 
       // modifiers:
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+      template<typename... _Args>
+	std::pair<iterator, bool>
+	emplace(_Args&&... __args)
+	{
+	  auto __res = _Base::emplace(std::forward<_Args>(__args)...);
+	  return std::pair<iterator, bool>(iterator(__res.first, this),
+					   __res.second);
+	}
+
+      template<typename... _Args>
+	iterator
+	emplace_hint(const_iterator __pos, _Args&&... __args)
+	{
+	  __glibcxx_check_insert(__pos);
+	  return iterator(_Base::emplace_hint(__pos.base(),
+					      std::forward<_Args>(__args)...),
+			  this);
+	}
+#endif
+
       std::pair<iterator, bool>
       insert(const value_type& __x)
       {
diff --git a/libstdc++-v3/include/profile/map.h b/libstdc++-v3/include/profile/map.h
index 42c32aa..cc01d90 100644
--- a/libstdc++-v3/include/profile/map.h
+++ b/libstdc++-v3/include/profile/map.h
@@ -236,6 +236,29 @@ namespace __profile
       }
 
       // modifiers:
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+      template<typename... _Args>
+	std::pair<iterator, bool>
+	emplace(_Args&&... __args)
+	{
+	  __profcxx_map_to_unordered_map_insert(this, size(), 1);
+	  auto __res = _Base::emplace(std::forward<_Args>(__args)...);
+	  return std::pair<iterator, bool>(iterator(__res.first),
+					   __res.second);
+	}
+
+      template<typename... _Args>
+	iterator
+	emplace_hint(const_iterator __pos, _Args&&... __args)
+	{
+	  size_type size_before = size();
+	  auto __res = _Base::emplace_hint(__pos.base(),
+					   std::forward<_Args>(__args)...));
+	  __profcxx_map_to_unordered_map_insert(this, size_before,
+						size() - size_before);
+	}
+#endif
+
       std::pair<iterator, bool>
       insert(const value_type& __x)
       {
@@ -282,7 +305,7 @@ namespace __profile
       {
         size_type size_before = size();
 	iterator __i = iterator(_Base::insert(__position, __x));
-        __profcxx_map_to_unordered_map_insert(this, size_before, 
+        __profcxx_map_to_unordered_map_insert(this, size_before,
 					      size() - size_before);
 	return __i;
       }
diff --git a/libstdc++-v3/include/profile/multimap.h b/libstdc++-v3/include/profile/multimap.h
index 608d6b7..2268161 100644
--- a/libstdc++-v3/include/profile/multimap.h
+++ b/libstdc++-v3/include/profile/multimap.h
@@ -180,6 +180,23 @@ namespace __profile
       using _Base::max_size;
 
       // modifiers:
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+      template<typename... _Args>
+	iterator
+	emplace(_Args&&... __args)
+	{
+	  return iterator(_Base::emplace(std::forward<_Args>(__args)...));
+	}
+
+      template<typename... _Args>
+	iterator
+	emplace_hint(const_iterator __pos, _Args&&... __args)
+	{
+	  return iterator(_Base::emplace_hint(__pos,
+					      std::forward<_Args>(__args)...));
+	}
+#endif
+      
       iterator
       insert(const value_type& __x)
       { return iterator(_Base::insert(__x)); }
diff --git a/libstdc++-v3/include/profile/multiset.h b/libstdc++-v3/include/profile/multiset.h
index a577938..f76b4fa 100644
--- a/libstdc++-v3/include/profile/multiset.h
+++ b/libstdc++-v3/include/profile/multiset.h
@@ -180,6 +180,21 @@ namespace __profile
       using _Base::max_size;
 
       // modifiers:
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+      template<typename... _Args>
+	iterator
+	emplace(_Args&&... __args)
+	{ return iterator(_Base::emplace(std::forward<_Args>(__args)...)); }
+
+      template<typename... _Args>
+	iterator
+	emplace_hint(const_iterator __pos, _Args&&... __args)
+	{
+	  return iterator(_Base::emplace_hint(__pos,
+					      std::forward<_Args>(__args)...));
+	}
+#endif
+
       iterator
       insert(const value_type& __x)
       { return iterator(_Base::insert(__x)); }
diff --git a/libstdc++-v3/include/profile/set.h b/libstdc++-v3/include/profile/set.h
index 47261e9..c0aa180 100644
--- a/libstdc++-v3/include/profile/set.h
+++ b/libstdc++-v3/include/profile/set.h
@@ -180,6 +180,25 @@ namespace __profile
       using _Base::max_size;
 
       // modifiers:
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+      template<typename... _Args>
+	std::pair<iterator, bool>
+	emplace(_Args&&... __args)
+	{
+	  auto __res = _Base::emplace(std::forward<_Args>(__args)...);
+	  return std::pair<iterator, bool>(iterator(__res.first),
+					   __res.second);
+	}
+
+      template<typename... _Args>
+	iterator
+	emplace_hint(const_iterator __pos, _Args&&... __args)
+	{
+	  return iterator(_Base::emplace_hint(__pos,
+					      std::forward<_Args>(__args)...));
+	}
+#endif
+
       std::pair<iterator, bool>
       insert(const value_type& __x)
       {
diff --git a/libstdc++-v3/testsuite/23_containers/map/modifiers/emplace/1.cc b/libstdc++-v3/testsuite/23_containers/map/modifiers/emplace/1.cc
new file mode 100644
index 0000000..bd25604
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/map/modifiers/emplace/1.cc
@@ -0,0 +1,114 @@
+// { dg-options "-std=c++11" }
+
+// Copyright (C) 2012 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 <utility>
+#include <tuple>
+#include <vector>
+#include <map>
+#include <testsuite_hooks.h>
+
+class PathPoint
+{
+public:
+  PathPoint(char t, const std::vector<double>& c)
+    : type(t), coords(c) { }
+  PathPoint(char t, std::vector<double>&& c)
+    : type(t), coords(std::move(c)) { }
+  char getType() const { return type; }
+  const std::vector<double>& getCoords() const { return coords; }
+private:
+  char type;
+  std::vector<double> coords;
+};
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  typedef std::map<char, std::vector<double>> Map;
+  Map m;
+
+  std::vector<double> coord1 = { 0.0, 1.0, 2.0 };
+
+  auto ret = m.emplace('a', coord1);
+  VERIFY( ret.second );
+  VERIFY( m.size() == 1 );
+  VERIFY( ret.first->first == 'a' );
+
+  coord1[0] = 3.0;
+  ret = m.emplace('a', coord1);
+  VERIFY( !ret.second );
+  VERIFY( m.size() == 1 );
+  VERIFY( ret.first->first == 'a' );
+  VERIFY( ret.first->second[0] == 0.0 );
+
+  auto it = m.emplace_hint(m.begin(), 'b', coord1);
+  VERIFY( it != m.end() );
+  VERIFY( it->first == 'b' );
+  VERIFY( it->second[0] == 3.0 );
+
+  double *px = &coord1[0];
+  ret = m.emplace('c', std::move(coord1));
+  VERIFY( ret.second );
+  VERIFY( ret.first->first == 'c' );
+  VERIFY( &(ret.first->second[0]) == px );
+}
+
+void test02()
+{
+  using namespace std;
+  typedef map<char, PathPoint> Map;
+  Map m;
+
+  vector<double> coord1 = { 0.0, 1.0, 2.0 };
+
+  auto ret = m.emplace(piecewise_construct,
+		       make_tuple('a'), make_tuple('a', coord1));
+  VERIFY( ret.second );
+  VERIFY( m.size() == 1 );
+  VERIFY( ret.first->first == 'a' );
+
+  coord1[0] = 3.0;
+  ret = m.emplace(piecewise_construct,
+		  make_tuple('a'), make_tuple( 'b', coord1));
+  VERIFY( !ret.second );
+  VERIFY( m.size() == 1 );
+  VERIFY( ret.first->first == 'a' );
+  VERIFY( ret.first->second.getCoords()[0] == 0.0 );
+
+  auto it = m.emplace_hint(m.begin(), piecewise_construct,
+			   make_tuple('b'), make_tuple('c', coord1));
+  VERIFY( it != m.end() );
+  VERIFY( it->first == 'b' );
+  VERIFY( it->second.getCoords()[0] == 3.0 );
+
+  double *px = &coord1[0];
+  ret = m.emplace(piecewise_construct,
+		  make_tuple('c'), make_tuple('d', move(coord1)));
+  VERIFY( ret.second );
+  VERIFY( ret.first->first == 'c' );
+  VERIFY( &(ret.first->second.getCoords()[0]) == px );
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/map/operators/2.cc b/libstdc++-v3/testsuite/23_containers/map/operators/2.cc
new file mode 100644
index 0000000..0d8a183
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/map/operators/2.cc
@@ -0,0 +1,87 @@
+// Copyright (C) 2012 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/>.
+
+// This test verifies that the value type of a map need not be default copyable.
+
+// { dg-options "-std=c++11" }
+
+#include <map>
+#include <testsuite_hooks.h>
+#include <testsuite_rvalref.h>
+#include <testsuite_counter_type.h>
+
+struct Mapped
+{
+  Mapped() = default;
+  explicit Mapped(const Mapped&) = default;
+};
+
+struct DefaultConstructibleType
+{
+  int val;
+
+  DefaultConstructibleType() : val(123)
+  {}
+
+  DefaultConstructibleType(const DefaultConstructibleType&) = delete;
+  DefaultConstructibleType(DefaultConstructibleType&&) = delete;
+
+  DefaultConstructibleType& operator=(int x)
+  {
+    val = x;
+    return *this;
+  }
+};
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  using __gnu_test::rvalstruct;
+  using __gnu_test::counter_type;
+
+  std::map<int, Mapped> m1;
+  m1[0] = Mapped();
+
+  std::map<int, rvalstruct> m2;
+  m2[0] = rvalstruct(13);
+
+  std::map<int, DefaultConstructibleType> m3;
+  VERIFY( m3[0].val == 123 );
+  VERIFY( m3.size() == 1 );
+  m3[0] = 2;
+  VERIFY( m3[0].val == 2 );
+
+  std::map<counter_type, int> m4;
+  VERIFY( m4[counter_type(1)] == 0 );
+  VERIFY( counter_type::specialize_count == 1 );
+  VERIFY( counter_type::copy_count == 0 );
+  VERIFY( counter_type::move_count == 1 );
+  
+  counter_type k(2);
+  counter_type::reset();
+
+  VERIFY( m4[k] == 0 );
+  VERIFY( counter_type::copy_count == 1 );
+  VERIFY( counter_type::move_count == 0 );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/modifiers/emplace/1.cc b/libstdc++-v3/testsuite/23_containers/multimap/modifiers/emplace/1.cc
new file mode 100644
index 0000000..71ca8a9
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multimap/modifiers/emplace/1.cc
@@ -0,0 +1,108 @@
+// { dg-options "-std=c++11" }
+
+// Copyright (C) 2012 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 <tuple>
+#include <vector>
+#include <map>
+#include <testsuite_hooks.h>
+
+class PathPoint
+{
+public:
+  PathPoint(char t, const std::vector<double>& c)
+  : type(t), coords(c) { }
+  PathPoint(char t, std::vector<double>&& c)
+  : type(t), coords(std::move(c)) { }
+  char getType() const { return type; }
+  const std::vector<double>& getCoords() const { return coords; }
+private:
+  char type;
+  std::vector<double> coords;
+};
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  typedef std::multimap<char, std::vector<double>> MMap;
+  MMap mm;
+
+  std::vector<double> coord1 = { 0.0, 1.0, 2.0 };
+
+  auto it = mm.emplace('a', coord1);
+  VERIFY( mm.size() == 1 );
+  VERIFY( it->first == 'a' );
+
+  coord1[0] = 3.0;
+  it = mm.emplace('a', coord1);
+  VERIFY( mm.size() == 2 );
+  VERIFY( it->first == 'a' );
+  VERIFY( it->second[0] == 3.0 );
+
+  it = mm.emplace_hint(mm.begin(), 'b', coord1);
+  VERIFY( it != mm.end() );
+  VERIFY( it->first == 'b' );
+  VERIFY( it->second[0] == 3.0 );
+
+  double *px = &coord1[0];
+  it = mm.emplace('c', std::move(coord1));
+  VERIFY( it->first == 'c' );
+  VERIFY( &(it->second[0]) == px );
+}
+
+void test02()
+{
+  using namespace std;
+  typedef multimap<char, PathPoint> Map;
+  Map m;
+
+  vector<double> coord1 = { 0.0, 1.0, 2.0 };
+
+  auto it = m.emplace(piecewise_construct,
+		      make_tuple('a'), make_tuple('a', coord1));
+  VERIFY( m.size() == 1 );
+  VERIFY( it->first == 'a' );
+
+  coord1[0] = 3.0;
+  it = m.emplace(piecewise_construct,
+		  make_tuple('a'), make_tuple( 'b', coord1));
+  VERIFY( m.size() == 2 );
+  VERIFY( it->first == 'a' );
+  VERIFY( it->second.getCoords()[0] == 3.0 );
+
+  it = m.emplace_hint(m.begin(), piecewise_construct,
+		      make_tuple('b'), make_tuple('c', coord1));
+  VERIFY( it != m.end() );
+  VERIFY( it->first == 'b' );
+  VERIFY( it->second.getCoords()[0] == 3.0 );
+
+  double *px = &coord1[0];
+  it = m.emplace(piecewise_construct,
+		  make_tuple('c'), make_tuple('d', move(coord1)));
+  VERIFY( it->first == 'c' );
+  VERIFY( &(it->second.getCoords()[0]) == px );
+}
+
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/modifiers/emplace/1.cc b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/emplace/1.cc
new file mode 100644
index 0000000..3a1e38c
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/emplace/1.cc
@@ -0,0 +1,79 @@
+// { dg-options "-std=c++11" }
+
+// Copyright (C) 2012 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 <vector>
+#include <set>
+#include <testsuite_hooks.h>
+
+class PathPoint
+{
+public:
+  PathPoint(char t, const std::vector<double>& c)
+  : type(t), coords(c) { }
+  PathPoint(char t, std::vector<double>&& c)
+  : type(t), coords(std::move(c)) { }
+  char getType() const { return type; }
+  const std::vector<double>& getCoords() const { return coords; }
+private:
+  char type;
+  std::vector<double> coords;
+};
+
+struct PathPointLess
+{
+  bool operator() (const PathPoint& __lhs, const PathPoint& __rhs) const
+  { return __lhs.getType() < __rhs.getType(); }
+};
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  typedef std::multiset<PathPoint, PathPointLess> Mset;
+  Mset ms;
+
+  std::vector<double> coord1 = { 0.0, 1.0, 2.0 };
+
+  auto it = ms.emplace('a', coord1);
+  VERIFY( ms.size() == 1 );
+  VERIFY( it->getType() == 'a' );
+
+  coord1[0] = 3.0;
+  it = ms.emplace('a', coord1);
+  VERIFY( ms.size() == 2 );
+  VERIFY( it->getType() == 'a' );
+  VERIFY( it->getCoords()[0] == 3.0 );
+
+  it = ms.emplace_hint(ms.begin(), 'b', coord1);
+  VERIFY( it != ms.end() );
+  VERIFY( it->getType() == 'b' );
+  VERIFY( it->getCoords()[0] == 3.0 );
+
+  double *px = &coord1[0];
+  it = ms.emplace('c', std::move(coord1));
+  VERIFY( ms.size() == 4 );
+  VERIFY( it->getType() == 'c' );
+  VERIFY( &(it->getCoords()[0]) == px );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/set/modifiers/emplace/1.cc b/libstdc++-v3/testsuite/23_containers/set/modifiers/emplace/1.cc
new file mode 100644
index 0000000..34c4c19
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/set/modifiers/emplace/1.cc
@@ -0,0 +1,81 @@
+// { dg-options "-std=c++11" }
+
+// Copyright (C) 2012 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 <vector>
+#include <set>
+#include <testsuite_hooks.h>
+
+class PathPoint
+{
+public:
+  PathPoint(char t, const std::vector<double>& c)
+  : type(t), coords(c) { }
+  PathPoint(char t, std::vector<double>&& c)
+  : type(t), coords(std::move(c)) { }
+  char getType() const { return type; }
+  const std::vector<double>& getCoords() const { return coords; }
+private:
+  char type;
+  std::vector<double> coords;
+};
+
+struct PathPointLess
+{
+  bool operator() (const PathPoint& __lhs, const PathPoint& __rhs) const
+  { return __lhs.getType() < __rhs.getType(); }
+};
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  typedef std::set<PathPoint, PathPointLess> Set;
+  Set s;
+
+  std::vector<double> coord1 = { 0.0, 1.0, 2.0 };
+
+  auto ret = s.emplace('a', coord1);
+  VERIFY( ret.second );
+  VERIFY( s.size() == 1 );
+  VERIFY( ret.first->getType() == 'a' );
+
+  coord1[0] = 3.0;
+  ret = s.emplace('a', coord1);
+  VERIFY( !ret.second );
+  VERIFY( s.size() == 1 );
+  VERIFY( ret.first->getType() == 'a' );
+  VERIFY( ret.first->getCoords()[0] == 0.0 );
+
+  auto it = s.emplace_hint(s.begin(), 'b', coord1);
+  VERIFY( it != s.end() );
+  VERIFY( it->getType() == 'b' );
+  VERIFY( it->getCoords()[0] == 3.0 );
+
+  double *px = &coord1[0];
+  ret = s.emplace('c', std::move(coord1));
+  VERIFY( ret.second );
+  VERIFY( ret.first->getType() == 'c' );
+  VERIFY( &(ret.first->getCoords()[0]) == px );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/util/testsuite_container_traits.h b/libstdc++-v3/testsuite/util/testsuite_container_traits.h
index cce91b7..5d8aae0 100644
--- a/libstdc++-v3/testsuite/util/testsuite_container_traits.h
+++ b/libstdc++-v3/testsuite/util/testsuite_container_traits.h
@@ -148,6 +148,9 @@ namespace __gnu_test
 
       typedef std::true_type	has_erase;
       typedef std::true_type	has_insert;
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+      typedef std::true_type	has_emplace;
+#endif
     };
 
   template<typename _Tp1, typename _Tp2, typename _Tp3, typename _Tp4>
@@ -161,6 +164,9 @@ namespace __gnu_test
 
       typedef std::true_type	has_erase;
       typedef std::true_type	has_insert;
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+      typedef std::true_type	has_emplace;
+#endif
     };
 
   template<typename _Tp1, typename _Tp2, typename _Tp3>
@@ -173,6 +179,9 @@ namespace __gnu_test
 
       typedef std::true_type	has_erase;
       typedef std::true_type	has_insert;
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+      typedef std::true_type	has_emplace;
+#endif
     };
 
   template<typename _Tp1, typename _Tp2, typename _Tp3>
@@ -185,6 +194,9 @@ namespace __gnu_test
 
       typedef std::true_type	has_erase;
       typedef std::true_type	has_insert;
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+      typedef std::true_type	has_emplace;
+#endif
     };
 
   template<typename _Tp1, typename _Tp2>