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

[Tomasz Kaminski]

On Thu, May 29, 2025 at 4:49 PM Jonathan Wakely <jwakely@redhat.com> wrote:

> On Thu, 29 May 2025 at 15:48, Jonathan Wakely <jwakely@redhat.com> wrote:
> >
> > 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>&);
>
> Or const tuple<const int&, const MyVal&>& or whatever the zipped type is.
>
Actually in [container.reqmts] p42
<https://eel.is/c++draft/containers#container.reqmts-42> we require that:
T  is equality comparable
Which in our case is std::tuple<int, MyVal>, but then we are comparing
std::tuple<int const&, MyVal const&>.
So I think just comparing containers is fine.

>
>
> >
> > 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
> > >>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20250529/d6734d34/attachment.htm>