Re: Value type of map need not be default copyable
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 forwardkey_type(__k) with move(__k) compiled fine. You are right, I replaced std::forwardkey_type with std::movekey_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 fdum...@gcc.gnu.org Ollie Wild a...@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
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 fdum...@gcc.gnu.org
Ollie Wild a...@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
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::tupleconst 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);
- templatetypename _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);
templatetypename... _Args
std::pairiterator, 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::pairbool, 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);
}
templatetypename _Key, typename _Value,
Re: Value type of map need not be default copyable
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 forwardkey_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
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 forwardkey_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
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 forwardkey_type(__k) with move(__k) compiled fine.
You are right, I replaced std::forwardkey_type with
std::movekey_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 fdum...@gcc.gnu.org
Ollie Wild a...@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
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);
- templatetypename _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);
templatetypename... _Args
std::pairiterator, 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::pairbool, 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
Re: Value type of map need not be default copyable
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 fdum...@gcc.gnu.org
Ollie Wild a...@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(forwardkey_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.
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);
- templatetypename _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);
templatetypename... _Args
std::pairiterator, 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
-
Re: Value type of map need not be default copyable
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 forwardkey_type(__k) with move(__k) compiled fine. -- Marc Glisse
Re: Value type of map need not be default copyable
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
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
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
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 fdum...@gcc.gnu.org
Ollie Wild a...@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
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::tupleconst 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
Re: Value type of map need not be default copyable
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(forwardkey_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
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(forwardkey_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
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
On 08/08/2012 09:34 AM, Marc Glisse wrote:
On Tue, 7 Aug 2012, Richard Smith wrote:
I've attached a patch for unordered_map which solves the rvalue
reference problem. For efficiency, I've created a new
_M_emplace_bucket method rather than call emplace directly.
I've verified all libstdc++ tests pass (sorry for the previous
oversight) and am running the full GCC test suite now. However, I'd
appreciate any feedback on whether this is a reasonable approach. STL
hacking is way outside my comfort zone. ;-)
If this looks good, I'll take a stab at std::map.
I think you should remove the mapped_type() argument from the call to
_M_emplace_bucket. In C++11, the mapped_type is not required to be
copyable
at all, just to be DefaultInsertable.
Indeed. The reason I was talking about emplace is that you want an
object to be created only at the time the node is created. That might
mean passing piecewise_construct_t and an empty tuple to emplace
(otherwise it is too similar to insert). Or for unordered_map where
the node functions are exposed, you could just create the node
directly without passing through emplace.
This is what I try to do in the attached patch. I replace
_M_insert_bucket with _M_insert_node and use it for operator[]
implementation. I have also introduce a special std::pair constructor
for container usage so that we do not have to include the whole tuple
stuff just for associative container implementations.
However one test is failing:
/home/fdt/dev/gcc/libstdc++-v3/testsuite/23_containers/unordered_map/insert/array_syntax_move.cc:39:18:
required from here
/home/fdt/dev/gcc-build/x86_64-unknown-linux-gnu/libstdc++-v3/include/bits/stl_pair.h:175:42:
error: use of deleted function '__gnu_test::rvalstruct::rvalstruct(const
__gnu_test::rvalstruct)'
: first(std::forward_T1(__x)), second() { }
I don't understand why it doesn't use the move constructor. I can't see
any std::forward call missing. Anyone ?
François
Index: include/bits/hashtable.h
===
--- include/bits/hashtable.h (revision 190209)
+++ include/bits/hashtable.h (working copy)
@@ -584,11 +584,10 @@
__node_base*
_M_get_previous_node(size_type __bkt, __node_base* __n);
- templatetypename _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);
-
templatetypename... _Args
std::pairiterator, 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.
templatetypename _Key, typename _Value,
typename _Alloc, typename _ExtractKey, typename _Equal,
typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
typename _Traits
-templatetypename _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::pairbool, 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::pairbool, 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);
-
Re: Value type of map need not be default copyable
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
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 pairT1,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
Re: Value type of map need not be default copyable
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 fdum...@gcc.gnu.org
Ollie Wild a...@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
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);
- templatetypename _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);
-
templatetypename... _Args
std::pairiterator, 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.
templatetypename _Key, typename _Value,
typename _Alloc, typename _ExtractKey, typename _Equal,
typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
typename _Traits
-templatetypename _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::pairbool, 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::pairbool, 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
Re: Value type of map need not be default copyable
On Sat, Aug 4, 2012 at 10:34 AM, Paolo Carlini paolo.carl...@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 a...@google.com
* include/bits/hashtable.h (_M_emplace_bucket): New function.
* include/bits/hashtable_policy.h (operator[](key_type)): Replace
_M_insert_bucket call with _M_emplace_bucket.
* testsuite/23_containers/unordered_map/operators/2.cc: New test.
commit dd690a5f164326c552c2450af6270ec27e9bfd8e
Author: Ollie Wild a...@google.com
Date: Tue Aug 7 16:34:05 2012 -0500
2012-08-03 Ollie Wild a...@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.carl...@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);
+ templatetypename... _Args
+ iterator
+ _M_emplace_bucket(size_type, __hash_code, _Args... __args);
+
templatetypename... _Args
std::pairiterator, bool
@@ -1356,6 +1360,51 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
}
+ // Insert v in bucket n (assumes no element with its key already present).
+ templatetypename _Key, typename _Value,
+ typename _Alloc, typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+ typename _Traits
+templatetypename... _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::pairbool, 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.
templatetypename _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
Re: Value type of map need not be default copyable
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.carl...@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
On 08/03/2012 05:19 PM, Ollie Wild wrote: On Fri, Aug 3, 2012 at 2:39 AM, Paolo Carlini paolo.carl...@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
.. 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
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::pairconst rvalstruct,rvalstruct V; static_assert(std::is_constructibleV, 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
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::pairconst rvalstruct,rvalstruct V; static_assert(std::is_constructibleV, 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
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
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
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
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
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
On Fri, Aug 3, 2012 at 2:39 AM, Paolo Carlini paolo.carl...@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
Value type of map need not be default copyable
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 a...@google.com
Richard Smith richardsm...@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.
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 000..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::mapint, Mapped m;
+ return m[0];
+}
