| Message ID | CAFOgFcR+yDmmWjnjw7txW+3Cgcg+6hEwByPHqrADwHcbEgCdAg@mail.gmail.com |
|---|---|
| State | New |
| Headers | show |
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.
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.
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); +}