`<flat_map>`: `count()`, `contains()`, and `equal_range()` are doing too much work

[StephanTLavavej]

(Vojtěch Michal (@vmichal)'s #5987 is changing this code, but the issue is pre-existing and orthogonal. Update these citations after merging that PR.)

STL/stl/inc/flat_map

Lines 1124 to 1134 in 18e1eb5

	template <class _KeyTy>
	_NODISCARD size_type _Count(const _KeyTy& _Key_val) const {
	_STL_INTERNAL_STATIC_ASSERT(is_same_v<_KeyTy, key_type> || _Transparent<key_compare>);
	return upper_bound(_Key_val) - lower_bound(_Key_val);
	}
	template <class _KeyTy>
	_NODISCARD bool _Contains(const _KeyTy& _Key_val) const {
	_STL_INTERNAL_STATIC_ASSERT(is_same_v<_KeyTy, key_type> || _Transparent<key_compare>);
	return find(_Key_val) != cend();
	}

STL/stl/inc/flat_map

Lines 1194 to 1198 in 18e1eb5

	template <class _KeyTy>
	_NODISCARD pair<iterator, iterator> _Equal_range(const _KeyTy& _Key_val) {
	_STL_INTERNAL_STATIC_ASSERT(is_same_v<_KeyTy, key_type> || _Transparent<key_compare>);
	return {lower_bound(_Key_val), upper_bound(_Key_val)};
	}

First, the implementations of count() and contains() are forming full key-value iterators, but they only need to care about the keys.

Second, count() and equal_range() are calling lower_bound() and upper_bound() independently, which performs two binary searches to get to the same general region. Going through ranges::equal_range would perform less work.

Third, count() should probably be optimized for non-multi flat_map, as it becomes morally equivalent to contains().

[vmichal]

Agreed, I thought about the extra work done by _Equal_range, but I was not sure it is something worth hunting.
I can look into it, provided you want to see it resolved.

[StephanTLavavej]

Yes, that would be great. IMO the binary search stuff is 100% the reason that flat_meow exists so it should be efficient.

[frederick-vs-ja]

Going through ranges::equal_range would perform less work.

ranges::equal_range seems overconstrained currently (see also LWG-4239), so I think we might need to use std::equal_range.

Third, count() should probably be optimized for non-multi flat_map, as it becomes morally equivalent to contains().

I think this isn't true for cases for transparent comparison. Perhaps we should restrict the optimization to cases where is_same_v<_KeyTy, key_type> is true.

[StephanTLavavej]

I think this isn't true for cases for transparent comparison.

Hmm, I think you're correct.

[vmichal]

Quick off-topic: It always pains me to see a paper say "there is a correct solution, but all required paperwork would take too long, so here's a quick patch for you" :'(

Nevertheless, to the topic: A. Jiang (@frederick-vs-ja) I beg to differ

I think this isn't true for cases for transparent comparison. Perhaps we should restrict the optimization to cases where is_same_v<_KeyTy, key_type> is true.

TLDR: !comp(a, b) && !comp(b, a) must be an equivalence relation ([associative.reqmts.general]/3), so non_multi_cont.count(key) can never return more than 1. Please correct me if I am wrong.

Supporting argument:
My understanding based on [associative.reqmts.general]/2 and 3 is that the comp object must induce a strict weak ordering on keys and the relation equiv(a, b) must be an equivalence relation on keys. By definition, equiv(a, b) = !comp(a, b) && !comp(b, a), so it is obviously symmetric. Additionally, it is transitive (required by the mathematical definition of an equivalence relation, but also supported by paragraph [alg.sorting.general]/4).

Now, suppose we have a non-multi container with two keys k1 and k2 such that comp(k1, k2) and we want to count the number of elements in this container equivalent to some generic key x. Suppose both k1 and k2 are both equivalent to x, so equiv(k1, x) && equiv(k2, x) holds. From the symmetry of equiv, we get that equiv(x, k2) holds. From the transitivity of equiv, we get that equiv(k1, k2) holds, but that is in direct contradiction to the assumption of comp(k1, k2).

So either the assumption comp(k1, k2) is wrong, in which case the container implementation is wrong, as it allowed the existence of two equivalent elements in a non-multi container.
Or the comp object provided by the user is not valid since it does not induce an equivalence relation equiv.
Either way, I don't see a valid way for non_multi_cont.count(x) to ever return more than 1.

[vmichal]

Other than that, regarding your comment

ranges::equal_range seems overconstrained currently (see also LWG-4239), so I think we might need to use std::equal_range.

The overconstrained problem in our case impacts not only ranges::equal_range, but also ranges::upper_bound, ranges::lower_bound, and ranges::binary_search; others (e.g. ranges::is_sorted_until) are not called with some user-provided generic key, so I guess they are ok. To be correct, we would have to replace all occurrences that could cause problems, right?

However, is that something we want to do now? Currently, although MSVC warns about array < array, such expression would never appear in our implementation, so the only problem would be a failing constrained, which is not the case, as shown by the example below. I personally prefer ranges:: algorithms, so I would consider using them, as it does not seem impossible that some other resolution will appear in the future.

    flat_map<string, int, less<>> m;
    m.try_emplace("abc", 5);
    using v = vector<int[3]>;
    static_assert(indirect_strict_weak_order<ranges::less, v::iterator, v::iterator>);
    using x = int[2];
    static_assert(strict_weak_order<ranges::less, x, x>);
    static_assert(strict_weak_order<ranges::less, char[3], char[3]>);
    static_assert(relation<ranges::less, char[3], char[3]>);
    static_assert(predicate<ranges::less, char[3], char[3]>);
    static_assert(regular_invocable<ranges::less, char[3], char[3]>);
    static_assert(invocable<ranges::less, char[3], char[3]>);

BTW there is currently only 1 call to ranges:: algorithms in <flat_set> and about 20 in <flat_map>, so I have no problem replacing them, if you say so.

[frederick-vs-ja]

Now, suppose we have a non-multi container with two keys k1 and k2 such that comp(k1, k2) and we want to count the number of elements in this container equivalent to some generic key x. Suppose both k1 and k2 are both equivalent to x, so equiv(k1, x) && equiv(k2, x) holds. From the symmetry of equiv, we get that equiv(x, k2) holds. From the transitivity of equiv, we get that equiv(k1, k2) holds, but that is in direct contradiction to the assumption of comp(k1, k2).

It doesn't seem to me that the whether the derived equivalence relation is also required for x whose type is not key_type.

Per [associative.reqmts.general]/7.22, it's only required that "the container is partitioned with respect to c(x, ke) and !c(ke, x), with c(x, ke) implying !c(ke, x)". So the following example should be valid.

#include <set>
#include <type_traits>
#include <print>

enum class E {};

struct divless {
    using is_transparent = void;

    template<class X, class Y>
        requires (std::is_same_v<X, int> && std::is_same_v<Y, E>)
              || (std::is_same_v<X, E> && std::is_same_v<Y, int>)
              || (std::is_same_v<X, int> && std::is_same_v<Y, int>)
    constexpr bool operator()(X x, Y y) const noexcept {
        if constexpr (std::is_same_v<X, E>) {
            return static_cast<int>(x) < y / 10;
        } else if constexpr (std::is_same_v<Y, E>) {
            return x / 10 < static_cast<int>(y);
        } else {
            return x < y;
        }
    }
};

int main() {
    std::set<int, divless> s1{1, 2, 11, 12};
    const auto n1 = s1.count(E{0});
    std::multiset<int, divless> s2{1, 2, 11, 12};
    const auto n2 = s2.count(E{0});

    std::println("n1 = {}; n2 = {}", n1, n2);
}

And implementations seemingly behave correctly. Godbolt link

Currently, although MSVC warns about array < array, such expression would never appear in our implementation, so the only problem would be a failing constrained, which is not the case, as shown by the example below.

operator</operator> are not the only cases we need to consider. IIUC the standard allows a user-provided comparator to reject comparing c(ke, ke).

[vmichal]

It doesn't seem to me that the whether the derived equivalence relation is also required for x whose type is not key_type.

So you suggest that based on https://eel.is/c++draft/associative.reqmts#general-2.sentence-1, comp(a, b) is only required to have nice properties for a, b keys from the container, but not when at least one of them is generic ke? Well, I don't have a strong formal counterargument, but it feels to be against the intent... But I admit I don't understand the intent of https://eel.is/c++draft/algorithms#alg.sorting.general-3.sentence-3 ...

I'm no expert, I'm just a dude who wants to help, so I'll do as you recommend. So apply optimizations only when _IsUnique && is_same_v<key_type, _Other>, right?

[vmichal]

And regarding your second point:

operator</operator> are not the only cases we need to consider. IIUC the standard allows a user-provided comparator to reject comparing c(ke, ke)

Understood, so until someone fixes the indirect_strict_weak_ordering constraint on Compare for ranges::lower_bound and friends, they are off the table in places where the user can provide some evil generic ke.
Would you like me to replace only calls that use a user-provided generic key, or all of them for consistency?

[vmichal]

I have implemented both A. Jiang (@frederick-vs-ja) 's suggestions, they are now in the linked PR.