diff mbox

Value type of map need not be default copyable

Message ID 50241BF1.3060404@gmail.com
State New
Headers show

Commit Message

François Dumont Aug. 9, 2012, 8:22 p.m. UTC 
On 08/09/2012 10:35 AM, Paolo Carlini wrote:
> 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.
>

     Here is an updated version considering the good catch from Marc. 
However I prefer to use an explicit instantiation of tuple rather than 
using cref that would have imply inclusion of <functional> in addition 
to <tuple>. I have also updated the test case to use a type without copy 
and move constructors.

2012-08-09  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/util/testsuite_counter_type.h: New.
     * testsuite/23_containers/unordered_map/operators/2.cc: New.


François

Comments

Marc Glisse Aug. 9, 2012, 9:22 p.m. UTC | #1 
On Thu, 9 Aug 2012, François Dumont wrote:

>    Here is an updated version considering the good catch from Marc. However 
> I prefer to use an explicit instantiation of tuple rather than using cref 
> that would have imply inclusion of <functional> in addition to <tuple>.

I wouldn't have used make_tuple at all (tuple<>() is shorter than 
make_tuple()), but I wanted to stick to your style as much as possible ;-)

I don't know if std:: is needed, but it looks strange to have it only on 
some functions:
std::forward_as_tuple(forward<key_type>(__k)),

Looking at this line again, you seem to be using std::forward on something 
that is not a deduced parameter type. I guess it is equivalent to 
std::move in this case, it just confuses me a bit.

>    * include/std/unordered_map: Include tuple.
>    * include/std/unordered_set: Likewise.

Is it a libstdc++ policy to put all includes in the topmost headers, as 
opposed to the header where they are used? I never paid much attention to 
it, I was just surprised because it doesn't match what I do in my code. 
But since hashtable*.h currently include nothing, it is consistent. Does 
that help with compile-time?

(ok, it is a bit obvious that I pretended to make a review just so I had 
an excuse to ask a question at the end ;-)
Paolo Carlini Aug. 9, 2012, 11:26 p.m. UTC | #2 
On 08/09/2012 11:22 PM, Marc Glisse wrote:
> I don't know if std:: is needed, but it looks strange to have it only 
> on some functions:
> std::forward_as_tuple(forward<key_type>(__k)),
>
> Looking at this line again, you seem to be using std::forward on 
> something that is not a deduced parameter type. I guess it is 
> equivalent to std::move in this case, it just confuses me a bit.
Wanted to point out that yesterday. Please double check std::move.

I realize now that nobody is interested in std::cref, good ;)

Thanks!
Paolo.
diff mbox

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_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::tuple<const 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;
     }
 
@@ -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: 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: 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,91 @@ 
+// 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-options "-std=gnu++11" }
+
+#include <unordered_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::unordered_map<int, Mapped> m1;
+  m1[0] = Mapped();
+
+  std::unordered_map<int, rvalstruct> m2;
+  m2[0] = rvalstruct(13);
+
+  std::unordered_map<int, DefaultConstructibleType> m3;
+  VERIFY( m3[0].val == 123 );
+  VERIFY( m3.size() == 1 );
+  m3[0] = 2;
+  VERIFY( m3[0].val == 2 );
+
+  std::unordered_map<counter_type, int,
+		     __gnu_test::counter_type_hasher> 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;
+}
Index: testsuite/util/testsuite_counter_type.h
===================================================================
--- testsuite/util/testsuite_counter_type.h	(revision 0)
+++ testsuite/util/testsuite_counter_type.h	(revision 0)
@@ -0,0 +1,123 @@ 
+// -*- C++ -*-
+//
+// 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/>.
+//
+
+#ifndef _TESTSUITE_COUNTER_TYPE_H
+#define _TESTSUITE_COUNTER_TYPE_H 1
+
+namespace __gnu_test
+{
+  // Type counting how many constructors or assign operators are invoked.
+  struct counter_type
+  {
+    // Constructor counters:
+    static int default_count;
+    static int specialize_count;
+    static int copy_count;
+    static int copy_assign_count;
+    static int less_compare_count;
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+    static int move_count;
+    static int move_assign_count;
+#endif
+
+    int val;
+    
+    counter_type() : val(0)
+    {
+      ++default_count;
+    }
+
+    counter_type(int inval) : val(inval)
+    {
+      ++specialize_count;
+    }
+
+    counter_type(const counter_type& in) : val(in.val)
+    {
+      ++copy_count;
+    }
+
+    counter_type&
+    operator=(const counter_type& in)
+    {
+      val = in.val;
+      ++copy_assign_count;
+      return *this;
+    }
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+    counter_type(counter_type&& in) noexcept
+    {
+      val = in.val;
+      ++move_count;
+    }
+
+    counter_type&
+    operator=(counter_type&& rhs)
+    {
+      val = rhs.val;
+      ++move_assign_count;
+      return *this;
+    }
+#endif
+
+    static void
+    reset()
+    {
+      default_count = 0;
+      specialize_count = 0;
+      copy_count = 0;
+      copy_assign_count = 0;
+      less_compare_count = 0;
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+      move_count = 0;
+      move_assign_count = 0;
+#endif
+    }
+
+    bool operator==(const counter_type& rhs) const
+    { return val == rhs.val; }
+
+    bool operator<(const counter_type& rhs) const
+    { return val < rhs.val; }
+  };
+
+  int counter_type::default_count = 0;
+  int counter_type::specialize_count = 0;
+  int counter_type::copy_count = 0;
+  int counter_type::copy_assign_count = 0;
+  int counter_type::less_compare_count = 0;
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+  int counter_type::move_count = 0;
+  int counter_type::move_assign_count = 0;
+#endif
+
+  struct counter_type_hasher
+  {
+    std::size_t operator()(const counter_type& c) const
+    {
+      return c.val;
+    }
+  };
+
+} // namespace __gnu_test
+#endif
+

Property changes on: testsuite/util/testsuite_counter_type.h
___________________________________________________________________
Added: svn:eol-style
   + native