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