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