Patchwork Value type of map need not be default copyable

login
register
mail settings
Submitter François Dumont
Date Aug. 8, 2012, 8:46 p.m.
Message ID <5022D02C.4070108@gmail.com>
Download mbox | patch
Permalink /patch/175956/
State New
Headers show

Comments

François Dumont - Aug. 8, 2012, 8:46 p.m.
On 08/08/2012 03:39 PM, Paolo Carlini wrote:
> On 08/08/2012 03:15 PM, François Dumont wrote:
>> 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.
> To be clear: sorry, this is not an option.
>
> Paolo.
>
     Then I can only imagine the attached patch which require to include 
tuple when including unordered_map or unordered_set. The 
std::pair(piecewise_construct_t, tuple<>, tuple<>) is the only 
constructor that allow to build a pair using the default constructor for 
the second member.

     In fact, adding declaration for std::make_tuple and 
std::forward_as_tuple could avoid to include tuple from unordered_set, 
there is no operator[] on unordered_set or unordered_multiset. But I am 
not sure it worth the effort, tell me.

     All unordered tests run under Linux x86_64, normal and debug modes.

2012-08-08  François Dumont  <fdumont@gcc.gnu.org>
         Ollie Wild  <aaw@google.com>

     * include/bits/hashtable.h (_Hashtable<>::_M_insert_bucket):
     Replace by ...
     (_Hashtable<>::_M_insert_node): ... this, new.
     (_Hashtable<>::_M_insert(_Args&&, true_type)): Use latter.
     * include/bits/hashtable_policy.h (_Map_base<>::operator[]): Use
     latter, emplace the value_type rather than insert.
     * include/std/unordered_map: Include tuple.
     * include/std/unordered_set: Likewise.
     * testsuite/23_containers/unordered_map/operators/2.cc: New.

François
Marc Glisse - Aug. 9, 2012, 7:14 a.m.
On Wed, 8 Aug 2012, François Dumont wrote:

> On 08/08/2012 03:39 PM, Paolo Carlini wrote:
>> On 08/08/2012 03:15 PM, François Dumont wrote:
>>> 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.
>> To be clear: sorry, this is not an option.
>> 
>> Paolo.
>>
>    Then I can only imagine the attached patch which require to include tuple 
> when including unordered_map or unordered_set. The 
> std::pair(piecewise_construct_t, tuple<>, tuple<>) is the only constructor 
> that allow to build a pair using the default constructor for the second 
> member.

I agree that the extra constructor would be convenient (I probably would 
have gone with pair(T&&,__default_construct_t), the symmetric version, and 
enough extra constructors to resolve all ambiguities). Maybe LWG would 
consider doing something.

+         __p = __h->_M_allocate_node(std::piecewise_construct,
+                                     std::make_tuple(__k),
+                                     std::make_tuple());

Don't you want cref(__k)? It might save a move at some point.
Paolo Carlini - Aug. 9, 2012, 8:35 a.m.
Hi,

On 08/09/2012 09:14 AM, Marc Glisse wrote:
> On Wed, 8 Aug 2012, François Dumont wrote:
>
>> On 08/08/2012 03:39 PM, Paolo Carlini wrote:
>>> On 08/08/2012 03:15 PM, François Dumont wrote:
>>>> 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.
>>> To be clear: sorry, this is not an option.
>>>
>>> Paolo.
>>>
>>    Then I can only imagine the attached patch which require to 
>> include tuple when including unordered_map or unordered_set. The 
>> std::pair(piecewise_construct_t, tuple<>, tuple<>) is the only 
>> constructor that allow to build a pair using the default constructor 
>> for the second member.
>
> I agree that the extra constructor would be convenient (I probably 
> would have gone with pair(T&&,__default_construct_t), the symmetric 
> version, and enough extra constructors to resolve all ambiguities). 
> Maybe LWG would consider doing something.
When it does, and the corresponding PR will be *ready* we'll reconsider 
the issue. After all the *months and months and months* spent by the LWG 
adding and removing members from pair and tweaking everything wrt the 
containers and issues *still* popping up (like that with the defaulted 
copy constructor vs insert constraining), and with the support for 
scoped allocators still missing from our implementation, we are not 
adding members to std::pair such easily. Sorry, but personally I'm not 
available now to further discuss this specific point.

I was still hoping that for something as simple as mapped_type() we 
wouldn't need the full <tuple> machinery, and I encourage everybody to 
have another look (while making sure anything we figure out adapts 
smoothly an consistently to std::map), then in a few days we'll take a 
final decision. We'll still have chances to further improve the code in 
time for 4.8.0.

> +         __p = __h->_M_allocate_node(std::piecewise_construct,
> +                                     std::make_tuple(__k),
> +                                     std::make_tuple());
>
> Don't you want cref(__k)? It might save a move at some point.
Are we already doing that elsewhere? I think we should aim for something 
simple first, then carefully evaluate if the additional complexity is 
worth the cost and in case deploy the superior solution consistently 
everywhere it may apply.

Thanks!
Paolo.
Jonathan Wakely - Aug. 9, 2012, noon
On 9 August 2012 09:35, Paolo Carlini wrote:
>
> When it does, and the corresponding PR will be *ready* we'll reconsider the
> issue. After all the *months and months and months* spent by the LWG adding
> and removing members from pair and tweaking everything wrt the containers
> and issues *still* popping up (like that with the defaulted copy constructor
> vs insert constraining), and with the support for scoped allocators still
> missing from our implementation, we are not adding members to std::pair such
> easily. Sorry, but personally I'm not available now to further discuss this
> specific point.

I'm with Paolo on this. No additional (non-standard) constructors in
std::pair please.

If it was possible to do without changing the ABI I'd include <tuple>
in the unordered containers anyway, when add scoped allocator support,
because std::tuple already knows how to avoid the EBO for 'final'
allocators (PR 51365).  I'd do the same in the other containers except
that they need to work in C++03 mode without std::tuple.

I think we should consider std::tuple almost as fundamental as
std::pair and shouldn't jump through hoops to avoid using it.  It's
already included by <memory> for example, to implement
std::unique_ptr, and I recently made changes to make it easier to use
std::unique_ptr internally, so we shouldn't be afraid of std::tuple
getting used more widely.

Patch

Index: include/std/unordered_map
===================================================================
--- include/std/unordered_map	(revision 190209)
+++ include/std/unordered_map	(working copy)
@@ -38,6 +38,7 @@ 
 #include <utility>
 #include <type_traits>
 #include <initializer_list>
+#include <tuple>
 #include <bits/stl_algobase.h>
 #include <bits/allocator.h>
 #include <bits/stl_function.h> // equal_to, _Identity, _Select1st
Index: include/std/unordered_set
===================================================================
--- include/std/unordered_set	(revision 190209)
+++ include/std/unordered_set	(working copy)
@@ -38,6 +38,7 @@ 
 #include <utility>
 #include <type_traits>
 #include <initializer_list>
+#include <tuple>
 #include <bits/stl_algobase.h>
 #include <bits/allocator.h>
 #include <bits/stl_function.h> // equal_to, _Identity, _Select1st
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h	(revision 190209)
+++ include/bits/hashtable.h	(working copy)
@@ -584,11 +584,11 @@ 
       __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 node in bucket bkt (assumes no element with its key already
+      // present). Take ownership of the node, deallocate it on exception.
+      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 +1307,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 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 +1367,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 +1439,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,14 @@ 
       __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::piecewise_construct,
+				      std::make_tuple(__k),
+				      std::make_tuple());
+	  __h->_M_store_code(__p, __code);
+	  return __h->_M_insert_node(__n, __code, __p)->second;
+	}
+
       return (__p->_M_v).second;
     }
 
@@ -598,9 +604,14 @@ 
       __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::piecewise_construct,
+				std::forward_as_tuple(forward<key_type>(__k)),
+				std::make_tuple());
+	  __h->_M_store_code(__p, __code);
+	  return __h->_M_insert_node(__n, __code, __p)->second;
+	}
+
       return (__p->_M_v).second;
     }
 
Index: testsuite/23_containers/unordered_map/operators/2.cc
===================================================================
--- testsuite/23_containers/unordered_map/operators/2.cc	(revision 0)
+++ testsuite/23_containers/unordered_map/operators/2.cc	(revision 0)
@@ -0,0 +1,44 @@ 
+// 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/>.
+
+// 23.5.4 template class unordered_map
+
+// This test verifies that the value type of a unordered_map need not be
+// default copyable.
+
+// { dg-do compile }
+// { dg-options "-std=gnu++11" }
+
+#include <unordered_map>
+#include <testsuite_rvalref.h>
+
+struct Mapped
+{
+  Mapped() = default;
+  explicit Mapped(const Mapped&) = default;
+};
+
+void foo()
+{
+  using __gnu_test::rvalstruct;
+
+  std::unordered_map<int, Mapped> m1;
+  m1[0] = Mapped();
+
+  std::unordered_map<int, rvalstruct> m2;
+  m2[0] = rvalstruct(13);
+}