Inconsistencies with associative/unordered containers

François Dumont frs.dumont@gmail.com
Wed Jul 1 20:20:00 GMT 2020


On 01/07/20 9:20 pm, Jonathan Wakely wrote:
> On 01/07/20 19:10 +0300, Никита Байков wrote:
>> Hello,
>>
>> I'm trying to make sense of associative and unordered containers' 
>> behavior. Some of the implementation details seem a little 
>> inconsistent to me. Could you please take a look?
>>
>> Most of my questions concern move constructors and assignments, and 
>> their noexcept specifications. To be more specific, let me list some 
>> examples.
>>
>> 1. Move constructor for unordered_set is explicitly defaulted on its 
>> first declaration:
>>
>>    /// Move constructor.
>>    unordered_set(unordered_set&&) = default;
>>
>> Since unordered_set has no base classes and has just one data member 
>> of type _Hashtable, its noexcept specification would be derived from 
>> the following:
>>
>>   template<typename _Key, typename _Value,
>>        typename _Alloc, typename _ExtractKey, typename _Equal,
>>        typename _H1, typename _H2, typename _Hash, typename 
>> _RehashPolicy,
>>        typename _Traits>
>>     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
>>            _H1, _H2, _Hash, _RehashPolicy, _Traits>::
>>     _Hashtable(_Hashtable&& __ht) noexcept
>>     : __hashtable_base(__ht),
>>    /* ... the of the initializer list and the constructor body */
>>
>> This move constructor is marked noexcept unconditionally despite the 
>> fact it has to copy hash function _H1 and function _Equal that 
>> compares the keys.
>
> Looks like a bug. It was introduced by
> https://gcc.gnu.org/g:0462b6aa20fd6734f7497f5eed9496d33701a952
>
> This program exited normally with GCC 4.8 and terminates since 4.9.0:
>
> #include <unordered_set>
>
> bool boom = false;
>
> struct Eq : std::equal_to<int>
> {
>   Eq() { }
>   Eq(const Eq&) { if (boom) throw 1; }
> };
>   int main()
> {
>   std::unordered_set<int, std::hash<int>, Eq> s;
>   try {
>     boom = true;
>     auto s2 = std::move(s);
>   } catch (int) {
>   }
> }
>
I had notice this one and submitted a patch as part of a series:

https://gcc.gnu.org/pipermail/libstdc++/2019-November/049597.html

I would prefer to commit in the submitted order but if you wish I can 
reorder those.

>
>> At the same time, its move assignment operator is also explicitly 
>> defaulted:
>>
>>    /// Move assignment operator
>>    unordered_set&
>>    operator=(unordered_set&&) = default;
>>
>> and therefore is conditionally noexcept, since the corresponding 
>> _Hashtable::operator= is declared as
>>
>> _Hashtable&
>>       operator=(_Hashtable&& __ht)
>> noexcept(__node_alloc_traits::_S_nothrow_move()
>>            && is_nothrow_move_assignable<_H1>::value
>>            && is_nothrow_move_assignable<_Equal>::value);
>>
>> So, the first question is why the copy assignment of _H1 and _Equal 
>> is considered to never throw, while the move assignment is not. As a 
>> side 
>
> Looks like a bug.
>
>> question, why does the move constructor choose to copy _H1 and _Equal 
>> instead of moving them?
>
> Howard Hinnant asked me about that recently, because we do the same
> for maps and sets as well as for unordered maps and sets.
>
> It's probably wrong, but I don't really want to change it until
> https://cplusplus.github.io/LWG/issue2227 is resolved.
>
>> 2. Let's assume that there is nothing wrong with noexcept 
>> specifications in unordered containers, i.e., all constructors and 
>> assignment operators are marked noexcept as they ought to be. Why 
>> then are the associative containers not implemented the same way? As 
>> far as I can see in bits/stl_set.h and bits/stl_tree.h,
>>
>>    //  Move constructor
>>    set(set&&) = default;
>>
>>    // The only data member of set is _Rb_tree object, whose move 
>> constructor is explicitly defaulted
>>    _Rb_tree(_Rb_tree&&) = default;
>>
>>    // The only data member of _Rb_tree is _Rb_tree_impl<_Compare> 
>> object that is defined as
>>    template<typename _Key_compare,
>>          bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)>
>>       struct _Rb_tree_impl
>>       : public _Node_allocator
>>       , public _Rb_tree_key_compare<_Key_compare>
>>       , public _Rb_tree_header
>>      {
>>       _Rb_tree_impl() = default;
>>       _Rb_tree_impl(_Rb_tree_impl&&) = default;
>>
>>      /* the rest of the definition */
>>      };
>>
>>    // Finally, _Rb_tree_key_compare move constructor is defined as
>>    _Rb_tree_key_compare(_Rb_tree_key_compare&& __x)
>> noexcept(is_nothrow_copy_constructible<_Key_compare>::value)
>>       : _M_key_compare(__x._M_key_compare)
>>       { }
>>
>> What is the difference between _Compare (for associative containers) 
>> and _Equal (for unordered containers) in regard to noexcept? Why we 
>
> One is correct and the other isn't.
>
>> have to check is_nothrow_copy_constructible value in the case of 
>> _Compare but can ignore it in the case of _Equal?
>>
>>
>> 3. The move constructor declaration and the allocator-extended move 
>> constructor declaration for std::set result into different noexcept 
>> specifications. Isn't that a small defect of the class interface?
>>
>>    /// Allocator-extended move constructor.
>>    set(set&& __x, const allocator_type& __a)
>> noexcept(is_nothrow_copy_constructible<_Compare>::value
>>         && _Alloc_traits::_S_always_equal())
>>    : _M_t(std::move(__x._M_t), _Key_alloc_type(__a)) { }
>>
>>    /// Move constructor
>>    set(set&&) = default;
>>
>> Given the declarations above, I reckon that noexcept specification of 
>> the explicitly defaulted constructor can be rewritten as
>>
>>    is_nothrow_copy_constructible<_Compare>::value && 
>> is_nothrow_move_constructible</*type of the rebinded allocator*/>::value
>
> Allocators aren't allowed to throw when copied or moved, so the
> is_nothrow_move_constructible check is not needed. The fact it's
> implied by the defaulted constructor does seem like a bug.
>
>> Let's say someone defined a custom empty allocator type but didn't 
>> mark its move constructor as noexcept (besides the fact that move 
>> constructors shall never throw). noexcept conditions evaluation 
>> yields different results.
>
> They should fix their allocator. Explicitly providing a move
> constructor for an allocator is silly anyway. Don't do that. If you
> insist on it, get the exception specification right.
>
>> P.S. Sorry if this is an inappropriate place to ask these questions. 
>> Since I am not truly convinced that any of these is a bug (more 
>> likely a kind of GCC's extension to the standard), I decided to not 
>> post them on the bug tracker. Hope that you would suggest the proper 
>> place then.
>
> Please do report it to bugzilla, because the assertion in the code
> below used to pass, but fails since GCC 7.1.0, due to the changes in
> https://gcc.gnu.org/g:a4dec0d6de97348e71932f7080fe4a3bb8730096
>
> #include <set>
>
> template<typename T>
> struct Alloc
> {
>   using value_type = T;
>
>   Alloc() { }
>   Alloc(const Alloc&) { }
>   template<typename U>
>     Alloc(const Alloc<U>&) { }
>
>   T* allocate(std::size_t n)
>   { return std::allocator<T>().allocate(n); }
>
>   void deallocate(T* p, std::size_t n)
>   { std::allocator<T>().deallocate(p, n); }
> };
>
> static_assert( std::is_nothrow_move_constructible<std::set<int, 
> std::less<>, Alloc<int>>>::value, "" );
>
>
> François, could you please take a look?
>
>
Yes, sure.



More information about the Libstdc++ mailing list