Value type of map need not be default copyable

Value type of map need not be default copyable

[Ollie Wild]

[-- Attachment #1: Type: text/plain, Size: 606 bytes --]

Patch courtesy Richard Smith at Google:

Fix bug in the implementation of std::map's operator[]. Construct an
object of type value_type, rather than using std::make_pair, so as to
allow mapped_type to have an *explicit* copy constructor.

See [map.access] (23.4.4.3)/5 for the corresponding standardese.

Tested via bootstrap + test.

Okay for trunk?

Thanks,
Ollie


2012-08-02  Ollie Wild  <aaw@google.com>
	    Richard Smith  <richardsmith@google.com>

	* include/bits/stl_map.h (operator[](key_type&&)): Replace
	std::make_pair with value_type.
	* testsuite/23_containers/map/operators/2.cc: New test.

[-- Attachment #2: patch.txt --]
[-- Type: text/plain, Size: 1970 bytes --]

diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h
index cfd478a..a3abdd4 100644
--- a/libstdc++-v3/include/bits/stl_map.h
+++ b/libstdc++-v3/include/bits/stl_map.h
@@ -475,7 +475,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	iterator __i = lower_bound(__k);
 	// __i->first is greater than or equivalent to __k.
 	if (__i == end() || key_comp()(__k, (*__i).first))
-          __i = insert(__i, std::make_pair(std::move(__k), mapped_type()));
+          __i = insert(__i, value_type(std::move(__k), mapped_type()));
 	return (*__i).second;
       }
 #endif
diff --git a/libstdc++-v3/testsuite/23_containers/map/operators/2.cc b/libstdc++-v3/testsuite/23_containers/map/operators/2.cc
new file mode 100644
index 0000000..ce633d7
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/map/operators/2.cc
@@ -0,0 +1,38 @@
+// 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.4.4 template class map
+
+// This test verifies that the value type of a map need not be default
+// copyable.
+
+// { dg-do compile }
+// { dg-options "-std=gnu++11" }
+
+#include <map>
+
+struct Mapped {
+    Mapped();
+    explicit Mapped(const Mapped&);
+};
+
+Mapped & foo()
+{
+  std::map<int, Mapped> m;
+  return m[0];
+}

Re: Value type of map need not be default copyable

[Paolo Carlini]

Hi,

On 08/03/2012 06:17 AM, Ollie Wild wrote:
> Patch courtesy Richard Smith at Google:
>
> Fix bug in the implementation of std::map's operator[]. Construct an
> object of type value_type, rather than using std::make_pair, so as to
> allow mapped_type to have an *explicit* copy constructor.
>
> See [map.access] (23.4.4.3)/5 for the corresponding standardese.
>
> Tested via bootstrap + test.
>
> Okay for trunk?
Ok, but, can you also double check and in case fix unordered_map too? 
Looks like we have the same issue, right?

Thanks!
Paolo.

PS: remember that all the library patches go to libstdc++@ too, and 
preferably please add something to the Subject about the library (like 
"[v3] ... ")

Re: Value type of map need not be default copyable

[Ollie Wild]

On Fri, Aug 3, 2012 at 2:39 AM, Paolo Carlini <paolo.carlini@oracle.com> wrote:
>
> Ok, but, can you also double check and in case fix unordered_map too?
> Looks like we have the same issue, right?

Indeed, we do.  I'll send a separate patch for the unordered_map problem.

>
> Thanks!
> Paolo.
>
> PS: remember that all the library patches go to libstdc++@ too, and
> preferably please add something to the Subject about the library (like "[v3]
> ... ")

Thanks for the reminder.

Ollie

Re: Value type of map need not be default copyable

[Paolo Carlini]

On 08/03/2012 05:19 PM, Ollie Wild wrote:
> On Fri, Aug 3, 2012 at 2:39 AM, Paolo Carlini <paolo.carlini@oracle.com> wrote:
>> Ok, but, can you also double check and in case fix unordered_map too?
>> Looks like we have the same issue, right?
> Indeed, we do.  I'll send a separate patch for the unordered_map problem.
But apparently something doesn't work together with the complex tangle 
of issues having to do with Core/1402 (aka c++/53733): the new testcase 
doesn't compile in mainline.

Thus, I'm reverting the patch for now. The we'll have to reanalyze 
whether the library specs should be further tweaked (beyond the 
container' bits of libstdc++/53657) in the light of Core/1402.

Paolo.

Re: Value type of map need not be default copyable

[Paolo Carlini]

.. note anyway, that only the new testcase was failing, no regressions 
on pre existing testcases. Thus, it may well be that only the testcase 
had issues, whereas the code changes themselves (likewise those for 
unordered_map) are fine as they are, no changes needed elsewhere, neithe 
in the specs nor in our code. I didn't really further investigate so far 
(in any case we don't want unexpected fails in the testsuite)

Iw would be great if you could get into the details.

Thanks,
Paolo.

Re: Value type of map need not be default copyable

[Marc Glisse]

On Sat, 4 Aug 2012, Paolo Carlini wrote:

> .. note anyway, that only the new testcase was failing, no regressions on pre 
> existing testcases.

What I am seeing is a different testcase (with the same name but in a 
different directory) failing, because:

   typedef std::pair<const rvalstruct,rvalstruct> V;
   static_assert(std::is_constructible<V, V&&>::value,"too bad");

and it makes sense, since you end up having to construct a rvalstruct from 
a rvalstruct const&&.

make_pair constructs a pair without const, from which a pair with const is 
constructible, though I am surprised it doesn't fail somewhere further. I 
don't know what the right solution is, maybe something emplace-like. In 
any case, make_pair is unlikely to be right.

-- 
Marc Glisse

Re: Value type of map need not be default copyable

[Paolo Carlini]

On 08/04/2012 03:26 PM, Marc Glisse wrote:
> On Sat, 4 Aug 2012, Paolo Carlini wrote:
>
>> .. note anyway, that only the new testcase was failing, no 
>> regressions on pre existing testcases.
>
> What I am seeing is a different testcase (with the same name but in a 
> different directory) failing, because:
>
>   typedef std::pair<const rvalstruct,rvalstruct> V;
>   static_assert(std::is_constructible<V, V&&>::value,"too bad");
>
> and it makes sense, since you end up having to construct a rvalstruct 
> from a rvalstruct const&&.
Oops, you are right, sorry. To be clear, the testcase which was failing 
with the patch applied is (just check testresults, many examples) is:

   23_containers/map/element_access/2.cc

> make_pair constructs a pair without const, from which a pair with 
> const is constructible, though I am surprised it doesn't fail 
> somewhere further. I don't know what the right solution is, maybe 
> something emplace-like. In any case, make_pair is unlikely to be right.
I'm not sure to understand which specific testcase you are discussing, 
but for sure we don't want regressions. I agree that we should assume a 
priori that the standard is right, but correcting the make_pair should 
not lead to failures elsewhere (unless a proper analysis establishes 
that the existing testcases are wrong)

Paolo.

Re: Value type of map need not be default copyable

[Marc Glisse]

On Sat, 4 Aug 2012, Paolo Carlini wrote:

> I'm not sure to understand which specific testcase you are discussing, but 
> for sure we don't want regressions. I agree that we should assume a priori 
> that the standard is right, but correcting the make_pair should not lead to 
> failures elsewhere (unless a proper analysis establishes that the existing 
> testcases are wrong)

Let's say it currently works by accident. What I believe is needed is to 
implement the missing emplace function, and then operator[] and others can 
be made to use it.

-- 
Marc Glisse

Re: Value type of map need not be default copyable

[Paolo Carlini]

On 08/04/2012 05:16 PM, Marc Glisse wrote:
> On Sat, 4 Aug 2012, Paolo Carlini wrote:
>
>> I'm not sure to understand which specific testcase you are 
>> discussing, but for sure we don't want regressions. I agree that we 
>> should assume a priori that the standard is right, but correcting the 
>> make_pair should not lead to failures elsewhere (unless a proper 
>> analysis establishes that the existing testcases are wrong)
>
> Let's say it currently works by accident. What I believe is needed is 
> to implement the missing emplace function, and then operator[] and 
> others can be made to use it.
Are you really sure that emplace is involved? I'm not. The letter of the 
standard uses 'inserts'.

Paolo.

Re: Value type of map need not be default copyable

[Marc Glisse]

On Sat, 4 Aug 2012, Paolo Carlini wrote:

> On 08/04/2012 05:16 PM, Marc Glisse wrote:
>> On Sat, 4 Aug 2012, Paolo Carlini wrote:
>> 
>>> I'm not sure to understand which specific testcase you are discussing, but 
>>> for sure we don't want regressions. I agree that we should assume a priori 
>>> that the standard is right, but correcting the make_pair should not lead 
>>> to failures elsewhere (unless a proper analysis establishes that the 
>>> existing testcases are wrong)
>> 
>> Let's say it currently works by accident. What I believe is needed is to 
>> implement the missing emplace function, and then operator[] and others can 
>> be made to use it.
> Are you really sure that emplace is involved? I'm not. The letter of the 
> standard uses 'inserts'.

The font indicates it is "english" insert, not "function" insert. In the 
testcase, value_type is not move constructible, so once you have an object 
of type value_type, you can't do anything with it.

-- 
Marc Glisse

Re: Value type of map need not be default copyable

[Paolo Carlini]

On 08/04/2012 05:27 PM, Marc Glisse wrote:
> On Sat, 4 Aug 2012, Paolo Carlini wrote:
>
>> On 08/04/2012 05:16 PM, Marc Glisse wrote:
>>> On Sat, 4 Aug 2012, Paolo Carlini wrote:
>>>
>>>> I'm not sure to understand which specific testcase you are 
>>>> discussing, but for sure we don't want regressions. I agree that we 
>>>> should assume a priori that the standard is right, but correcting 
>>>> the make_pair should not lead to failures elsewhere (unless a 
>>>> proper analysis establishes that the existing testcases are wrong)
>>>
>>> Let's say it currently works by accident. What I believe is needed 
>>> is to implement the missing emplace function, and then operator[] 
>>> and others can be made to use it.
>> Are you really sure that emplace is involved? I'm not. The letter of 
>> the standard uses 'inserts'.
> The font indicates it is "english" insert, not "function" insert. In 
> the testcase, value_type is not move constructible, so once you have 
> an object of type value_type, you can't do anything with it.
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.

Paolo.

Re: Value type of map need not be default copyable

[Ollie Wild]

[-- Attachment #1: Type: text/plain, Size: 1301 bytes --]

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.

[-- Attachment #2: patch.txt --]
[-- Type: text/plain, Size: 5023 bytes --]

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:
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);
+}

Re: Value type of map need not be default copyable

[Paolo Carlini]

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.

Re: Value type of map need not be default copyable

[Marc Glisse]

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.

-- 
Marc Glisse

Re: Value type of map need not be default copyable

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 2048 bytes --]

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


[-- Attachment #2: hashtable.patch --]
[-- Type: text/x-patch, Size: 6828 bytes --]

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)
       {

Re: Value type of map need not be default copyable

[Paolo Carlini]

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.

Re: Value type of map need not be default copyable

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 1545 bytes --]

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


[-- Attachment #2: hashtable.patch --]
[-- Type: text/x-patch, Size: 8372 bytes --]

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);
+}

Re: Value type of map need not be default copyable

[Marc Glisse]

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.

-- 
Marc Glisse

Re: Value type of map need not be default copyable

[Paolo Carlini]

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.

Re: Value type of map need not be default copyable

[Jonathan Wakely]

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.

Re: Value type of map need not be default copyable

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 3544 bytes --]

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




[-- Attachment #2: hashtable.patch --]
[-- Type: text/x-patch, Size: 12871 bytes --]

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

Re: Value type of map need not be default copyable

[Marc Glisse]

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 ;-)

-- 
Marc Glisse

Re: Value type of map need not be default copyable

[Paolo Carlini]

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.

Re: Value type of map need not be default copyable

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 2580 bytes --]

     Here is an other attempt. I took the time to refactor the hashtable 
implementation. I prefer to rename _M_insert_node into 
_M_insert_unique_node and use it also into _M_emplace implementation. I 
introduce _M_insert_multi_node that is used in _M_insert and _M_emplace 
when keys are not unique.

     Your remark on using std::move rather than std::forward Marc made 
sens but didn't work. I don't understand why but the new test is showing 
that std::forward works. If anyone can explain why std::move doesn't 
work I am interested.

     For your question regarding how to include headers I just follow 
current method. Normally it is done so to make headers more reusable but 
in this case I agree that hashtable_policy.h can't be included without 
<tuple> before. Should I put <tuple> include into hashtable_policy.h ? 
Adding a declaration of std::tuple in hashtable_policy.h could make this 
header less dependent on <tuple>, should I do so ?

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

     * include/bits/hashtable.h
     (_Hashtable<>_M_insert_multi_node(hash_code, node_type*)): New.
     (_Hashtable<>_M_insert(_Args&&, false_type)): Use latter.
     (_Hashtable<>::_M_emplace(false_type, _Args&&...)): Likewise.
     (_Hashtable<>::_M_insert_bucket): Replace by ...
     (_Hashtable<>::_M_insert_unique_node(size_type, hash_code, 
node_type*)):
     ... this, new.
     (_Hashtable<>::_M_insert(_Args&&, true_type)): Use latter.
     (_Hashtable<>::_M_emplace(true_type, _Args&&...)): Likewise.
     * 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.

Tested under linux x86_64, normal and debug mode.

Ok for trunk ?

François

On 08/10/2012 01:26 AM, Paolo Carlini wrote:
> 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.
>


[-- Attachment #2: hashtable.patch --]
[-- Type: text/x-patch, Size: 19925 bytes --]

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,10 +584,17 @@
       __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 with hash code __code, in bucket bkt if no rehash (assumes
+      // no element with its key already present). Take ownership of the node,
+      // deallocate it on exception.
+      iterator
+      _M_insert_unique_node(size_type __bkt, __hash_code __code,
+			    __node_type* __n);
 
+      // Insert node with hash code __code. Take ownership of the node,
+      // deallocate it on exception.
+      iterator
+      _M_insert_multi_node(__hash_code __code, __node_type* __n);
 
       template<typename... _Args>
 	std::pair<iterator, bool>
@@ -1214,42 +1221,29 @@
       {
 	// First build the node to get access to the hash code
 	__node_type* __node = _M_allocate_node(std::forward<_Args>(__args)...);
+	const key_type& __k = this->_M_extract()(__node->_M_v);
+	__hash_code __code;
 	__try
 	  {
-	    const key_type& __k = this->_M_extract()(__node->_M_v);
-	    __hash_code __code = this->_M_hash_code(__k);
-	    size_type __bkt = _M_bucket_index(__k, __code);
-
-	    if (__node_type* __p = _M_find_node(__bkt, __k, __code))
-	      {
-		// There is already an equivalent node, no insertion
-		_M_deallocate_node(__node);
-		return std::make_pair(iterator(__p), false);
-	      }
-
-	    // We are going to insert this node
-	    this->_M_store_code(__node, __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);
-
-	    if (__do_rehash.first)
-	      {
-		_M_rehash(__do_rehash.second, __saved_state);
-		__bkt = _M_bucket_index(__k, __code);
-	      }
-
-	    _M_insert_bucket_begin(__bkt, __node);
-	    ++_M_element_count;
-	    return std::make_pair(iterator(__node), true);
+	    __code = this->_M_hash_code(__k);
 	  }
 	__catch(...)
 	  {
 	    _M_deallocate_node(__node);
 	    __throw_exception_again;
 	  }
+
+	size_type __bkt = _M_bucket_index(__k, __code);
+	if (__node_type* __p = _M_find_node(__bkt, __k, __code))
+	  {
+	    // There is already an equivalent node, no insertion
+	    _M_deallocate_node(__node);
+	    return std::make_pair(iterator(__p), false);
+	  }
+
+	// Insert the node
+	return std::make_pair(_M_insert_unique_node(__bkt, __code, __node),
+			      true);
       }
 
   template<typename _Key, typename _Value,
@@ -1264,98 +1258,111 @@
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
       _M_emplace(std::false_type, _Args&&... __args)
       {
-	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);
-
 	// First build the node to get its hash code.
 	__node_type* __node = _M_allocate_node(std::forward<_Args>(__args)...);
+
+	__hash_code __code;
 	__try
 	  {
-	    const key_type& __k = this->_M_extract()(__node->_M_v);
-	    __hash_code __code = this->_M_hash_code(__k);
-	    this->_M_store_code(__node, __code);
-
-	    // Second, do rehash if necessary.
-	    if (__do_rehash.first)
-		_M_rehash(__do_rehash.second, __saved_state);
-
-	    // Third, find the node before an equivalent one.
-	    size_type __bkt = _M_bucket_index(__k, __code);
-	    __node_base* __prev = _M_find_before_node(__bkt, __k, __code);
-
-	    if (__prev)
-	      {
-		// Insert after the node before the equivalent one.
-		__node->_M_nxt = __prev->_M_nxt;
-		__prev->_M_nxt = __node;
-	      }
-	    else
-	      // The inserted node has no equivalent in the
-	      // hashtable. We must insert the new node at the
-	      // beginning of the bucket to preserve equivalent
-	      // elements relative positions.
-	      _M_insert_bucket_begin(__bkt, __node);
-	    ++_M_element_count;
-	    return iterator(__node);
+	    __code = this->_M_hash_code(this->_M_extract()(__node->_M_v));
 	  }
 	__catch(...)
 	  {
 	    _M_deallocate_node(__node);
 	    __throw_exception_again;
 	  }
+
+	return _M_insert_multi_node(__code, __node);
       }
 
-  // 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 _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_unique_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,
-						    __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)
+      __try
+	{
+	  if (__do_rehash.first)
+	    {
 	      _M_rehash(__do_rehash.second, __saved_state);
+	      __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v), __code);
+	    }
 
-	    _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;
-	  }
-      }
+	  this->_M_store_code(__node, __code);
 
+	  // Always insert at the begining of the bucket.
+	  _M_insert_bucket_begin(__bkt, __node);
+	  ++_M_element_count;
+	  return iterator(__node);
+	}
+      __catch(...)
+	{
+	  _M_deallocate_node(__node);
+	  __throw_exception_again;
+	}
+    }
+
+  // Insert node, in bucket bkt if no rehash (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>
+    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_multi_node(__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);
+
+      __try
+	{
+	  if (__do_rehash.first)
+	    _M_rehash(__do_rehash.second, __saved_state);
+
+	  this->_M_store_code(__node, __code);
+	  const key_type& __k = this->_M_extract()(__node->_M_v);
+	  size_type __bkt = _M_bucket_index(__k, __code);
+
+	  // Find the node before an equivalent one.
+	  __node_base* __prev = _M_find_before_node(__bkt, __k, __code);
+	  if (__prev)
+	    {
+	      // Insert after the node before the equivalent one.
+	      __node->_M_nxt = __prev->_M_nxt;
+	      __prev->_M_nxt = __node;
+	    }
+	  else
+	    // The inserted node has no equivalent in the
+	    // hashtable. We must insert the new node at the
+	    // beginning of the bucket to preserve equivalent
+	    // elements relative positions.
+	    _M_insert_bucket_begin(__bkt, __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,
@@ -1372,12 +1379,14 @@
       {
 	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));
+	return std::make_pair(_M_insert_unique_node(__bkt, __code, __n), true);
       }
 
   // Insert v unconditionally.
@@ -1393,55 +1402,16 @@
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
       _M_insert(_Arg&& __v, std::false_type)
       {
-	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);
-
-	// First compute the hash code so that we don't do anything if
-	// it throws.
+	// First compute the hash code so that we don't do anything if it
+	// throws.
 	__hash_code __code = this->_M_hash_code(this->_M_extract()(__v));
 
-	__node_type* __node = nullptr;
-	__try
-	  {
-	    // Second allocate new node so that we don't rehash if it 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);
+	// Second allocate new node so that we don't rehash if it throws.
+	__node_type* __node = _M_allocate_node(std::forward<_Arg>(__v));
 
-	    // Third, find the node before an equivalent one.
-	    size_type __bkt = _M_bucket_index(__node);
-	    __node_base* __prev
-	      = _M_find_before_node(__bkt, this->_M_extract()(__node->_M_v),
-				    __code);
-	    if (__prev)
-	      {
-		// Insert after the node before the equivalent one.
-		__node->_M_nxt = __prev->_M_nxt;
-		__prev->_M_nxt = __node;
-	      }
-	    else
-	      // The inserted node has no equivalent in the
-	      // hashtable. We must insert the new node at the
-	      // beginning of the bucket to preserve equivalent
-	      // elements relative positions.
-	      _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;
-	  }
+	return _M_insert_multi_node(__code, __node);
       }
 
-
   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,13 @@
       __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::tuple<>());
+	  return __h->_M_insert_unique_node(__n, __code, __p)->second;
+	}
+
       return (__p->_M_v).second;
     }
 
@@ -598,9 +603,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::piecewise_construct,
+			std::forward_as_tuple(std::forward<key_type>(__k)),
+			std::tuple<>());
+	  return __h->_M_insert_unique_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,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

Re: Value type of map need not be default copyable

[Marc Glisse]

On Sat, 11 Aug 2012, François Dumont wrote:

>    Your remark on using std::move rather than std::forward Marc made sens 
> but didn't work. I don't understand why but the new test is showing that 
> std::forward works. If anyone can explain why std::move doesn't work I am 
> interested.

What testcase failed? I just tried the 2.cc file you added with the patch, 
and replacing forward<key_type>(__k) with move(__k) compiled fine.

-- 
Marc Glisse

Re: Value type of map need not be default copyable

[Jonathan Wakely]

On 11 August 2012 14:47, Marc Glisse wrote:
>
> What testcase failed? I just tried the 2.cc file you added with the patch,
> and replacing forward<key_type>(__k) with move(__k) compiled fine.

Shouldn't it be std::move(__k) to disable ADL though?

Re: Value type of map need not be default copyable

[Marc Glisse]

On Sun, 12 Aug 2012, Jonathan Wakely wrote:

> On 11 August 2012 14:47, Marc Glisse wrote:
>>
>> What testcase failed? I just tried the 2.cc file you added with the patch,
>> and replacing forward<key_type>(__k) with move(__k) compiled fine.
>
> Shouldn't it be std::move(__k) to disable ADL though?

It is written std::forward, so replacing forward with move gives std::move 
;-)

(OK, that was just luck, good remark)

-- 
Marc Glisse

Re: Value type of map need not be default copyable

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 1687 bytes --]

On 08/11/2012 03:47 PM, Marc Glisse wrote:
> On Sat, 11 Aug 2012, François Dumont wrote:
>
>>    Your remark on using std::move rather than std::forward Marc made 
>> sens but didn't work. I don't understand why but the new test is 
>> showing that std::forward works. If anyone can explain why std::move 
>> doesn't work I am interested.
>
> What testcase failed? I just tried the 2.cc file you added with the 
> patch, and replacing forward<key_type>(__k) with move(__k) compiled fine.
>

     You are right, I replaced std::forward<key_type> with 
std::move<key_type> forcing a wrong type deduction in std::move. With a 
simple std::move() it works fine. So here is the patch again.

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

     * include/bits/hashtable.h
     (_Hashtable<>_M_insert_multi_node(hash_code, node_type*)): New.
     (_Hashtable<>_M_insert(_Args&&, false_type)): Use latter.
     (_Hashtable<>::_M_emplace(false_type, _Args&&...)): Likewise.
     (_Hashtable<>::_M_insert_bucket): Replace by ...
     (_Hashtable<>::_M_insert_unique_node(size_type, hash_code, 
node_type*)):
     ... this, new.
     (_Hashtable<>::_M_insert(_Args&&, true_type)): Use latter.
     (_Hashtable<>::_M_emplace(true_type, _Args&&...)): Likewise.
     * 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.

Tested under Linux x86_64.

Ok for trunk ?

François


[-- Attachment #2: hashtable.patch --]
[-- Type: text/x-patch, Size: 19926 bytes --]

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,10 +584,17 @@
       __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 with hash code __code, in bucket bkt if no rehash (assumes
+      // no element with its key already present). Take ownership of the node,
+      // deallocate it on exception.
+      iterator
+      _M_insert_unique_node(size_type __bkt, __hash_code __code,
+			    __node_type* __n);
 
+      // Insert node with hash code __code. Take ownership of the node,
+      // deallocate it on exception.
+      iterator
+      _M_insert_multi_node(__hash_code __code, __node_type* __n);
 
       template<typename... _Args>
 	std::pair<iterator, bool>
@@ -1214,42 +1221,29 @@
       {
 	// First build the node to get access to the hash code
 	__node_type* __node = _M_allocate_node(std::forward<_Args>(__args)...);
+	const key_type& __k = this->_M_extract()(__node->_M_v);
+	__hash_code __code;
 	__try
 	  {
-	    const key_type& __k = this->_M_extract()(__node->_M_v);
-	    __hash_code __code = this->_M_hash_code(__k);
-	    size_type __bkt = _M_bucket_index(__k, __code);
-
-	    if (__node_type* __p = _M_find_node(__bkt, __k, __code))
-	      {
-		// There is already an equivalent node, no insertion
-		_M_deallocate_node(__node);
-		return std::make_pair(iterator(__p), false);
-	      }
-
-	    // We are going to insert this node
-	    this->_M_store_code(__node, __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);
-
-	    if (__do_rehash.first)
-	      {
-		_M_rehash(__do_rehash.second, __saved_state);
-		__bkt = _M_bucket_index(__k, __code);
-	      }
-
-	    _M_insert_bucket_begin(__bkt, __node);
-	    ++_M_element_count;
-	    return std::make_pair(iterator(__node), true);
+	    __code = this->_M_hash_code(__k);
 	  }
 	__catch(...)
 	  {
 	    _M_deallocate_node(__node);
 	    __throw_exception_again;
 	  }
+
+	size_type __bkt = _M_bucket_index(__k, __code);
+	if (__node_type* __p = _M_find_node(__bkt, __k, __code))
+	  {
+	    // There is already an equivalent node, no insertion
+	    _M_deallocate_node(__node);
+	    return std::make_pair(iterator(__p), false);
+	  }
+
+	// Insert the node
+	return std::make_pair(_M_insert_unique_node(__bkt, __code, __node),
+			      true);
       }
 
   template<typename _Key, typename _Value,
@@ -1264,98 +1258,111 @@
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
       _M_emplace(std::false_type, _Args&&... __args)
       {
-	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);
-
 	// First build the node to get its hash code.
 	__node_type* __node = _M_allocate_node(std::forward<_Args>(__args)...);
+
+	__hash_code __code;
 	__try
 	  {
-	    const key_type& __k = this->_M_extract()(__node->_M_v);
-	    __hash_code __code = this->_M_hash_code(__k);
-	    this->_M_store_code(__node, __code);
-
-	    // Second, do rehash if necessary.
-	    if (__do_rehash.first)
-		_M_rehash(__do_rehash.second, __saved_state);
-
-	    // Third, find the node before an equivalent one.
-	    size_type __bkt = _M_bucket_index(__k, __code);
-	    __node_base* __prev = _M_find_before_node(__bkt, __k, __code);
-
-	    if (__prev)
-	      {
-		// Insert after the node before the equivalent one.
-		__node->_M_nxt = __prev->_M_nxt;
-		__prev->_M_nxt = __node;
-	      }
-	    else
-	      // The inserted node has no equivalent in the
-	      // hashtable. We must insert the new node at the
-	      // beginning of the bucket to preserve equivalent
-	      // elements relative positions.
-	      _M_insert_bucket_begin(__bkt, __node);
-	    ++_M_element_count;
-	    return iterator(__node);
+	    __code = this->_M_hash_code(this->_M_extract()(__node->_M_v));
 	  }
 	__catch(...)
 	  {
 	    _M_deallocate_node(__node);
 	    __throw_exception_again;
 	  }
+
+	return _M_insert_multi_node(__code, __node);
       }
 
-  // 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 _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_unique_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,
-						    __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)
+      __try
+	{
+	  if (__do_rehash.first)
+	    {
 	      _M_rehash(__do_rehash.second, __saved_state);
+	      __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v), __code);
+	    }
 
-	    _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;
-	  }
-      }
+	  this->_M_store_code(__node, __code);
 
+	  // Always insert at the begining of the bucket.
+	  _M_insert_bucket_begin(__bkt, __node);
+	  ++_M_element_count;
+	  return iterator(__node);
+	}
+      __catch(...)
+	{
+	  _M_deallocate_node(__node);
+	  __throw_exception_again;
+	}
+    }
+
+  // Insert node, in bucket bkt if no rehash (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>
+    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_multi_node(__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);
+
+      __try
+	{
+	  if (__do_rehash.first)
+	    _M_rehash(__do_rehash.second, __saved_state);
+
+	  this->_M_store_code(__node, __code);
+	  const key_type& __k = this->_M_extract()(__node->_M_v);
+	  size_type __bkt = _M_bucket_index(__k, __code);
+
+	  // Find the node before an equivalent one.
+	  __node_base* __prev = _M_find_before_node(__bkt, __k, __code);
+	  if (__prev)
+	    {
+	      // Insert after the node before the equivalent one.
+	      __node->_M_nxt = __prev->_M_nxt;
+	      __prev->_M_nxt = __node;
+	    }
+	  else
+	    // The inserted node has no equivalent in the
+	    // hashtable. We must insert the new node at the
+	    // beginning of the bucket to preserve equivalent
+	    // elements relative positions.
+	    _M_insert_bucket_begin(__bkt, __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,
@@ -1372,12 +1379,14 @@
       {
 	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));
+	return std::make_pair(_M_insert_unique_node(__bkt, __code, __n), true);
       }
 
   // Insert v unconditionally.
@@ -1393,55 +1402,16 @@
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
       _M_insert(_Arg&& __v, std::false_type)
       {
-	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);
-
-	// First compute the hash code so that we don't do anything if
-	// it throws.
+	// First compute the hash code so that we don't do anything if it
+	// throws.
 	__hash_code __code = this->_M_hash_code(this->_M_extract()(__v));
 
-	__node_type* __node = nullptr;
-	__try
-	  {
-	    // Second allocate new node so that we don't rehash if it 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);
+	// Second allocate new node so that we don't rehash if it throws.
+	__node_type* __node = _M_allocate_node(std::forward<_Arg>(__v));
 
-	    // Third, find the node before an equivalent one.
-	    size_type __bkt = _M_bucket_index(__node);
-	    __node_base* __prev
-	      = _M_find_before_node(__bkt, this->_M_extract()(__node->_M_v),
-				    __code);
-	    if (__prev)
-	      {
-		// Insert after the node before the equivalent one.
-		__node->_M_nxt = __prev->_M_nxt;
-		__prev->_M_nxt = __node;
-	      }
-	    else
-	      // The inserted node has no equivalent in the
-	      // hashtable. We must insert the new node at the
-	      // beginning of the bucket to preserve equivalent
-	      // elements relative positions.
-	      _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;
-	  }
+	return _M_insert_multi_node(__code, __node);
       }
 
-
   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,13 @@
       __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::tuple<>());
+	  return __h->_M_insert_unique_node(__n, __code, __p)->second;
+	}
+
       return (__p->_M_v).second;
     }
 
@@ -598,9 +603,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::piecewise_construct,
+				      std::forward_as_tuple(std::move(__k)),
+				      std::tuple<>());
+	  return __h->_M_insert_unique_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,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

Re: Value type of map need not be default copyable

[Paolo Carlini]

On 08/12/2012 10:00 PM, François Dumont wrote:
> On 08/11/2012 03:47 PM, Marc Glisse wrote:
>> On Sat, 11 Aug 2012, François Dumont wrote:
>>
>>>    Your remark on using std::move rather than std::forward Marc made 
>>> sens but didn't work. I don't understand why but the new test is 
>>> showing that std::forward works. If anyone can explain why std::move 
>>> doesn't work I am interested.
>>
>> What testcase failed? I just tried the 2.cc file you added with the 
>> patch, and replacing forward<key_type>(__k) with move(__k) compiled 
>> fine.
>>
>
>     You are right, I replaced std::forward<key_type> with 
> std::move<key_type> forcing a wrong type deduction in std::move. With 
> a simple std::move() it works fine. So here is the patch again.
>
> 2012-08-10  François Dumont  <fdumont@gcc.gnu.org>
>         Ollie Wild  <aaw@google.com>
>
>     * include/bits/hashtable.h
>     (_Hashtable<>_M_insert_multi_node(hash_code, node_type*)): New.
>     (_Hashtable<>_M_insert(_Args&&, false_type)): Use latter.
>     (_Hashtable<>::_M_emplace(false_type, _Args&&...)): Likewise.
>     (_Hashtable<>::_M_insert_bucket): Replace by ...
>     (_Hashtable<>::_M_insert_unique_node(size_type, hash_code, 
> node_type*)):
>     ... this, new.
>     (_Hashtable<>::_M_insert(_Args&&, true_type)): Use latter.
>     (_Hashtable<>::_M_emplace(true_type, _Args&&...)): Likewise.
>     * 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.
>
> Tested under Linux x86_64.
>
> Ok for trunk ?
Ok, thanks!

Paolo.

PS: you may want to remove the trailing blank line of 
testsuite_counter_type.h

Re: Value type of map need not be default copyable

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 1207 bytes --]

On 08/13/2012 02:10 PM, Paolo Carlini wrote:
> On 08/12/2012 10:00 PM, François Dumont wrote:
>> Ok for trunk ?
> Ok, thanks!
>
> Paolo.
>
> PS: you may want to remove the trailing blank line of 
> testsuite_counter_type.h
>

Attached patch applied.

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

     * include/bits/hashtable.h
     (_Hashtable<>_M_insert_multi_node(hash_code, node_type*)): New.
     (_Hashtable<>_M_insert(_Args&&, false_type)): Use latter.
     (_Hashtable<>::_M_emplace(false_type, _Args&&...)): Likewise.
     (_Hashtable<>::_M_insert_bucket): Replace by ...
     (_Hashtable<>::_M_insert_unique_node(size_type, hash_code, 
node_type*)):
     ... this, new.
     (_Hashtable<>::_M_insert(_Args&&, true_type)): Use latter.
     (_Hashtable<>::_M_emplace(true_type, _Args&&...)): Likewise.
     * 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


[-- Attachment #2: hashtable.patch --]
[-- Type: text/x-patch, Size: 19924 bytes --]

Index: include/bits/hashtable_policy.h
===================================================================
--- include/bits/hashtable_policy.h	(revision 190353)
+++ include/bits/hashtable_policy.h	(working copy)
@@ -577,8 +577,13 @@
       __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::tuple<>());
+	  return __h->_M_insert_unique_node(__n, __code, __p)->second;
+	}
+
       return (__p->_M_v).second;
     }
 
@@ -598,9 +603,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::piecewise_construct,
+				      std::forward_as_tuple(std::move(__k)),
+				      std::tuple<>());
+	  return __h->_M_insert_unique_node(__n, __code, __p)->second;
+	}
+
       return (__p->_M_v).second;
     }
 
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h	(revision 190353)
+++ include/bits/hashtable.h	(working copy)
@@ -584,10 +584,17 @@
       __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 with hash code __code, in bucket bkt if no rehash (assumes
+      // no element with its key already present). Take ownership of the node,
+      // deallocate it on exception.
+      iterator
+      _M_insert_unique_node(size_type __bkt, __hash_code __code,
+			    __node_type* __n);
 
+      // Insert node with hash code __code. Take ownership of the node,
+      // deallocate it on exception.
+      iterator
+      _M_insert_multi_node(__hash_code __code, __node_type* __n);
 
       template<typename... _Args>
 	std::pair<iterator, bool>
@@ -1214,42 +1221,29 @@
       {
 	// First build the node to get access to the hash code
 	__node_type* __node = _M_allocate_node(std::forward<_Args>(__args)...);
+	const key_type& __k = this->_M_extract()(__node->_M_v);
+	__hash_code __code;
 	__try
 	  {
-	    const key_type& __k = this->_M_extract()(__node->_M_v);
-	    __hash_code __code = this->_M_hash_code(__k);
-	    size_type __bkt = _M_bucket_index(__k, __code);
-
-	    if (__node_type* __p = _M_find_node(__bkt, __k, __code))
-	      {
-		// There is already an equivalent node, no insertion
-		_M_deallocate_node(__node);
-		return std::make_pair(iterator(__p), false);
-	      }
-
-	    // We are going to insert this node
-	    this->_M_store_code(__node, __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);
-
-	    if (__do_rehash.first)
-	      {
-		_M_rehash(__do_rehash.second, __saved_state);
-		__bkt = _M_bucket_index(__k, __code);
-	      }
-
-	    _M_insert_bucket_begin(__bkt, __node);
-	    ++_M_element_count;
-	    return std::make_pair(iterator(__node), true);
+	    __code = this->_M_hash_code(__k);
 	  }
 	__catch(...)
 	  {
 	    _M_deallocate_node(__node);
 	    __throw_exception_again;
 	  }
+
+	size_type __bkt = _M_bucket_index(__k, __code);
+	if (__node_type* __p = _M_find_node(__bkt, __k, __code))
+	  {
+	    // There is already an equivalent node, no insertion
+	    _M_deallocate_node(__node);
+	    return std::make_pair(iterator(__p), false);
+	  }
+
+	// Insert the node
+	return std::make_pair(_M_insert_unique_node(__bkt, __code, __node),
+			      true);
       }
 
   template<typename _Key, typename _Value,
@@ -1264,98 +1258,111 @@
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
       _M_emplace(std::false_type, _Args&&... __args)
       {
-	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);
-
 	// First build the node to get its hash code.
 	__node_type* __node = _M_allocate_node(std::forward<_Args>(__args)...);
+
+	__hash_code __code;
 	__try
 	  {
-	    const key_type& __k = this->_M_extract()(__node->_M_v);
-	    __hash_code __code = this->_M_hash_code(__k);
-	    this->_M_store_code(__node, __code);
-
-	    // Second, do rehash if necessary.
-	    if (__do_rehash.first)
-		_M_rehash(__do_rehash.second, __saved_state);
-
-	    // Third, find the node before an equivalent one.
-	    size_type __bkt = _M_bucket_index(__k, __code);
-	    __node_base* __prev = _M_find_before_node(__bkt, __k, __code);
-
-	    if (__prev)
-	      {
-		// Insert after the node before the equivalent one.
-		__node->_M_nxt = __prev->_M_nxt;
-		__prev->_M_nxt = __node;
-	      }
-	    else
-	      // The inserted node has no equivalent in the
-	      // hashtable. We must insert the new node at the
-	      // beginning of the bucket to preserve equivalent
-	      // elements relative positions.
-	      _M_insert_bucket_begin(__bkt, __node);
-	    ++_M_element_count;
-	    return iterator(__node);
+	    __code = this->_M_hash_code(this->_M_extract()(__node->_M_v));
 	  }
 	__catch(...)
 	  {
 	    _M_deallocate_node(__node);
 	    __throw_exception_again;
 	  }
+
+	return _M_insert_multi_node(__code, __node);
       }
 
-  // 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 _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_unique_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,
-						    __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)
+      __try
+	{
+	  if (__do_rehash.first)
+	    {
 	      _M_rehash(__do_rehash.second, __saved_state);
+	      __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v), __code);
+	    }
 
-	    _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;
-	  }
-      }
+	  this->_M_store_code(__node, __code);
 
+	  // Always insert at the begining of the bucket.
+	  _M_insert_bucket_begin(__bkt, __node);
+	  ++_M_element_count;
+	  return iterator(__node);
+	}
+      __catch(...)
+	{
+	  _M_deallocate_node(__node);
+	  __throw_exception_again;
+	}
+    }
+
+  // Insert node, in bucket bkt if no rehash (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>
+    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_multi_node(__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);
+
+      __try
+	{
+	  if (__do_rehash.first)
+	    _M_rehash(__do_rehash.second, __saved_state);
+
+	  this->_M_store_code(__node, __code);
+	  const key_type& __k = this->_M_extract()(__node->_M_v);
+	  size_type __bkt = _M_bucket_index(__k, __code);
+
+	  // Find the node before an equivalent one.
+	  __node_base* __prev = _M_find_before_node(__bkt, __k, __code);
+	  if (__prev)
+	    {
+	      // Insert after the node before the equivalent one.
+	      __node->_M_nxt = __prev->_M_nxt;
+	      __prev->_M_nxt = __node;
+	    }
+	  else
+	    // The inserted node has no equivalent in the
+	    // hashtable. We must insert the new node at the
+	    // beginning of the bucket to preserve equivalent
+	    // elements relative positions.
+	    _M_insert_bucket_begin(__bkt, __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,
@@ -1372,12 +1379,14 @@
       {
 	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));
+	return std::make_pair(_M_insert_unique_node(__bkt, __code, __n), true);
       }
 
   // Insert v unconditionally.
@@ -1393,55 +1402,16 @@
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
       _M_insert(_Arg&& __v, std::false_type)
       {
-	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);
-
-	// First compute the hash code so that we don't do anything if
-	// it throws.
+	// First compute the hash code so that we don't do anything if it
+	// throws.
 	__hash_code __code = this->_M_hash_code(this->_M_extract()(__v));
 
-	__node_type* __node = nullptr;
-	__try
-	  {
-	    // Second allocate new node so that we don't rehash if it 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);
+	// Second allocate new node so that we don't rehash if it throws.
+	__node_type* __node = _M_allocate_node(std::forward<_Arg>(__v));
 
-	    // Third, find the node before an equivalent one.
-	    size_type __bkt = _M_bucket_index(__node);
-	    __node_base* __prev
-	      = _M_find_before_node(__bkt, this->_M_extract()(__node->_M_v),
-				    __code);
-	    if (__prev)
-	      {
-		// Insert after the node before the equivalent one.
-		__node->_M_nxt = __prev->_M_nxt;
-		__prev->_M_nxt = __node;
-	      }
-	    else
-	      // The inserted node has no equivalent in the
-	      // hashtable. We must insert the new node at the
-	      // beginning of the bucket to preserve equivalent
-	      // elements relative positions.
-	      _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;
-	  }
+	return _M_insert_multi_node(__code, __node);
       }
 
-
   template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
Index: include/std/unordered_set
===================================================================
--- include/std/unordered_set	(revision 190353)
+++ 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/std/unordered_map
===================================================================
--- include/std/unordered_map	(revision 190353)
+++ 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: 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,122 @@
+// -*- 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

Re: Value type of map need not be default copyable

[Marc Glisse]

On Wed, 8 Aug 2012, François Dumont wrote:

> 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 ?

You are dealing with a pair<T1,T2> where T1 is const T3.

It is roughly the same issue as before, we end up trying to call a move 
constructor on a const&&.

You probably want your pair constructor to accept T3&&, not T1&&.

-- 
Marc Glisse