[libc++][ranges] implement std::ranges::equal_range
philnik var-const jdoerfert
- Group Reviewers
- rG0f6364b8a100: [libc++][ranges] implement `std::ranges::equal_range`
Why not use __make_projected? Wouldn't this cause a visible change in behavior for the classic algorithm (now accepting a pointer-to-member as the comparator)? (alternatively, you could do a static_assert(__is_callable) like in e.g. lower_bound).
Does this need to be forwarded, or not?
You probably need to pass _Compare explicitly as well, I'm not sure why it wasn't done before (_Compare is normally a reference, so type deduction would decay it to a value).
Why is this cast necessary, and does it work in debug mode? (when _Comp_ref is a struct)
Please don't remove the inlines -- this could increase binary size. We plan to do some investigation and potentially make a dedicated patch to clean up these unwanted inlines.
Do these have to be forwarded as well?
Nit: I know it's a pattern, but perhaps we could rename this? RangeRange looks a little awkward.
Nit: consider s/is in the middle/would be in the middle/.
This can be omitted -- I'll merge the robust_against_dangling patch very soon.
Optional: share this comparator across the two test cases?
You don't have to (and can't really) pass _Compare explicitly. __lower_bound_impl always takes the comparator by reference instead of by value. I don't know why this hasn't been done this way before, but that makes a lot more sense that explicitly passing the template parameter around everywhere.
I think it was done that way to support _Comp_ref resolving to either a reference type (in a regular build) or a non-reference type (in a debug build). Does that not apply here?
That does apply, but why wouldn't you just pass _Comp_ref by reference? The only thing may be that passing it by value is more efficient, but I would expect the functions to be inlined anyways, so it shouldn't matter.
__make_projected cannot be used here because the __comp takes two arguments but we only want to apply __proj to only one of arguments. And tricky thing is sometimes we want to apply __proj for the first argument (see line above) and sometimes we want to apply __proj to the second argument (see few lines below).
It is just much easier to pass in the comp and proj and explicitly write how to apply the projection. I will add static_assert
re "Does this need to be forwarded, or not?"
re pass _Compare explicitly, I agree with @philnik , we shouldn't explicit specify the template argument here and should let it deduced. would decay it to a value is not correct anymore as both functions take arguments by reference.
Actually "explicit specifying the template argument creates problems". My intent of __upper_bound is taking comp by forwarding reference, but explicitly specifying the template arguments makes it pass by rvalue reference. (which triggers some ci failure)
Extra nit nit: make_pair in c++03 does extra copies. since it is similar readability, perhaps just leave it as it is? (the original code on the left uses the constructor)
I added static_cast to fix a CI failure but it was in the wrong place. The problem is the one I explained above. In debug mode, the _Comp_ref is debug_less and the __equal_range deduced _Compare to debug_less . then later, it calls __upper_bound<policy, _Compare>
So we should not really explicit specifying template arguments now as most algorithms takes _Compare by reference (either lvalue reference or forwarding reference). and explicit writing the type can only cause harm.
It was useful in the past because they used to take _Compare by value. But now we are trying our best not to make copies so _Compare are mostly passed by references. If the passing-by-reference causes performance regression, we should revisit all the algorithms. But explicit writing the template argument does not help because you cannot stop them being passed by reference
Here I will just remove the explicit template argument and leave the static_cast. In normal build it does nothing because it casts an l-value to an lvalue reference. In debug mode, it will construct the temporary debug_less struct
Hmm, using an rvalue reference as the argument type looks promising. The _Comp_ref quirk makes things pretty inconvenient, in the future it would be great to clean it up as much as possible without losing the functionality.
@philnik has previously pointed out in one of my patches that this could make the classic algorithm more permissive than mandated by the standard by accepting move-only iterator types. FWIW, I worked around that by adding a static_assert(is_copy_constructible<>::value).
Feel free to address in a follow-up.