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