Re: Value type of map need not be default copyable

[FranÃois Dumont <frs dot dumont at gmail dot com>]

On 08/08/2012 09:34 AM, Marc Glisse wrote:
> On Tue, 7 Aug 2012, Richard Smith wrote:
>
> > > I've attached a patch for unordered_map which solves the rvalue
> > > reference problem.  For efficiency, I've created a new
> > > _M_emplace_bucket method rather than call emplace directly.
> > >
> > > I've verified all libstdc++ tests pass (sorry for the previous
> > > oversight) and am running the full GCC test suite now.  However, I'd
> > > appreciate any feedback on whether this is a reasonable approach.  STL
> > > hacking is way outside my comfort zone.  ;-)
> > >
> > > If this looks good, I'll take a stab at std::map.
> >
> > I think you should remove the mapped_type() argument from the call to
> > _M_emplace_bucket. In C++11, the mapped_type is not required to be 
> > copyable
> > at all, just to be DefaultInsertable.
>
> Indeed. The reason I was talking about emplace is that you want an 
> object to be created only at the time the node is created. That might 
> mean passing piecewise_construct_t and an empty tuple to emplace 
> (otherwise it is too similar to insert). Or for unordered_map where 
> the node functions are "exposed", you could just create the node 
> directly without passing through emplace.
This is what I try to do in the attached patch. I replace 
_M_insert_bucket with _M_insert_node and use it for operator[] 
implementation. I have also introduce a special std::pair constructor 
for container usage so that we do not have to include the whole tuple 
stuff just for associative container implementations.

However one test is failing:
/home/fdt/dev/gcc/libstdc++-v3/testsuite/23_containers/unordered_map/insert/array_syntax_move.cc:39:18: 
required from here
/home/fdt/dev/gcc-build/x86_64-unknown-linux-gnu/libstdc++-v3/include/bits/stl_pair.h:175:42: 
error: use of deleted function '__gnu_test::rvalstruct::rvalstruct(const 
__gnu_test::rvalstruct&)'
  : first(std::forward<_T1>(__x)), second() { }

I don't understand why it doesn't use the move constructor. I can't see 
any std::forward call missing. Anyone ?

FranÃois

Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h	(revision 190209)
+++ include/bits/hashtable.h	(working copy)
@@ -584,11 +584,10 @@
       __node_base*
       _M_get_previous_node(size_type __bkt, __node_base* __n);
 
-      template<typename _Arg>
-	iterator
-	_M_insert_bucket(_Arg&&, size_type, __hash_code);
+      // Insert the node n. Assumes key doesn't exist
+      iterator
+      _M_insert_node(size_type __bkt, __hash_code __code, __node_type* __n);
 
-
       template<typename... _Args>
 	std::pair<iterator, bool>
 	_M_emplace(std::true_type, _Args&&... __args);
@@ -1307,54 +1306,49 @@
 	  }
       }
 
-  // Insert v in bucket n (assumes no element with its key already present).
+  // Insert node in bucket bkt (assumes no element with its key already
+  // present). Take ownership of the passed node, deallocate it on exception.
   template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	   typename _Traits>
-    template<typename _Arg>
-      typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
-			  _H1, _H2, _Hash, _RehashPolicy,
-			  _Traits>::iterator
-      _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
-		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-      _M_insert_bucket(_Arg&& __v, size_type __n, __hash_code __code)
-      {
-	const __rehash_state& __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);
+    typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+			_H1, _H2, _Hash, _RehashPolicy,
+			_Traits>::iterator
+    _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+    _M_insert_node(size_type __bkt, __hash_code __code, __node_type* __node)
+    {
+      const __rehash_state& __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)
-	  {
-	    const key_type& __k = this->_M_extract()(__v);
-	    __n = __hash_code_base::_M_bucket_index(__k, __code,
+      if (__do_rehash.first)
+	{
+	  const key_type& __k = this->_M_extract()(__node->_M_v);
+	  __bkt = __hash_code_base::_M_bucket_index(__k, __code,
 						    __do_rehash.second);
-	  }
+	}
 
-	__node_type* __node = nullptr;
-	__try
-	  {
-	    // Allocate the new node before doing the rehash so that we
-	    // don't do a rehash if the allocation throws.
-	    __node = _M_allocate_node(std::forward<_Arg>(__v));
-	    this->_M_store_code(__node, __code);
-	    if (__do_rehash.first)
-	      _M_rehash(__do_rehash.second, __saved_state);
+      __try
+	{
+	  if (__do_rehash.first)
+	    _M_rehash(__do_rehash.second, __saved_state);
 
-	    _M_insert_bucket_begin(__n, __node);
-	    ++_M_element_count;
-	    return iterator(__node);
-	  }
-	__catch(...)
-	  {
-	    if (!__node)
-	      _M_rehash_policy._M_reset(__saved_state);
-	    else
-	      _M_deallocate_node(__node);
-	    __throw_exception_again;
-	  }
-      }
+	  _M_insert_bucket_begin(__bkt, __node);
+	  ++_M_element_count;
+	  return iterator(__node);
+	}
+      __catch(...)
+	{
+	  if (!__node)
+	    _M_rehash_policy._M_reset(__saved_state);
+	  else
+	    _M_deallocate_node(__node);
+	  __throw_exception_again;
+	}
+    }
 
   // Insert v if no element with its key is already present.
   template<typename _Key, typename _Value,
@@ -1372,12 +1366,15 @@
       {
 	const key_type& __k = this->_M_extract()(__v);
 	__hash_code __code = this->_M_hash_code(__k);
-	size_type __n = _M_bucket_index(__k, __code);
+	size_type __bkt = _M_bucket_index(__k, __code);
 
-	if (__node_type* __p = _M_find_node(__n, __k, __code))
-	  return std::make_pair(iterator(__p), false);
-	return std::make_pair(_M_insert_bucket(std::forward<_Arg>(__v),
-			      __n, __code), true);
+	__node_type* __n = _M_find_node(__bkt, __k, __code);
+	if (__n)
+	  return std::make_pair(iterator(__n), false);
+
+	__n = _M_allocate_node(std::forward<_Arg>(__v));
+	this->_M_store_code(__n, __code);
+	return std::make_pair(_M_insert_node(__bkt, __code, __n), true);
       }
 
   // Insert v unconditionally.
@@ -1441,7 +1438,6 @@
 	  }
       }
 
-
   template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
Index: include/bits/hashtable_policy.h
===================================================================
--- include/bits/hashtable_policy.h	(revision 190209)
+++ include/bits/hashtable_policy.h	(working copy)
@@ -577,8 +577,12 @@
       __node_type* __p = __h->_M_find_node(__n, __k, __code);
 
       if (!__p)
-	return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()),
-				     __n, __code)->second;
+	{
+	  __p = __h->_M_allocate_node(std::__detail::container_construct, __k);
+	  __h->_M_store_code(__p, __code);
+	  return __h->_M_insert_node(__n, __code, __p)->second;
+	}
+
       return (__p->_M_v).second;
     }
 
@@ -598,9 +602,13 @@
       __node_type* __p = __h->_M_find_node(__n, __k, __code);
 
       if (!__p)
-	return __h->_M_insert_bucket(std::make_pair(std::move(__k),
-						    mapped_type()),
-				     __n, __code)->second;
+	{
+	  __p = __h->_M_allocate_node(std::__detail::container_construct,
+				      std::forward<key_type>(__k));
+	  __h->_M_store_code(__p, __code);
+	  return __h->_M_insert_node(__n, __code, __p)->second;
+	}
+
       return (__p->_M_v).second;
     }
 
Index: include/bits/stl_pair.h
===================================================================
--- include/bits/stl_pair.h	(revision 190209)
+++ include/bits/stl_pair.h	(working copy)
@@ -81,6 +81,23 @@
 
   template<std::size_t...>
     struct _Index_tuple;
+
+_GLIBCXX_END_NAMESPACE_VERSION
+
+namespace __detail
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+  /// container_construct_t for associative container usage only.
+  struct container_construct_t { };
+
+  /// container_construct
+  constexpr container_construct_t container_construct = container_construct_t();
+
+_GLIBCXX_END_NAMESPACE_VERSION
+}
+
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
 #endif
 
  /**
@@ -151,6 +168,12 @@
       template<typename... _Args1, typename... _Args2>
         pair(piecewise_construct_t, tuple<_Args1...>, tuple<_Args2...>);
 
+      pair(std::__detail::container_construct_t, const _T1& __x)
+	: first(__x), second() { }
+
+      pair(std::__detail::container_construct_t, _T1&& __x)
+	: first(std::forward<_T1>(__x)), second() { }
+
       pair&
       operator=(const pair& __p)
       {