[PATCH] libstdc++: Compare keys and values separately in flat_map::operator==

[Jonathan Wakely]

On Thu, 29 May 2025 at 15:42, Tomasz Kaminski <tkaminsk@redhat.com> wrote:
>
>
>
> On Thu, May 29, 2025 at 3:56 PM Patrick Palka <ppalka@redhat.com> wrote:
>>
>> Tested on x86_64-pc-linux-gnu, does this look OK for trunk/15?
>>
>> -- >8 --
>>
>> Instead of effectively doing a zipped comparison of the keys and values,
>> compare them separately to leverage the underlying containers' optimized
>> equality implementations.
>>
>> libstdc++-v3/ChangeLog:
>>
>>         * include/std/flat_map (_Flat_map_impl::operator==): Compare
>>         keys and values separately.
>> ---
>>  libstdc++-v3/include/std/flat_map | 5 ++++-
>>  1 file changed, 4 insertions(+), 1 deletion(-)
>>
>> diff --git a/libstdc++-v3/include/std/flat_map b/libstdc++-v3/include/std/flat_map
>> index c0716d12412a..134307324190 100644
>> --- a/libstdc++-v3/include/std/flat_map
>> +++ b/libstdc++-v3/include/std/flat_map
>> @@ -873,7 +873,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>        [[nodiscard]]
>>        friend bool
>>        operator==(const _Derived& __x, const _Derived& __y)
>> -      { return std::equal(__x.begin(), __x.end(), __y.begin(), __y.end()); }
>> +      {
>> +       return __x._M_cont.keys == __y._M_cont.keys
>> +         && __x._M_cont.values == __y._M_cont.values;
>
> Previously we supported containers that do not have operator==, by calling equal.

Oh, good point.
Using == means the element types of the underlying containers must be
equality comparable, but the original approach of using std::equal on
the zipped values only means those tuples must be equality comparable,
and an evil user could have overloaded:

bool operator==(const tuple<int, MyVal>&, const tuple<int, MyVal>&);

so that those comparisons work, but MyVal might not be equality comparable.

> For the flat_set we also do not compare the containers. I would suggest using in both:
>   ranges::equal(x._M_cont)
> Or using == on containers in both flat_map and flat_set.
>>
>> +      }
>>
>>        template<typename _Up = value_type>
>>         [[nodiscard]]
>> --
>> 2.50.0.rc0
>>