implement std::ranges::set_intersection by reusing the classic std::set_intersection
added unit tests
Details
- Reviewers
philnik var-const ldionne jdoerfert - Group Reviewers
Restricted Project - Commits
- rG96b674f23cd6: [libc++][ranges] implement `std::ranges::set_intersection`
Diff Detail
- Repository
- rG LLVM Github Monorepo
Event Timeline
libcxx/docs/Status/RangesAlgorithms.csv | ||
---|---|---|
57 | Nit: s/set_intersenction/set_intersection/ in the patch description. | |
libcxx/include/__algorithm/set_intersection.h | ||
32 | I'd suggest defining a simple struct to hold the return values instead. It would be more readable than a tuple (the meaning of e.g. ret.first1 is a lot more obvious than std::get<0>(ret)) and would avoid the need for the conditional macros. | |
60 | Instead of returning __first1 and __first2 and putting the responsibility to convert sentinels to iterators on the caller, I'd suggest calling next here and returning only __first1 (advanced to the last position), __first2 (same) and __result. I think iterator_operations.h would be a good place to hide the difference between std::next and std::ranges::next. |
libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.intersection/ranges_set_intersection.pass.cpp | ||
---|---|---|
230 | This class should probably also be moved to the utility header. | |
274 | Unused? | |
586 | You probably need to make this function return bool and add a static assertion here, similar to how test is invoked twice above. If there's a reason not to, please add it as a comment. |
libcxx/include/__algorithm/set_intersection.h | ||
---|---|---|
32 | That was my first attempt. it turns out that in c++03 , initialising an aggregate is so hard. I can’t just return myStrucr{a,b}; I have to declare a variable and then return it. And by declaring a variable , it might be copied (NRVO is not guaranteed ). So I have to define a proper constructor for it to work for c++03 That is too much effort and I gave up and use tuple But I still like the idea and struct with named members. what about only use struct for c++11 onward and for 03 just guard with macro | |
60 | I did consider that. But for claasic algorithm, there is no need to call next since the iterators are discarded. std::next can be a linear complexity operation and it is wasteful to compute it when the result is not needed at all. That is why I used this approach so that only ranges overload computes the next What do you think? |
libcxx/include/__algorithm/set_intersection.h | ||
---|---|---|
32 | I'd prefer to have a three-element constructor -- it is a bit of boilerplate, but I think it's vastly preferable over the downsides of using a tuple. | |
60 | I'd avoid using macros if at all possible. I think you could achieve a similar result by passing a template type as a tag to distinguish whether the function is invoked by the classic algorithm or the ranges algorithm (the return type would be decltype(auto) and the function could use if constexpr to return different types). However, I think it's more trouble than it's worth. For the classic algorithm, the compiler should be able to optimize away the unused variables and their computation. In cases like this, IMO a simpler and more obviously correct implementation is higher priority than the minor performance difference (which should be optimized away in any optimized build). |
addressing feedback
libcxx/include/__algorithm/set_intersection.h | ||
---|---|---|
32 | I used a slightly different approach now. It is combined with the other suggestion of using a "Tag" type. The "Tag" type specify what the return type should be. | |
60 | The macro is removed. and now the algorithm take the additional "tag" type. but with slightly different approach. the tag type dictates how to make the result. so the "classic tag" simply returns the output iterator and the "ranges tag" creates the set_intersection_result. The benefit is to avoid writing intermediate struct (or avoid using tuple which isn't very readable). also it avoids writing the code that converts the intermediate result (temporary struct or tuple) to the final set_intersection_result What do you think? | |
libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.intersection/ranges_set_intersection.pass.cpp | ||
274 | it is used. see the function body of runAllIteratorPermutationsTests contains static_assert | |
586 | Unfortunately that does not work because it exceeds the constexpr execution step limit, due to the large number of combination of types of iterators (it is a 3-dimentional cartesian product) The workaround here is instead of having one single static_assert that tests all the combinations, in the runAllIteratorPermutationsTests function, it has lots of smaller static_assert and each of them test 2-dimentional cartesian product which is less than the step limit. |
libcxx/include/__algorithm/set_intersection.h | ||
---|---|---|
60 | I definitely prefer this to the previous state, but I still think it's a minor optimization that isn't worth its cost in extra complexity. If these extra copies ever come up as a performance issue, we can always do the optimization later. I don't see a strong reason to avoid writing an intermediate struct -- it seems like it should be just ~6 lines of very straightforward boilerplate, mostly confined to a single internal header (but perhaps I'm missing something?). | |
libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.intersection/ranges_set_intersection.pass.cpp | ||
586 | Thanks for explaining! Please add this rationale as a comment here. |
Thanks for addressing the feedback!
libcxx/include/__algorithm/set_intersection.h | ||
---|---|---|
75 | Nit: move the iterators? |
We started seeing a test failure in libcxx/clang_tidy.sh.cpp after this patch:
FAIL: llvm-libc++-static.cfg.in :: libcxx/clang_tidy.sh.cpp (6983 of 12107) ******************** TEST 'llvm-libc++-static.cfg.in :: libcxx/clang_tidy.sh.cpp' FAILED ******************** Script: -- : 'RUN: at line 12'; clang-tidy /b/s/w/ir/x/w/llvm-llvm-project/libcxx/test/libcxx/clang_tidy.sh.cpp --warnings-as-errors=* -header-filter=.* -- -Wweak-vtables -Wno-unknown-warning-option -nostdinc++ -I /b/s/w/ir/x/w/staging/llvm_build/include/c++/v1 -I /b/s/w/ir/x/w/staging/llvm_build/include/x86_64-unknown-linux-gnu/c++/v1 -I /b/s/w/ir/x/w/llvm-llvm-project/libcxx/test/support -std=c++2b -Werror -Wall -Wextra -Wshadow -Wundef -Wno-unused-command-line-argument -Wno-attributes -Wno-pessimizing-move -Wno-c++11-extensions -Wno-noexcept-type -Wno-atomic-alignment -Wno-user-defined-literals -Wno-tautological-compare -Wsign-compare -Wunused-variable -Wunused-parameter -Wunreachable-code -Wno-unused-local-typedef -D_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER -D_LIBCPP_ENABLE_EXPERIMENTAL -D_LIBCPP_DISABLE_AVAILABILITY -fcoroutines-ts -Werror=thread-safety -Wuser-defined-warnings -fno-modules -- Exit Code: 1 Command Output (stdout): -- $ ":" "RUN: at line 12" $ "clang-tidy" "/b/s/w/ir/x/w/llvm-llvm-project/libcxx/test/libcxx/clang_tidy.sh.cpp" "--warnings-as-errors=*" "-header-filter=.*" "--" "-Wweak-vtables" "-Wno-unknown-warning-option" "-nostdinc++" "-I" "/b/s/w/ir/x/w/staging/llvm_build/include/c++/v1" "-I" "/b/s/w/ir/x/w/staging/llvm_build/include/x86_64-unknown-linux-gnu/c++/v1" "-I" "/b/s/w/ir/x/w/llvm-llvm-project/libcxx/test/support" "-std=c++2b" "-Werror" "-Wall" "-Wextra" "-Wshadow" "-Wundef" "-Wno-unused-command-line-argument" "-Wno-attributes" "-Wno-pessimizing-move" "-Wno-c++11-extensions" "-Wno-noexcept-type" "-Wno-atomic-alignment" "-Wno-user-defined-literals" "-Wno-tautological-compare" "-Wsign-compare" "-Wunused-variable" "-Wunused-parameter" "-Wunreachable-code" "-Wno-unused-local-typedef" "-D_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER" "-D_LIBCPP_ENABLE_EXPERIMENTAL" "-D_LIBCPP_DISABLE_AVAILABILITY" "-fcoroutines-ts" "-Werror=thread-safety" "-Wuser-defined-warnings" "-fno-modules" # command output: /b/s/w/ir/x/w/staging/llvm_build/include/c++/v1/__algorithm/set_intersection.h:33:40: error: invalid case style for parameter '__inIter1' [readability-identifier-naming,-warnings-as-errors] __set_intersection_result(_InIter1&& __inIter1, _InIter2&& __inIter2, _OutIter&& __outIter) ^~~~~~~~~ __in_iter1 /b/s/w/ir/x/w/staging/llvm_build/include/c++/v1/__algorithm/set_intersection.h:33:62: error: invalid case style for parameter '__inIter2' [readability-identifier-naming,-warnings-as-errors] __set_intersection_result(_InIter1&& __inIter1, _InIter2&& __inIter2, _OutIter&& __outIter) ^~~~~~~~~ __in_iter2 /b/s/w/ir/x/w/staging/llvm_build/include/c++/v1/__algorithm/set_intersection.h:33:84: error: invalid case style for parameter '__outIter' [readability-identifier-naming,-warnings-as-errors] __set_intersection_result(_InIter1&& __inIter1, _InIter2&& __inIter2, _OutIter&& __outIter) ^~~~~~~~~ __out_iter
Thanks for the report. D129503 is tested in the CI and should fix your build failure.
Nit: s/set_intersenction/set_intersection/ in the patch description.