[Bug libstdc++/115285] [12/13/14/15 Regression] std::unordered_set can have duplicate value
Jonathan Wakely
jwakely@redhat.com
Fri Nov 1 21:25:35 GMT 2024
On 31/10/24 19:19 +0000, Jonathan Wakely wrote:
>On 31/10/24 19:16 +0000, Jonathan Wakely wrote:
>>On 31/10/24 19:11 +0000, Jonathan Wakely wrote:
>>>On 31/10/24 10:38 +0000, Jonathan Wakely wrote:
>>>>On 28/10/24 21:51 +0100, François Dumont wrote:
>>>>>
>>>>>>On 24/10/2024 21:49, Jonathan Wakely wrote:
>>>>>>>On Thu, 24 Oct 2024 at 19:43, François Dumont<frs.dumont@gmail.com> wrote:
>>>>>>>>Committed as trivial the attached patch.
>>>>>>>>
>>>>>>>> libstdc++: Fix test broken when using COW std::string
>>>>>>>>
>>>>>>>> libstdc++-v3/ChangeLog:
>>>>>>>>
>>>>>>>> * testsuite/23_containers/unordered_map/96088.cc (test03):
>>>>>>>Thanks! I think it was affecting the unordered_set test too.
>>>>>>>
>>>>>Hi
>>>>>
>>>>>This was indeed revealing a problem in my attempt to fix this bug.
>>>>>
>>>>>Here is the complete patch that I will backport if validated.
>>>>>
>>>>>libstdc++: [_Hashtable] Avoid temporaries when inserting existing key
>>>>>
>>>>>Following PR 115285 fix, the hashtable _S_forward_key
>>>>>responsible for finding
>>>>>the best way to transmit the key part of the argument parameter to the hash
>>>>>functor was modified to return a key_type instance for any
>>>>>argument type. Only
>>>>>the overloads for const key_type& and key_type&& were still
>>>>>preventing a key_type
>>>>>instanciation.
>>>>>
>>>>>It revealed that a overload for key_type& was missing. To fix
>>>>>this problem we now
>>>>>deal with all sort of key_type of reference type in the unique
>>>>>_S_forward_key static
>>>>>method and remove the overloads. When decayed type of the
>>>>>input instance is the same
>>>>>as key_type we avoid the instanciation. Note that for the
>>>>>comparison we also decay
>>>>>key_type to properly managed when unordered container is
>>>>>instantiated with a const
>>>>>type.
>>>>>
>>>>>libstdc++-v3/ChangeLog:
>>>>>
>>>>> * include/bits/hashtable_policy.h
>>>>> (_ConvertToValueType<_Select1st,
>>>>>_Value>::operator(std::pair<>&)): New,
>>>>> allow consistent behavior with
>>>>>_ConvertToValueType<_Identity, _Value>.
>>>>> * include/bits/hashtable.h
>>>>> (_S_forward_key<_Kt>(_Kt&&)): Adapt to return _Kt&&
>>>>>when decayed _Kt is
>>>>> key_type, return a new key_type instance otherwise.
>>>>> (_S_forward_key(const key_type&)): Remove.
>>>>> (_S_forward_key(key_type&&)): Remove.
>>>>> * testsuite/23_containers/unordered_set/96088.cc
>>>>>(test03): Adapt expected
>>>>> allocation increment.
>>>>>
>>>>>Tested under linux x64, both std::string abi.
>>>>>
>>>>>Ok to commit ?
>>>>>
>>>>>François
>>>>
>>>>>diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
>>>>>index f1a5490b5ff..8324e75aefd 100644
>>>>>--- a/libstdc++-v3/include/bits/hashtable.h
>>>>>+++ b/libstdc++-v3/include/bits/hashtable.h
>>>>>@@ -930,18 +930,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>>>> _M_insert_unique(_Kt&&, _Arg&&, _NodeGenerator&);
>>>>>
>>>>> template<typename _Kt>
>>>>>- key_type
>>>>>+ static __conditional_t<std::is_same<__decay_t<_Kt>,
>>>>>+ __decay_t<key_type>>::value,
>>>>>+ _Kt&&, key_type>
>>>>> _S_forward_key(_Kt&& __k)
>>>>> { return std::forward<_Kt>(__k); }
>>>>
>>>>Does this assume that __k is implicitly convertible to key_type?
>>>>
>>>>e.g. if Kt is int and the key_type(int) constructor is explicit?
>>>
>>>Yes, this fails, and I think it should compile:
>>>
>>>#include <unordered_set>
>>>
>>>struct K {
>>>explicit K(int) noexcept { }
>>>bool operator==(const K&) const { return true; }
>>>};
>>>
>>>template<> struct std::hash<K> {
>>>auto operator()(const K&) const { return 0ul; }
>>>};
>>>
>>>int main()
>>>{
>>>int i[1]{};
>>>std::unordered_set<K> s(i, i);
>>>}
>>>
>>>
>>>>Does it need to be something like:
>>>>
>>>>template<typename _Kt>
>>>>static __conditional_t<is_same<const _Kt&, const key_type&>::value,
>>>> _Kt&&, key_type>
>>>>_S_forward_key(_Kt&& __k)
>>>>{
>>>> using type = __conditional_t<is_same<const _Kt&, const key_type&>::value,
>>>> _Kt&&, key_type>
>>>> return static_cast<type>(__k);
>>>>}
>>>>
>>>>?
>>
>>Can we just remove _S_forward_key and use static_cast directly?
>>
>>
>>--- a/libstdc++-v3/include/bits/hashtable.h
>>+++ b/libstdc++-v3/include/bits/hashtable.h
>>@@ -929,26 +929,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>> std::pair<iterator, bool>
>> _M_insert_unique(_Kt&&, _Arg&&, _NodeGenerator&);
>>- template<typename _Kt>
>>- key_type
>>- _S_forward_key(_Kt&& __k)
>>- { return std::forward<_Kt>(__k); }
>>-
>>- static const key_type&
>>- _S_forward_key(const key_type& __k)
>>- { return __k; }
>>-
>>- static key_type&&
>>- _S_forward_key(key_type&& __k)
>>- { return std::move(__k); }
>>-
>> template<typename _Arg, typename _NodeGenerator>
>> std::pair<iterator, bool>
>> _M_insert_unique_aux(_Arg&& __arg, _NodeGenerator& __node_gen)
>> {
>
>Adding this comment here would be useful:
>
> // If _ExtractKey{}(__arg) is already a reference to key_type,
> // forward it unchanged. Otherwise, construct a key_type from it.
I decided that maybe the best way to fix the bugs was just to remove
all those problematic code, and implement all insert members in terms
of emplace. That turned into a big refactoring:
https://forge.sourceware.org/gcc/gcc-TEST/pulls/15
More information about the Libstdc++
mailing list