Add std::unordered_* C++11 allocator support

[François Dumont]

Hi

     Here is another proposal with:
- No attempt to remove const key
- No attempt to use assignment operator
- noexcept move constructor; I slightly modify a static assertion so 
that it checks that _M_bucket_index is noexcept qualified which depends 
on the noexcept qualification of the functors involved in bucket computation

2013-04-21  François Dumont  <fdumont@gcc.gnu.org>

     * include/bits/hashtable_policy.h: Add C++11 allocator support.
     * include/bits/hashtable.h: Likewise.
     * include/bits/unordered_set.h: Likewise.
     * include/bits/unordered_map.h: Likewise.
     * include/debug/unordered_set: Likewise.
     * include/debug/unordered_map: Likewise.
     * include/std/unordered_set: Remove bits/algobase.h
     include. Replace bits/alloc_traits.h by ext/alloc_traits.h.
     * include/std/unordered_map: Likewise.
     * testsuite/util/testsuite_counter_type.h: Add count of destructors.
     * testsuite/23_containers/unordered_set/
     not_default_constructible_hash_neg.cc: Adjust dg-error line number.
     * testsuite/23_containers/unordered_set/instantiation_neg.cc: Likewise.
     * testsuite/23_containers/unordered_set/allocator/copy.cc: New.
     * testsuite/23_containers/unordered_set/allocator/copy_assign.cc: New.
     * testsuite/23_containers/unordered_set/allocator/minimal.cc: New.
     * testsuite/23_containers/unordered_set/allocator/move_assign.cc: New.
     * testsuite/23_containers/unordered_set/allocator/noexcept.cc: New.
     * testsuite/23_containers/unordered_set/allocator/swap.cc: New.
     * testsuite/23_containers/unordered_multiset/allocator/copy.cc: New.
     * testsuite/23_containers/unordered_multiset/allocator/copy_assign.cc:
     New.
     * testsuite/23_containers/unordered_multiset/allocator/minimal.cc: New.
     * testsuite/23_containers/unordered_multiset/allocator/move_assign.cc:
     New.
     * testsuite/23_containers/unordered_multiset/allocator/noexcept.cc: 
New.
     * testsuite/23_containers/unordered_multiset/allocator/swap.cc: New.
     * testsuite/23_containers/unordered_map/allocator/copy.cc: New.
     * testsuite/23_containers/unordered_map/allocator/copy_assign.cc: New.
     * testsuite/23_containers/unordered_map/allocator/minimal.cc: New.
     * testsuite/23_containers/unordered_map/allocator/move_assign.cc: New.
     * testsuite/23_containers/unordered_map/allocator/noexcept.cc:
     New.
     * testsuite/23_containers/unordered_map/allocator/swap.cc: New.
     * testsuite/23_containers/unordered_multimap/allocator/copy.cc: New.
     * testsuite/23_containers/unordered_multimap/allocator/copy_assign.cc:
     New.
     * testsuite/23_containers/unordered_multimap/allocator/minimal.cc: New.
     * testsuite/23_containers/unordered_multimap/allocator/move_assign.cc:
     New.
     * testsuite/23_containers/unordered_multimap/allocator/noexcept.cc: 
New.
     * testsuite/23_containers/unordered_multimap/allocator/swap.cc: New.

Tested under Linux x86_64.

Ok to commit ?

François


On 04/08/2013 10:24 AM, Jonathan Wakely wrote:
> On 6 April 2013 19:53, Jonathan Wakely wrote:
>> I'm not very comfortable with the "mutable value type" part which
>> accesses the stored value through a pointer to a different type. This
>> violates strict aliasing rules and would also give the wrong result if
>> users provide an explicit specialization of std::pair<int, Foo> which
>> stores pair::second before pair::first, then tries to store that type
>> in an unordered_map.  When a pair<const int, Foo>* is cast to
>> pair<int, Foo>* the user's explicit specialization would not be used
>> and the layout would be wrong.  Would it be possible to separate the
>> C++11 allocator support from the new feature that attempts to reuse
>> existing nodes?  Or maybe remove the mutable value type stuff so that
>> nodes can be reused for unordered sets but not unordered maps?
> For a non-assignable value_type we can reuse the node (but not the
> value_type) by destroying and constructing a new value_type in place:
>
>        __node_type*
>        operator()(const __node_type* __n) const
>        {
>      if (_M_nodes)
>        {
>          __node_type* __node = _M_nodes;
>          allocator_traits<A>::destroy(a, __node->_M_valptr());
>          __try {
>            allocator_traits<A>::construct(a, __node->_M_valptr(),
> *__n->_M_valptr());
>            // Construction didn't throw, we can unlink the node.
>            _M_nodes = _M_nodes->_M_next();
>            __node->_M_nxt = nullptr;
>            return __node;
>          } __catch (...) {
>            // TODO deallocate node
>            __throw_exception_again;
>          }
>        }
>      return _M_h._M_allocate_node(__n->_M_v());
>        }
>
> This can be much less efficient than assignment if the value_type has
> its own allocated memory, but I don't see any alternative. Casting
> pair<const A,B>& to pair<A,B>& is not an option.
>
> N.B. the code above
>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: unordered_alloc.patch
Type: text/x-patch
Size: 150628 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20130421/2ad83b6b/attachment.bin>