reused classic std::set_difference
added unit tests
philnik ldionne var-const jdoerfert
- Group Reviewers
- rG1cdec6c96e85: [libcxx][ranges] implement `std::ranges::set_difference`
Looks pretty good overall, the only substantial comment is about avoid observable changes in behavior in the classic set_difference algorithm. Thanks for working on this!
Please add a link to this patch.
Nit: unnecessary std::.
Nit: unnecessary (I think) space. Is this done by clang-format? If yes, it's not worth changing.
Does using decay here lead to any observable difference?
Wouldn't using invoke here create an observable change in behavior for the classic algorithm? It seems like it would cause e.g. passing a pointer to member to work with the classic algorithm which wasn't the case before.
Instead, I would strongly recommend the following trick: in the range algorithm, create a lambda that wraps the comparator and the projection functors and pass it as the comparator. It also avoids the need to pass the projections directly. See e.g. ranges_sort.h:
auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); std::__sort_impl(std::move(__first), __last_iter, __projected_comp);
Optional: you can also s/_LIBCPP_INLINE_VISIBILITY/_LIBCPP_HIDE_FROM_ABI/ since you're changing this line anyway. _LIBCPP_HIDE_FROM_ABI is the newer name for the same macro (we use it in new code and IMO it's good to update the old code to use the new name when opportunity arises).
Ultranit: qualify std:: for consistency?
Can you also check the case when the lengths are the same (but the elements are different)?
Nit: the test case doesn't seem to check borrowed_range, so remove that part of the comment?
Nit: probably needs renaming for consistency with the merge test.
Question: does cpp17_input_iterator not work? If yes, can you add a short comment indicating why it doesn't work, to make it clear it wasn't forgotten but deliberately omitted?
Since this class is already used here and in merge test, and will likely be used more in further tests, it should probably be moved into a shared header with helpers.
The algorithm requires the input to be std::input_iterator which is a c++ 20 concept. cpp_17_input_iterator might or might not work, depending on whether or not it models C++20 input_iterator concept.
IMO it doesn't add too much in the test, and at the same time it couples the test to the implementation of cpp_17_input_iterator. Whether or not model c++ 20's input_iterator might change for that particular class.
If we really want to test it must work, we should probably create another class cpp17_and_cpp20_input_iterator
What do you think?
Thanks for addressing the feedback!
Question: why is this check necessary (is_member_pointer)?
If a type modeling the _bare minimum_ required to satisfy cpp17_input_iterator doesn't meet the requirements, then we can say that cpp17_input_iterator doesn't work. Consider a comment like "cpp17_input_iterator doesn't satisfy the std::input_iterator constraint".
if the caller is passing a member function pointer as comparator and two identitys as projections, without this check, if would just return __comp, which is a member function pointer. And the returned member function pointer is used by the __impl function and the __impl function simply invoke operator() as __comp(*first, *second). This would fail because member function pointer don't support this syntax.
I suspect the overload above needs the same treatment. For the algorithms you've implemented, do you have any tests that pass a member function pointer as comparator and std::identity as projection?
LGTM % nits.
This formatting is really weird. Hopefully I'll have some time soon to fix clang-format a bit.
Why aren't you returning std::__set_difference(...).second here? IIUC explicitly doing the move is either redundant because of implicit move or detrimental because of copy elision.
Could you also uncomment the corresponding line in ranges_result_alias_declarations.compile.pass.cpp?
Double checked with several compilers, it is always a move
not because it is implicit move, it is because the expression make_pair(x, y).second yields an rvalue reference to the second member,