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