[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