Patchwork unordered containers emplace

login
register
mail settings
Submitter François Dumont
Date Dec. 9, 2011, 9:02 p.m.
Message ID <4EE27777.2010909@gmail.com>
Download mbox | patch
Permalink /patch/130467/
State New
Headers show

Comments

François Dumont - Dec. 9, 2011, 9:02 p.m.
Attached patch applied.

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.

Regards

On 12/09/2011 11:17 AM, Paolo Carlini wrote:
>> Ok to commit ?
> Sure, thanks!
>
> Paolo.
>

Patch

Index: doc/xml/manual/status_cxx2011.xml
===================================================================
--- doc/xml/manual/status_cxx2011.xml	(revision 182133)
+++ doc/xml/manual/status_cxx2011.xml	(working copy)
@@ -1403,11 +1403,10 @@ 
       <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>
Index: include/debug/unordered_map
===================================================================
--- include/debug/unordered_map	(revision 182133)
+++ include/debug/unordered_map	(working copy)
@@ -204,6 +204,29 @@ 
       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 @@ 
       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)
       {
Index: include/debug/unordered_set
===================================================================
--- include/debug/unordered_set	(revision 182133)
+++ include/debug/unordered_set	(working copy)
@@ -204,6 +204,29 @@ 
       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 @@ 
       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)
       {
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h	(revision 182133)
+++ include/bits/hashtable.h	(working copy)
@@ -467,6 +467,14 @@ 
 	_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 @@ 
 	_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 @@ 
       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 @@ 
 	      _M_deallocate_node(__new_node);
 	    __throw_exception_again;
 	  }
-
       }
 
   template<typename _Key, typename _Value,
Index: testsuite/23_containers/unordered_map/modifiers/emplace.cc
===================================================================
--- testsuite/23_containers/unordered_map/modifiers/emplace.cc	(revision 0)
+++ testsuite/23_containers/unordered_map/modifiers/emplace.cc	(revision 0)
@@ -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;
+}
Index: testsuite/23_containers/unordered_multimap/modifiers/emplace.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/modifiers/emplace.cc	(revision 0)
+++ testsuite/23_containers/unordered_multimap/modifiers/emplace.cc	(revision 0)
@@ -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;
+}
Index: testsuite/23_containers/unordered_set/modifiers/emplace.cc
===================================================================
--- testsuite/23_containers/unordered_set/modifiers/emplace.cc	(revision 0)
+++ testsuite/23_containers/unordered_set/modifiers/emplace.cc	(revision 0)
@@ -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;
+}
Index: testsuite/23_containers/unordered_multiset/modifiers/emplace.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/modifiers/emplace.cc	(revision 0)
+++ testsuite/23_containers/unordered_multiset/modifiers/emplace.cc	(revision 0)
@@ -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;
+}
Index: testsuite/util/exception/safety.h
===================================================================
--- testsuite/util/exception/safety.h	(revision 182133)
+++ testsuite/util/exception/safety.h	(working copy)
@@ -826,7 +826,111 @@ 
 	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>
       struct clear
@@ -1023,6 +1127,8 @@ 
       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 @@ 
       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 @@ 
 	_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));
Index: testsuite/util/testsuite_container_traits.h
===================================================================
--- testsuite/util/testsuite_container_traits.h	(revision 182133)
+++ testsuite/util/testsuite_container_traits.h	(working copy)
@@ -43,6 +43,7 @@ 
     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 @@ 
 
       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 @@ 
 
       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 @@ 
 
       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 @@ 
 
       typedef std::true_type	has_erase;
       typedef std::true_type	has_insert;
+      typedef std::true_type	has_emplace;
     };
 } // namespace __gnu_test