Patchwork Value type of map need not be default copyable

login
register
mail settings
Submitter Ollie Wild
Date Aug. 7, 2012, 9:43 p.m.
Message ID <CAFOgFcR+yDmmWjnjw7txW+3Cgcg+6hEwByPHqrADwHcbEgCdAg@mail.gmail.com>
Download mbox | patch
Permalink /patch/175807/
State New
Headers show

Comments

Ollie Wild - Aug. 7, 2012, 9:43 p.m.
On Sat, Aug 4, 2012 at 10:34 AM, Paolo Carlini <paolo.carlini@oracle.com> wrote:
>
>
> First, I think we should add libstdc++ in CC.
>
> Thus, I would recommend people working in this area to begin with
> unordered_map, because in that case emplace is already available, assuming
> that's really the point (and therefore reverting the patch was a good idea,
> luckily an existing testcase helped us)
>
> At the same time an implementation of emplace is definitely welcome, in
> any case.

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.

Thanks,
Ollie


2012-08-03  Ollie Wild  <aaw@google.com>

        * include/bits/hashtable.h (_M_emplace_bucket): New function.
        * include/bits/hashtable_policy.h (operator[](key_type&&)): Replace
        _M_insert_bucket call with _M_emplace_bucket.
        * testsuite/23_containers/unordered_map/operators/2.cc: New test.
commit dd690a5f164326c552c2450af6270ec27e9bfd8e
Author: Ollie Wild <aaw@google.com>
Date:   Tue Aug 7 16:34:05 2012 -0500

    2012-08-03  Ollie Wild  <aaw@google.com>
    
    	* include/bits/hashtable.h (_M_emplace_bucket): New function.
    	* include/bits/hashtable_policy.h (operator[](key_type&&)): Replace
    	_M_insert_bucket call with _M_emplace_bucket.
    	* testsuite/23_containers/unordered_map/operators/2.cc: New test.

 2012-08-04  Paolo Carlini  <paolo.carlini@oracle.com>
 
 	Revert:
Paolo Carlini - Aug. 7, 2012, 10:11 p.m.
Hi,

(adding in CC Francois too)

On 08/07/2012 11:43 PM, Ollie Wild wrote:
> On Sat, Aug 4, 2012 at 10:34 AM, Paolo Carlini <paolo.carlini@oracle.com> wrote:
>>
>> First, I think we should add libstdc++ in CC.
>>
>> Thus, I would recommend people working in this area to begin with
>> unordered_map, because in that case emplace is already available, assuming
>> that's really the point (and therefore reverting the patch was a good idea,
>> luckily an existing testcase helped us)
>>
>> At the same time an implementation of emplace is definitely welcome, in
>> any case.
> 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.
Patch looks already pretty good to me. A couple of comments:
- Did you consider whether _M_emplace_bucket could be used as an 
implementation detail of_M_emplace? Or figure out in any case a 
smart(er) refactoring to share code with the implementation of 
_M_emplace. I didn't study in detail your code, but I think we can avoid 
some redundancy.
- For consistency at least, I think we should get rid of the make_pair 
in the other overload too.
> 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.
That would be great. We have a PR which remained open way too much time. 
The challenge is figuring out a way to avoid writing too much code 
similar to what we have already for the inserts. Honestly, I tried, a 
while ago, and failed, didn't see an easy way, but in any case, it's 
time to have this stuff implemented - I hear Marc ;) - one way or the 
other, for 4.8.0

Thanks,
Paolo.
Marc Glisse - Aug. 8, 2012, 7:34 a.m.
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.

Patch

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 2faf0b3..869b0e9 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -588,6 +588,10 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	iterator
 	_M_insert_bucket(_Arg&&, size_type, __hash_code);
 
+      template<typename... _Args>
+	iterator
+	_M_emplace_bucket(size_type, __hash_code, _Args&&... __args);
+
 
       template<typename... _Args>
 	std::pair<iterator, bool>
@@ -1356,6 +1360,51 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  }
       }
 
+  // Insert v in bucket n (assumes no element with its key already present).
+  template<typename _Key, typename _Value,
+	   typename _Alloc, typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+	   typename _Traits>
+    template<typename... _Args>
+      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_emplace_bucket(size_type __n, __hash_code __code, _Args&&... __args)
+      {
+	// First build the node to get access to the hash code
+	__node_type* __node = _M_allocate_node(std::forward<_Args>(__args)...);
+	__try
+	  {
+
+	    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()(__node->_M_v);
+		__n = __hash_code_base::_M_bucket_index(__k, __code,
+							__do_rehash.second);
+	      }
+
+	    this->_M_store_code(__node, __code);
+	    if (__do_rehash.first)
+	      _M_rehash(__do_rehash.second, __saved_state);
+
+	    _M_insert_bucket_begin(__n, __node);
+	    ++_M_element_count;
+	    return iterator(__node);
+	  }
+	__catch(...)
+	  {
+	    _M_deallocate_node(__node);
+	    __throw_exception_again;
+	  }
+      }
+
   // Insert v if no element with its key is already present.
   template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 27790f2..addf9d13 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -598,9 +598,8 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __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;
+	return __h->_M_emplace_bucket(__n, __code,
+				      std::move(__k), mapped_type())->second;
       return (__p->_M_v).second;
     }
 
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/operators/2.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/operators/2.cc
new file mode 100644
index 0000000..1940fa2
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/operators/2.cc
@@ -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);
+}