Inconsistencies with associative/unordered containers

Jonathan Wakely jwakely@redhat.com
Wed Jul 1 20:50:53 GMT 2020


On 01/07/20 22:20 +0200, François Dumont wrote:
>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.

I'll try to review the series tomorrow. Thanks for the reminder.

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