Skip to content

<flat_map>: Can we separately compare key and mapped containers? #5075

@frederick-vs-ja

Description

@frederick-vs-ja

Currently, we're implementing flat_(multi)map's comparison operators in inconsistent ways:

STL/stl/inc/flat_map

Lines 769 to 774 in fbe5394

_NODISCARD friend bool operator==(const _Derived& _Left, const _Derived& _Right) {
auto& _Left_base = static_cast<const _Flat_map_base&>(_Left);
auto& _Right_base = static_cast<const _Flat_map_base&>(_Right);
return _RANGES equal(_Left_base._Data.keys, _Right_base._Data.keys)
&& _RANGES equal(_Left_base._Data.values, _Right_base._Data.values);
}

STL/stl/inc/flat_map

Lines 776 to 780 in fbe5394

_NODISCARD friend auto operator<=>(const _Derived& _Left, const _Derived& _Right) {
return _STD lexicographical_compare_three_way(_STD _Get_unwrapped(_Left.cbegin()),
_STD _Get_unwrapped(_Left.cend()), _STD _Get_unwrapped(_Right.cbegin()), _STD _Get_unwrapped(_Right.cend()),
_Synth_three_way{});
}

For operator==, key and mapped containers are compared separately. For operator<=>, they are compared step by step together.

It seems to me that the standard wording only specifies the latter ([container.reqmts]/44, [container.opt.reqmts]/4). The current strategy for operator== possibly incorrectly behaves if the comparison beyond the index of the first inequivalent iterator pair doesn't have well-defined result (i.e. causes UB, terminates, or throws an exception).

E.g. if _Left_base._Data.values[0] != _Right_base._Data.values[0], perhaps we're generally disallowed to compare _Left_base._Data.keys[1] with _Right_base._Data.keys[1].

However, the separately comparing strategy might still be viable if the element types are "well-behaving" enough (e.g. if they are arithmetic types, or possibly string?).

Metadata

Metadata

Assignees

No one assigned

    Labels

    fixedSomething works now, yay!flat_meowC++23 container adaptorsperformanceMust go faster

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions