On 13/06/2024 16:44, Arthur O'Dwyer via Std-Proposals wrote:
> On Thu, Jun 13, 2024 at 11:13 AM Oleksandr Pikozh via Std-Proposals
> <std-proposals_at_[hidden] <mailto:std-proposals_at_[hidden]>>
> wrote:
>
> I was thinking about exactly the same thing long ago (a-la “they did
> great job when designing the std library, how could it be that this
> thing is missing?”). Certainly I needed that more than once for
> production code (of course, I don't remember the details now).
> Happily, since c++14 (and in boost), we can workaround that via
> transparent comparators. Still, it would be certainly an improvement
> (closing the gap) if someone writes the paper and it gets accepted.
> My intuition don't even believes this needs an explicit motivation
> (binary tree index for a composite key [kinda RDBMS terminology
> here, but the idea is true everywhere] should give a possibility to
> search not only by the full key but also by the subkeys a-la
> first-few-attributes-of-the-full-key – by itself, i.e. without
> building additional indices [creating extra maps]), though of course
> my mind understands that the motivation is always needed.
>
> Hmm... This is actually adjacent to a pain point that libc++ has had
> with the associative containers. Consider:
>
> std::multiset<std::string, std::less<>> ms;
> std::set<std::string, std::less<>> s;
> auto r1 = ms.equal_range("ABC"s); // might return 2 or
> more elements, requires two O(lg N) steps
> auto r2 = ms.equal_range("ABC"sv); // might return 2 or
> more elements, requires two O(lg N) steps
> auto r3 = s.equal_range("ABC"s); // always returns 0 or 1
> elements, requires one O(lg N) step plus O(1)
> auto r4 = s.equal_range("ABC"sv); // might(!!) return 2 or more
> elements, requires two O(lg N) steps
>
> Notice that r4 is measurably slower than r3.
> This is because there's no way for the `set` itself to understand that
> the domain of `string_view` is intentionally identical to the domain of
> `string`.

Couldn't this optimization be enabled at least for std::ranges::less as
Compare? Note that std::ranges::less requires totally_ordered_with,
which might imply that the domains are isomorph regarding comparison.

Otherwise I think in general this is a property of Compare, and it
should be exposed by an optional member (or member template for the
argument types) that could opt-in for the isomorphism (or a lesser
requirement that still enables the optimization).

> The STL has to assume that you might be abusing the
> transparent `equal_range` to compute a range of multiple elements,
> simply because /the transparent `equal_range` is the only verb we
> provide for that operation/.
> In 20/20 hindsight, it would have made a lot more sense to provide two
> separate verbs for
> (1) "Give me the range of elements matching this predicate [expressed as
> equivalence to this magic object], /which I guarantee [on pain of UB]
> will all be consecutive/." (Call this "the slow operation.")
> (2) "Give me the 0 or 1 elements that match this specific /value/, which
> I guarantee [on pain of UB] /comes from the same domain/ as your own
> value_type." (Call this "the fast operation.")
>
> It sounds like this `.partition_point` idea is very close to the idea of
> (1). If we could express (1) cleanly with some new verb, then there is a
> (tiny) chance that one day we could change the precondition on
> `set.equal_range` to make it perform the fast operation (2) instead of
> the slow operation (1). Which is what 90% of programmers probably always
> thought it did, anyway.
> (Even some libc++ contributors, at one point! ;))
>
> I do agree that it would make sense to try to get this operation into
> some third-party library (Abseil, Boost, ...) before writing a WG21
> proposal.
> Heck, they might already have it!
> It would also allow you to survey how those non-STL implementations
> currently treat `r4` — do they already treat it as the fast operation?
> If so, do they currently lack a verb for the slow operation? Would the
> addition of your verb actually get them all the way to the idyllic state
> I describe?
>
> I tend to believe that "Multiple third-party libraries already do
> exactly this" is a great argument in favor of WG21 doing the same thing.
> (Admittedly, I believe this /contra/ the visible evidence of P1144,
> which a dozen third-party libraries implement but WG21 shuns. ;))
>
> –Arthur
>