[Bug libstdc++/115285] [12/13/14/15 Regression] std::unordered_set can have duplicate value

[Jonathan Wakely]

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); }
>
>-      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)
>diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
>index 5d79e2ba26f..f35eb7ddb43 100644
>--- a/libstdc++-v3/include/bits/hashtable_policy.h
>+++ b/libstdc++-v3/include/bits/hashtable_policy.h
>@@ -141,6 +141,11 @@ namespace __detail
> 	operator()(std::pair<_Kt, _Val>&& __x) const noexcept
> 	{ return std::move(__x); }
>
>+      template<typename _Kt, typename _Val>
>+	constexpr std::pair<_Kt, _Val>&
>+	operator()(std::pair<_Kt, _Val>& __x) const noexcept
>+	{ return __x; }
>+

This overload is not sufficient:

struct Pair
{
   explicit operator std::pair<const K, int>() const&&
   { return {K(1), 2}; }
};

int main()
{
   Pair p2[1];
   std::unordered_map<K, int> um(std::make_move_iterator(p2),
                                 std::make_move_iterator(p2+1));
}


>       template<typename _Kt, typename _Val>
> 	constexpr const std::pair<_Kt, _Val>&
> 	operator()(const std::pair<_Kt, _Val>& __x) const noexcept
>diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc
>index bc2f093f47c..59e1ad12401 100644
>--- a/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc
>+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc
>@@ -244,7 +244,7 @@ test03()
>     VERIFY( us.size() == 1 );
>
>     VERIFY( __gnu_test::counter::count() == origin + increments );
>-    VERIFY( __gnu_test::counter::get()._M_increments == increments + 1 );
>+    VERIFY( __gnu_test::counter::get()._M_increments == increments );
>   }
>   VERIFY( __gnu_test::counter::count() == origin );
>