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

[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?).

[muellerj2]

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).

operator== is defined in terms of std::equal(), and the order of comparison isn't specified for std::equal() as far as I can tell. So I think a program is not allowed to assume that equality comparisons for some iterator pairs aren't performed just because there is an inequivalent iterator pair earlier in the sequence.

However, I think the wording in [container.reqmts]/44 still suggests that keys and values should be compared alternatingly. So are standard-compliant programs allowed to assume this alternation or observe divergence from it?

[CaseyCarter]

It seems to me that the standard wording only specifies the latter ([container.reqmts]/44, [container.opt.reqmts]/4).

However, I think the wording in [container.reqmts]/44 still suggests that keys and values should be compared alternatingly. So are standard-compliant programs allowed to assume this alternation or observe divergence from it?

The fact that both of the cited paragraphs are "Returns" elements is significant. They specify only the value that a function is expected to return, not a means by which that value is to be calculated nor any of the observable effects of doing so. See [structure.specifications]/3.8 which says that it's "a description of the value(s) returned by the function."

We must return the same value as depicted in the Standard, but we may calculate that value in the way we deem to be best for our implementation. (I don't feel bad for anyone that puts incomparable values in a standard container and then tries to compare that container.)

[frederick-vs-ja]

Oh, I'm sorry for forgetting LWG-3410. Is it intended that lexicographical_compare_three_way can also compare more elements than necessary?

If so, I think we can try the strategy that compares key containers first.

[muellerj2]

We must return the same value as depicted in the Standard, but we may calculate that value in the way we deem to be best for our implementation.

Yeah, but this alone is not sufficient for the transformation: If operator== of the keys and and operator== of the values are allowed to interact such that they produce different results on alternation than on non-alternation, then this transformation does not produce the same output.

That said, designing such questionable equality comparators is just asking for trouble, so it's probably not worth thinking much about.

Is it intended that lexicographical_compare_three_way can also compare more elements than necessary?
If so, I think we can try the strategy that compares key containers first.

Yes, it may do more comparisons. But I doubt comparing keys first is worth it in terms of complexity of the implementation and computational runtime.

First, the code transformation is not straightforward. To produce the same result, you would have to compute the index where keys first compare non-equal, then determine the index where values first compare non-equal and finally return the ordering at the smaller of these two indices. So you can't just delegate to lexicographical_compare_three_way because you have to know these indices.

Second, while you can get away with not fully determining the index for the values if it is the larger one, you have to determine the index for keys accurately if you decide to compare the keys first. And that means you might do lots of unnecessary comparisons between keys.

[StephanTLavavej]

We talked about this at the weekly maintainer meeting. We don't believe that the Standard should require us to tolerate non-comparable elements here. (We think the Standard's vagueness supports us here.) As for performance, we expect most equality comparisons to find equality, in which case all keys and all values must be inspected, so separately comparing the keys and then the values is better for locality (for all types) and better for vectorization. For spaceship, @StephanTLavavej thinks this will be uncommon for flat_meow but @CaseyCarter thinks that containers-in-containers are common-ish. However, we would want to see benchmark results comparing the current approach to "compare keys before comparing values" before deciding whether to change the strategy. Comparing keys first could similarly be better for locality and vectorization, but at the cost of more code to determine the spaceship result (since it isn't as simple as equal && equal).

[muellerj2]

While I can't provide a benchmark, here is a back-of-the-envelope calculation how many more (key) comparisons the algorithm separating key and value comparison is expected to do compared to the alternating algorithm (which is optimal in the number of performed comparisons):

Let's assume that comparisons are independent and that the probability that a pair of keys or a pair of values compares different is $p$. The number of value pair comparisons is the same for the alternating and separating algorithms, but they differ in the number of performed key comparisons. Let $X_a$ and $X_s$ respectively be the position of the last pair of keys compared by the alternating or separating algorithm.

For simplicity of calculation, let's also assume that the algorithms are applied to sequences of infinite size. Then $X_a$ and $X_s$ are geometrically distributed. The probability that the current key pair is the last compared one is $1-(1-p)^2$ for the alternating and $p$ for the separating algorithm. Thus, the expected positions of the last compared key pair are $E[X_a] = 1/(1-(1-p)^2)$ and $E[X_s] = 1/p$. That means that the separating algorithm is expected to do $E[X_s]/E[X_a] = 2-p$ times as many comparisons of key pairs as the alternating algorithm, so almost twice as many for small $p$. In total, this means the separating algorithm is expected to do up to 50% more comparisons of keys and values.

(Note that this calculation breaks down for containers of $n$ elements if the probability becomes very small, on the order of $p \in O(1/n)$, since the calculation error due to assuming infinite size is no longer negligible. But the estimate remains good even for asymptotically slightly larger $p$.)