hashtable.h (_Hashtable<>::emplace, [...]): Add.

2011-12-09  François Dumont <fdumont@gcc.gnu.org>

	* include/bits/hashtable.h (_Hashtable<>::emplace,
	_Hashtable<>::emplace_hint): Add.
	* include/debug/unordered_set (unordered_set<>::emplace,
	unordered_set<>::emplace_hint, unordered_multiset<>::emplace,
	unordered_multiset<>::emplace_hint): Add.
	* include/profile/unordered_set: Likewise.
	* include/debug/unordered_map (unordered_map<>::emplace,
	unordered_map<>::emplace_hint, unordered_multimap<>::emplace,
	unordered_multimap<>::emplace_hint): Add.
	* include/profile/unordered_map: Likewise.
	* testsuite/23_containers/unordered_map/modifiers/emplace.cc: New.
	* testsuite/23_containers/unordered_multimap/modifiers/emplace.cc:
	New.
	* testsuite/23_containers/unordered_set/modifiers/emplace.cc: New.
	* testsuite/23_containers/unordered_multiset/modifiers/emplace.cc:
	New.
	* testsuite/util/testsuite_container_traits.h
	(traits_base::has_emplace): Add and defined as std::true_type for
	unordered containers.
	* testsuite/util/exception/safety.h (emplace, emplace_hint): Add and
	use them in basic_safety exception test case.
	* doc/xml/manual/status_cxx2011.xml: Update unordered containers
	status.

From-SVN: r182174

11 files changed, 780 insertions, 5 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index bf5224e..5ade2a0 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,29 @@
+2011-12-09  François Dumont <fdumont@gcc.gnu.org>
+
+	* include/bits/hashtable.h (_Hashtable<>::emplace,
+	_Hashtable<>::emplace_hint): Add.
+	* include/debug/unordered_set (unordered_set<>::emplace,
+	unordered_set<>::emplace_hint, unordered_multiset<>::emplace,
+	unordered_multiset<>::emplace_hint): Add.
+	* include/profile/unordered_set: Likewise.
+	* include/debug/unordered_map (unordered_map<>::emplace,
+	unordered_map<>::emplace_hint, unordered_multimap<>::emplace,
+	unordered_multimap<>::emplace_hint): Add.
+	* include/profile/unordered_map: Likewise.
+	* testsuite/23_containers/unordered_map/modifiers/emplace.cc: New.
+	* testsuite/23_containers/unordered_multimap/modifiers/emplace.cc:
+	New.
+	* testsuite/23_containers/unordered_set/modifiers/emplace.cc: New.
+	* testsuite/23_containers/unordered_multiset/modifiers/emplace.cc:
+	New.
+	* testsuite/util/testsuite_container_traits.h
+	(traits_base::has_emplace): Add and defined as std::true_type for
+	unordered containers.
+	* testsuite/util/exception/safety.h (emplace, emplace_hint): Add and
+	use them in basic_safety exception test case.
+	* doc/xml/manual/status_cxx2011.xml: Update unordered containers
+	status.
+
 2011-12-08  Jonathan Wakely  <jwakely.gcc@gmail.com>
 
 	* include/bits/atomic_base.h (__calculate_memory_order): Rename to...
diff --git a/libstdc++-v3/doc/xml/manual/status_cxx2011.xml b/libstdc++-v3/doc/xml/manual/status_cxx2011.xml
index f47710e..1f39ce5 100644
--- a/libstdc++-v3/doc/xml/manual/status_cxx2011.xml
+++ b/libstdc++-v3/doc/xml/manual/status_cxx2011.xml
@@ -1403,11 +1403,10 @@ particular release.
       <entry>Missing emplace members</entry>
     </row>
     <row>
-      <?dbhtml bgcolor="#B0B0B0" ?>
       <entry>23.2.5</entry>
       <entry>Unordered associative containers</entry>
-      <entry>Partial</entry>
-      <entry>Missing emplace members</entry>
+      <entry>Y</entry>
+      <entry/>
     </row>
     <row>
       <entry>23.3</entry>
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 712b1df..3874cbc 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -467,6 +467,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_Insert_Conv_Type;
 
     protected:
+      template<typename... _Args>
+	std::pair<iterator, bool>
+	_M_emplace(std::true_type, _Args&&... __args);
+
+      template<typename... _Args>
+	iterator
+	_M_emplace(std::false_type, _Args&&... __args);
+
       template<typename _Arg>
 	std::pair<iterator, bool>
 	_M_insert(_Arg&&, std::true_type);
@@ -476,7 +484,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_insert(_Arg&&, std::false_type);
 
     public:
-      // Insert and erase
+      // Emplace, insert and erase
+      template<typename... _Args>
+	_Insert_Return_Type
+	emplace(_Args&&... __args)
+	{ return _M_emplace(integral_constant<bool, __unique_keys>(),
+			    std::forward<_Args>(__args)...); }
+
+      template<typename... _Args>
+	iterator
+	emplace_hint(const_iterator, _Args&&... __args)
+	{ return _Insert_Conv_Type()(emplace(std::forward<_Args>(__args)...)); }
+
       _Insert_Return_Type
       insert(const value_type& __v)
       { return _M_insert(__v, integral_constant<bool, __unique_keys>()); }
@@ -1160,6 +1179,128 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return __prev_n;
     }
 
+  template<typename _Key, typename _Value,
+	   typename _Allocator, typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+	   bool __chc, bool __cit, bool __uk>
+    template<typename... _Args>
+      std::pair<typename _Hashtable<_Key, _Value, _Allocator,
+				    _ExtractKey, _Equal, _H1,
+				    _H2, _Hash, _RehashPolicy,
+				    __chc, __cit, __uk>::iterator, bool>
+      _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
+		 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
+      _M_emplace(std::true_type, _Args&&... __args)
+      {
+	// First build the node to get access to the hash code
+	_Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
+	__try
+	  {
+	    const key_type& __k = this->_M_extract(__new_node->_M_v);
+	    typename _Hashtable::_Hash_code_type __code
+	      = this->_M_hash_code(__k);
+	    size_type __bkt
+	      = this->_M_bucket_index(__k, __code, _M_bucket_count);
+
+	    if (_Node* __p = _M_find_node(__bkt, __k, __code))
+	      {
+		// There is already an equivalent node, no insertion
+		_M_deallocate_node(__new_node);
+		return std::make_pair(iterator(__p), false);
+	      }
+
+	    // We are going to insert this node
+	    this->_M_store_code(__new_node, __code);
+	    const _RehashPolicyState& __saved_state
+	      = _M_rehash_policy._M_state();
+	    std::pair<bool, std::size_t> __do_rehash
+	      = _M_rehash_policy._M_need_rehash(_M_bucket_count,
+						_M_element_count, 1);
+
+	    if (__do_rehash.first)
+	      {
+		_M_rehash(__do_rehash.second, __saved_state);
+		__bkt = this->_M_bucket_index(__k, __code, _M_bucket_count);
+	      }
+
+	    if (_M_buckets[__bkt])
+	      _M_insert_after(__bkt, _M_buckets[__bkt], __new_node);
+	    else 
+	      _M_insert_bucket_begin(__bkt, __new_node);
+	    ++_M_element_count;
+	    return std::make_pair(iterator(__new_node), true);
+	  }
+	__catch(...)
+	  {
+	    _M_deallocate_node(__new_node);
+	    __throw_exception_again;
+	  }
+      }
+
+  template<typename _Key, typename _Value,
+	   typename _Allocator, typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+	   bool __chc, bool __cit, bool __uk>
+    template<typename... _Args>
+      typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
+			  _H1, _H2, _Hash, _RehashPolicy,
+			  __chc, __cit, __uk>::iterator
+      _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
+		 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
+      _M_emplace(std::false_type, _Args&&... __args)
+      {
+	const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
+	std::pair<bool, std::size_t> __do_rehash
+	  = _M_rehash_policy._M_need_rehash(_M_bucket_count,
+					    _M_element_count, 1);
+
+	// First build the node to get its hash code
+	_Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
+	__try
+	  {
+	    const key_type& __k = this->_M_extract(__new_node->_M_v);
+	    typename _Hashtable::_Hash_code_type __code
+	      = this->_M_hash_code(__k);
+	    this->_M_store_code(__new_node, __code);
+	    size_type __bkt
+	      = this->_M_bucket_index(__k, __code, _M_bucket_count);
+
+	    // Second find the node, avoid rehash if compare throws.
+	    _Node* __prev = _M_find_node(__bkt, __k, __code);
+	    
+	    if (__do_rehash.first)
+	      {
+		_M_rehash(__do_rehash.second, __saved_state);
+		__bkt = this->_M_bucket_index(__k, __code, _M_bucket_count);
+		// __prev is still valid because rehash do not invalidate nodes
+	      }
+
+	    if (__prev)
+	      // Insert after the previous equivalent node
+	      _M_insert_after(__bkt, __prev, __new_node);
+	    else if (_M_buckets[__bkt])
+	      // Bucket is not empty and the inserted node has no equivalent in
+	      // the hashtable. We must insert the new node at the beginning or
+	      // end of the bucket to preserve equivalent elements relative
+	      // positions.
+	      if (__bkt != _M_begin_bucket_index)
+		// We insert the new node at the beginning
+		_M_insert_after(__bkt, _M_buckets[__bkt], __new_node);
+	      else
+		// We insert the new node at the end
+		_M_insert_after(__bkt, _M_bucket_end(__bkt), __new_node);
+	    else
+	      _M_insert_bucket_begin(__bkt, __new_node);
+	    ++_M_element_count;
+	    return iterator(__new_node);
+	  }
+	__catch(...)
+	  {
+	    _M_deallocate_node(__new_node);
+	    __throw_exception_again;
+	  }
+      }
+
   // Insert v in bucket n (assumes no element with its key already present).
   template<typename _Key, typename _Value,
 	   typename _Allocator, typename _ExtractKey, typename _Equal,
@@ -1300,7 +1441,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      _M_deallocate_node(__new_node);
 	    __throw_exception_again;
 	  }
-
       }
 
   template<typename _Key, typename _Value,
diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map
index 6ad46b6..cf84948 100644
--- a/libstdc++-v3/include/debug/unordered_map
+++ b/libstdc++-v3/include/debug/unordered_map
@@ -204,6 +204,29 @@ namespace __debug
       cend(size_type __b) const
       { return const_local_iterator(_Base::cend(__b), __b, this); }
 
+      template<typename... _Args>
+	std::pair<iterator, bool>
+	emplace(_Args&&... __args)
+	{
+	  size_type __bucket_count = this->bucket_count();
+	  std::pair<_Base_iterator, bool> __res
+	    = _Base::emplace(std::forward<_Args>(__args)...);
+	  _M_check_rehashed(__bucket_count);
+	  return std::make_pair(iterator(__res.first, this), __res.second);
+	}
+
+      template<typename... _Args>
+	iterator
+	emplace_hint(const_iterator __hint, _Args&&... __args)
+	{
+	  __glibcxx_check_insert(__hint);
+	  size_type __bucket_count = this->bucket_count();
+	  _Base_iterator __it = _Base::emplace_hint(__hint.base(),
+					std::forward<_Args>(__args)...);
+	  _M_check_rehashed(__bucket_count);
+	  return iterator(__it, this);
+	}
+
       std::pair<iterator, bool>
       insert(const value_type& __obj)
       {
@@ -587,6 +610,29 @@ namespace __debug
       cend(size_type __b) const
       { return const_local_iterator(_Base::cend(__b), __b, this); }
 
+      template<typename... _Args>
+	iterator
+	emplace(_Args&&... __args)
+	{
+	  size_type __bucket_count = this->bucket_count();
+	  _Base_iterator __it
+	    = _Base::emplace(std::forward<_Args>(__args)...);
+	  _M_check_rehashed(__bucket_count);
+	  return iterator(__it, this);
+	}
+
+      template<typename... _Args>
+	iterator
+	emplace_hint(const_iterator __hint, _Args&&... __args)
+	{
+	  __glibcxx_check_insert(__hint);
+	  size_type __bucket_count = this->bucket_count();
+	  _Base_iterator __it = _Base::emplace_hint(__hint.base(),
+					std::forward<_Args>(__args)...);
+	  _M_check_rehashed(__bucket_count);
+	  return iterator(__it, this);
+	}
+
       iterator
       insert(const value_type& __obj)
       {
diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set
index 2f41bc3..ba44040 100644
--- a/libstdc++-v3/include/debug/unordered_set
+++ b/libstdc++-v3/include/debug/unordered_set
@@ -204,6 +204,29 @@ namespace __debug
       cend(size_type __b) const
       { return const_local_iterator(_Base::cend(__b), __b, this); }
 
+      template<typename... _Args>
+	std::pair<iterator, bool>
+	emplace(_Args&&... __args)
+	{
+	  size_type __bucket_count = this->bucket_count();
+	  std::pair<_Base_iterator, bool> __res
+	    = _Base::emplace(std::forward<_Args>(__args)...);
+	  _M_check_rehashed(__bucket_count);
+	  return std::make_pair(iterator(__res.first, this), __res.second);
+	}
+
+      template<typename... _Args>
+	iterator
+	emplace_hint(const_iterator __hint, _Args&&... __args)
+	{
+	  __glibcxx_check_insert(__hint);
+	  size_type __bucket_count = this->bucket_count();
+	  _Base_iterator __it = _Base::emplace_hint(__hint.base(),
+					std::forward<_Args>(__args)...);
+	  _M_check_rehashed(__bucket_count);
+	  return iterator(__it, this);
+	}
+
       std::pair<iterator, bool>
       insert(const value_type& __obj)
       {
@@ -582,6 +605,29 @@ namespace __debug
       cend(size_type __b) const
       { return const_local_iterator(_Base::cend(__b), __b, this); }
 
+      template<typename... _Args>
+	iterator
+	emplace(_Args&&... __args)
+	{
+	  size_type __bucket_count = this->bucket_count();
+	  _Base_iterator __it
+	    = _Base::emplace(std::forward<_Args>(__args)...);
+	  _M_check_rehashed(__bucket_count);
+	  return iterator(__it, this);
+	}
+
+      template<typename... _Args>
+	iterator
+	emplace_hint(const_iterator __hint, _Args&&... __args)
+	{
+	  __glibcxx_check_insert(__hint);
+	  size_type __bucket_count = this->bucket_count();
+	  _Base_iterator __it = _Base::emplace_hint(__hint.base(),
+					std::forward<_Args>(__args)...);
+	  _M_check_rehashed(__bucket_count);
+	  return iterator(__it, this);
+	}
+
       iterator
       insert(const value_type& __obj)
       {
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/emplace.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/emplace.cc
new file mode 100644
index 0000000..0a0dff8
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/emplace.cc
@@ -0,0 +1,116 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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/>.
+
+// range insert
+
+#include <utility>
+#include <tuple>
+#include <vector>
+#include <unordered_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::unordered_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 unordered_map<char, PathPoint> Map;
+  Map m;
+
+  std::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/unordered_multimap/modifiers/emplace.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/emplace.cc
new file mode 100644
index 0000000..40aef98
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/emplace.cc
@@ -0,0 +1,110 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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/>.
+
+// range insert
+
+#include <tuple>
+#include <vector>
+#include <unordered_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::unordered_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 unordered_multimap<char, PathPoint> Map;
+  Map m;
+
+  std::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/unordered_multiset/modifiers/emplace.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/emplace.cc
new file mode 100644
index 0000000..057e326
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/emplace.cc
@@ -0,0 +1,88 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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/>.
+
+// range insert
+
+#include <vector>
+#include <unordered_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 PathPointHasher
+{
+  std::size_t operator() (const PathPoint& __pp) const
+  { return __pp.getType(); }
+};
+
+struct PathPointEqual
+{
+  bool operator() (const PathPoint& __lhs, const PathPoint& __rhs) const
+  { return __lhs.getType() == __rhs.getType(); }
+};
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  typedef std::unordered_multiset<PathPoint, PathPointHasher,
+				  PathPointEqual> 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/unordered_set/modifiers/emplace.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/emplace.cc
new file mode 100644
index 0000000..2ae4e76
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/emplace.cc
@@ -0,0 +1,89 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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/>.
+
+// range insert
+
+#include <vector>
+#include <unordered_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 PathPointHasher
+{
+  std::size_t operator() (const PathPoint& __pp) const
+  { return __pp.getType(); }
+};
+
+struct PathPointEqual
+{
+  bool operator() (const PathPoint& __lhs, const PathPoint& __rhs) const
+  { return __lhs.getType() == __rhs.getType(); }
+};
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  typedef std::unordered_set<PathPoint, PathPointHasher, PathPointEqual> 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/exception/safety.h b/libstdc++-v3/testsuite/util/exception/safety.h
index b85f7fe..5041898 100644
--- a/libstdc++-v3/testsuite/util/exception/safety.h
+++ b/libstdc++-v3/testsuite/util/exception/safety.h
@@ -826,6 +826,110 @@ namespace __gnu_test
 	operator()(_Tp&, _Tp&) { }
       };
 
+    template<typename _Tp,
+	     bool = traits<_Tp>::has_emplace::value>
+      struct emplace;
+
+    // Specialization for most containers.
+    template<typename _Tp>
+      struct emplace<_Tp, true>
+      {
+	typedef _Tp					container_type;
+	typedef typename container_type::value_type	value_type;
+	typedef typename container_type::size_type	size_type;
+
+	void
+	operator()(_Tp& __test)
+	{
+	  try
+	    {
+	      const value_type cv = generate_unique<value_type>();
+	      __test.emplace(cv);
+	    }
+	  catch(const __gnu_cxx::forced_error&)
+	    { throw; }
+	}
+
+	// Assumes containers start out equivalent.
+	void
+	operator()(_Tp& __control, _Tp& __test)
+	{
+	  try
+	    {
+	      const value_type cv = generate_unique<value_type>();
+	      __test.emplace(cv);
+	    }
+	  catch(const __gnu_cxx::forced_error&)
+	    { throw; }
+ 	}
+      };
+
+    // Specialization, empty.
+    template<typename _Tp>
+      struct emplace<_Tp, false>
+      {
+	void
+	operator()(_Tp&) { }
+
+	void
+	operator()(_Tp&, _Tp&) { }
+      };
+
+    template<typename _Tp,
+	     bool = traits<_Tp>::has_emplace::value>
+      struct emplace_hint;
+
+    // Specialization for most containers.
+    template<typename _Tp>
+      struct emplace_hint<_Tp, true>
+      {
+	typedef _Tp 				       	container_type;
+	typedef typename container_type::value_type 	value_type;
+
+	void
+	operator()(_Tp& __test)
+	{
+	  try
+	    {
+	      const value_type cv = generate_unique<value_type>();
+	      const size_type sz = std::distance(__test.begin(), __test.end());
+	      size_type s = generate(sz);
+	      auto i = __test.begin();
+	      std::advance(i, s);
+	      __test.emplace_hint(i, cv);
+	    }
+	  catch(const __gnu_cxx::forced_error&)
+	    { throw; }
+	}
+
+	// Assumes containers start out equivalent.
+	void
+	operator()(_Tp& __control, _Tp& __test)
+	{
+	  try
+	    {
+	      const value_type cv = generate_unique<value_type>();
+	      const size_type sz = std::distance(__test.begin(), __test.end());
+	      size_type s = generate(sz);
+	      auto i = __test.begin();
+	      std::advance(i, s);
+	      __test.emplace_hint(i, cv);
+	    }
+	  catch(const __gnu_cxx::forced_error&)
+	    { throw; }
+ 	}
+      };
+
+    // Specialization, empty.
+    template<typename _Tp>
+      struct emplace_hint<_Tp, false>
+      {
+	void
+	operator()(_Tp&) { }
+
+	void
+	operator()(_Tp&, _Tp&) { }
+      };
 
     template<typename _Tp, bool = traits<_Tp>::is_associative::value
 				  || traits<_Tp>::is_unordered::value>
@@ -1023,6 +1127,8 @@ namespace __gnu_test
       typedef erase_point<container_type> 	       	erase_point;
       typedef erase_range<container_type> 	       	erase_range;
       typedef insert_point<container_type> 	       	insert_point;
+      typedef emplace<container_type>			emplace;
+      typedef emplace_hint<container_type>		emplace_hint;
       typedef pop_front<container_type> 	       	pop_front;
       typedef pop_back<container_type> 			pop_back;
       typedef push_front<container_type> 	       	push_front;
@@ -1039,6 +1145,8 @@ namespace __gnu_test
       erase_point		_M_erasep;
       erase_range		_M_eraser;
       insert_point		_M_insertp;
+      emplace			_M_emplace;
+      emplace_hint		_M_emplaceh;
       pop_front			_M_popf;
       pop_back			_M_popb;
       push_front	       	_M_pushf;
@@ -1098,6 +1206,8 @@ namespace __gnu_test
 	_M_functions.push_back(function_type(base_type::_M_erasep));
 	_M_functions.push_back(function_type(base_type::_M_eraser));
 	_M_functions.push_back(function_type(base_type::_M_insertp));
+	_M_functions.push_back(function_type(base_type::_M_emplace));
+	_M_functions.push_back(function_type(base_type::_M_emplaceh));
 	_M_functions.push_back(function_type(base_type::_M_popf));
 	_M_functions.push_back(function_type(base_type::_M_popb));
 	_M_functions.push_back(function_type(base_type::_M_pushf));
diff --git a/libstdc++-v3/testsuite/util/testsuite_container_traits.h b/libstdc++-v3/testsuite/util/testsuite_container_traits.h
index 4d8ff99..cce91b7 100644
--- a/libstdc++-v3/testsuite/util/testsuite_container_traits.h
+++ b/libstdc++-v3/testsuite/util/testsuite_container_traits.h
@@ -43,6 +43,7 @@ namespace __gnu_test
     typedef std::false_type	has_throwing_erase;
     typedef std::false_type	has_insert;
     typedef std::false_type	has_insert_after;
+    typedef std::false_type	has_emplace;
     typedef std::false_type	has_push_pop;
     typedef std::false_type	has_size_type_constructor;
   };
@@ -216,6 +217,7 @@ namespace __gnu_test
 
       typedef std::true_type	has_erase;
       typedef std::true_type	has_insert;
+      typedef std::true_type	has_emplace;
     };
 
   template<typename _Tp1, typename _Tp2, typename _Tp3,
@@ -230,6 +232,7 @@ namespace __gnu_test
 
       typedef std::true_type	has_erase;
       typedef std::true_type	has_insert;
+      typedef std::true_type	has_emplace;
     };
 
   template<typename _Tp1, typename _Tp2, typename _Tp3, typename _Tp4>
@@ -242,6 +245,7 @@ namespace __gnu_test
 
       typedef std::true_type	has_erase;
       typedef std::true_type	has_insert;
+      typedef std::true_type	has_emplace;
     };
 
   template<typename _Tp1, typename _Tp2, typename _Tp3, typename _Tp4>
@@ -254,6 +258,7 @@ namespace __gnu_test
 
       typedef std::true_type	has_erase;
       typedef std::true_type	has_insert;
+      typedef std::true_type	has_emplace;
     };
 } // namespace __gnu_test