aboutsummaryrefslogtreecommitdiff
path: root/libcxx/include/algorithm
AgeCommit message (Collapse)AuthorFilesLines
2022-08-08[libc++][ranges] Implement `ranges::is_permutation`Nikolas Klauser1-0/+16
Co-authored-by: Konstantin Varlamov <varconst@apple.com> Differential Revision: https://reviews.llvm.org/D127194 (cherry picked from commit 4038c859e58c12e997041927a87e880f2f3ef883)
2022-08-08[libc++][NFC] Remove rebase artifactIgor Zhukov1-1/+0
I found it in this commit: https://github.com/llvm/llvm-project/commit/a203acb9dd7227323d6161431225189d49917744 Reviewed By: Mordante Differential Revision: https://reviews.llvm.org/D131163 (cherry picked from commit 1915c1c01e6c84a1fda5a313f85e2a3dbccd7ce0)
2022-08-08[libc++][ranges] Implement `ranges::clamp`Nikolas Klauser1-0/+7
Differential Revision: https://reviews.llvm.org/D126193 (cherry picked from commit a203acb9dd7227323d6161431225189d49917744)
2022-08-08[libc++][ranges] Implement `ranges::rotate`.Konstantin Varlamov1-0/+8
Also fix `ranges::stable_sort` and `ranges::inplace_merge` to support proxy iterators now that their internal implementations can correctly dispatch `rotate`. Differential Revision: https://reviews.llvm.org/D130758 (cherry picked from commit 36c746ca2d5b325a7ac64135c1ff8774c06ab34c)
2022-08-05[libc++][ranges] Implement `ranges::{prev, next}_permutation`.Nikolas Klauser1-0/+33
Co-authored-by: Konstantin Varlamov <varconst@apple.com> Differential Revision: https://reviews.llvm.org/D129859 (cherry picked from commit 68264b649461206dc095e672eacf8a003e0b9e49)
2022-08-05[libc++][ranges] Implement `ranges::sample`.Konstantin Varlamov1-0/+13
Differential Revision: https://reviews.llvm.org/D130865 (cherry picked from commit 6bdb64223473585f783572c9fbf0673b4b324a35)
2022-08-05[libc++][ranges] Implement `ranges::replace_copy{,_if}`.Nikolas Klauser1-0/+39
Co-authored-by: Konstantin Varlamov <varconst@apple.com> Differential Revision: https://reviews.llvm.org/D129806 (cherry picked from commit 93172c1c2b10066628c85c9ff78eb882222fb304)
2022-08-05[libc++][ranges] Implement `ranges::remove_copy{, _if}`.Nikolas Klauser1-0/+34
Co-authored-by: Hui Xie <hui.xie1990@gmail.com> Differential Revision: https://reviews.llvm.org/D130599 (cherry picked from commit 760d2b462c04537d119d76d3cc37d2cb53774a05)
2022-08-02[libc++][ranges] Implement `std::ranges::partial_sort_copy`.Konstantin Varlamov1-0/+20
Differential Revision: https://reviews.llvm.org/D130532 (cherry picked from commit db7d7959787ed68f037e2a6e5a70bb0d8c17ab27)
2022-08-02[libc++][ranges] implement `std::ranges::unique{_copy}`Hui Xie1-0/+30
implement `std::ranges::unique` and `std::ranges::unique_copy` Differential Revision: https://reviews.llvm.org/D130404 (cherry picked from commit 72f57e3a30d597346feec74cf626796b0055680f)
2022-08-02[libc++][ranges] implement `std::ranges::inplace_merge`Hui Xie1-4/+16
Differential Revision: https://reviews.llvm.org/D130627 (cherry picked from commit 8a61749f767e9af773051fc4f6dc99276fe189e3)
2022-07-26[libc++][ranges] Implement `ranges::is_heap{,_until}`.Konstantin Varlamov1-0/+19
Differential Revision: https://reviews.llvm.org/D130547
2022-07-26[libc++][ranges] Implement `ranges::generate{,_n}`.Konstantin Varlamov1-0/+14
Differential Revision: https://reviews.llvm.org/D130552
2022-07-22[libc++][ranges] Implement `ranges::shuffle`.Konstantin Varlamov1-0/+11
Differential Revision: https://reviews.llvm.org/D130321
2022-07-22[libc++][ranges] implement `std::ranges::includes`Hui Xie1-0/+15
implement `std::ranges::includes` and delegate to `std::includes` Differential Revision: https://reviews.llvm.org/D130116
2022-07-22[libc++][ranges] implement `std::ranges::equal_range`Hui Xie1-0/+12
implement `std::ranges::equal_range` which delegates to `std::equal_range` Differential Revision: https://reviews.llvm.org/D129796
2022-07-20[libc++][ranges] Implement `std::ranges::partition_{point,copy}`.Konstantin Varlamov1-0/+30
Reviewed By: #libc, huixie90, ldionne Differential Revision: https://reviews.llvm.org/D130070
2022-07-19[libc++][ranges] Implement `ranges::partial_sort`.varconst1-0/+12
Differential Revision: https://reviews.llvm.org/D128744
2022-07-18[libc++][ranges] Implement `ranges::{,stable_}partition`.Konstantin Varlamov1-0/+24
Differential Revision: https://reviews.llvm.org/D129624
2022-07-14[libc++][ranges] implement `std::ranges::set_union`Hui Xie1-0/+18
[libc++][ranges] implement `std::ranges::set_union` Differential Revision: https://reviews.llvm.org/D129657
2022-07-13[libc++][ranges] implement `std::ranges::set_symmetric_difference`Hui Xie1-0/+21
[libc++][ranges] implement `std::ranges::set_symmetric_difference` Differential Revision: https://reviews.llvm.org/D129520
2022-07-13[libc++] Implement ranges::find_end, ranges::search{, _n}Nikolas Klauser1-0/+46
Reviewed By: var-const, #libc, huixie90 Spies: thakis, h-vetinari, huixie90, libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D124079
2022-07-13Revert "[libc++] Implement ranges::find_end, ranges::search{, _n}"Nikolas Klauser1-46/+0
This reverts commit 76a76518507ccc59ccdad5b83f44dc8c3d9593c7.
2022-07-13[libc++] Implement ranges::find_end, ranges::search{, _n}Nikolas Klauser1-0/+46
Reviewed By: var-const, #libc, huixie90 Spies: h-vetinari, huixie90, libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D124079
2022-07-11[libc++] Implement ranges::{reverse, rotate}_copyNikolas Klauser1-2/+30
Reviewed By: var-const, #libc Spies: huixie90, libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D127211
2022-07-11[libc++][ranges] implement `std::ranges::set_intersection`Hui Xie1-0/+20
implement `std::ranges::set_intersection` by reusing the classic `std::set_intersenction` added unit tests Differential Revision: https://reviews.llvm.org/D129233
2022-07-08[libc++][ranges] Implement modifying heap algorithms:Konstantin Varlamov1-0/+48
- `ranges::make_heap`; - `ranges::push_heap`; - `ranges::pop_heap`; - `ranges::sort_heap`. Differential Revision: https://reviews.llvm.org/D128115
2022-07-08[libc++][ranges] Implement `ranges::nth_element`.Konstantin Varlamov1-0/+12
Differential Revision: https://reviews.llvm.org/D128149
2022-07-08[libcxx][ranges] implement `std::ranges::set_difference`Hui Xie1-0/+19
implement `std::ranges::set_difference` reused classic std::set_difference added unit tests Differential Revision: https://reviews.llvm.org/D128983
2022-07-06[libc++] Implement ranges::remove{, _if}Nikolas Klauser1-0/+22
Reviewed By: var-const, #libc Spies: huixie90, sstefan1, libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D128618
2022-07-04[libc++] Implement `std::ranges::merge`Hui Xie1-0/+18
Implement `std::ranges::merge`. added unit tests Differential Revision: https://reviews.llvm.org/D128611
2022-07-01[libc++][ranges] Implement `ranges::stable_sort`.Konstantin Varlamov1-3/+13
Differential Revision: https://reviews.llvm.org/D127834
2022-06-28[libc++][ranges] Finish LWG issues directly related to the One Ranges Proposal.Konstantin Varlamov1-5/+34
- P1252 ("Ranges Design Cleanup") -- deprecate `move_iterator::operator->` starting from C++20; add range comparisons to the `<functional>` synopsis. This restores `move_iterator::operator->` that was incorrectly deleted in D117656; it's still defined in the latest draft, see http://eel.is/c++draft/depr.move.iter.elem. Note that changes to `*_result` types from 6.1 in the paper are no longer relevant now that these types are aliases; - P2106 ("Alternative wording for GB315 and GB316") -- add a few `*_result` types to the synopsis in `<algorithm>` (some algorithms are not implemented yet and thus some of the proposal still cannot be marked as done); Also mark already done issues as done (or as nothing to do): - P2091 ("Fixing Issues With Range Access CPOs") was already implemented (this patch adds tests for some ill-formed cases); - LWG 3247 ("`ranges::iter_move` should perform ADL-only lookup of `iter_move`") was already implemented; - LWG 3300 ("Non-array ssize overload is underconstrained") doesn't affect the implementation; - LWG 3335 ("Resolve C++20 NB comments US 273 and GB 274") was already implemented; - LWG 3355 ("The memory algorithms should support move-only input iterators introduced by P1207") was already implemented (except for testing). Differential Revision: https://reviews.llvm.org/D126053
2022-06-27[libc++] Re-add transitive includes that had been removed since LLVM 14Louis Dionne1-0/+6
This commit re-adds transitive includes that had been removed by 4cd04d1687f1, c36870c8e79c, a83f4b9cda57, 1458458b558d, 2e2f3158c604, and 489637e66dd3. This should cover almost all the includes that had been removed since LLVM 14 and that would contribute to breaking user code when releasing LLVM 15. It is possible to disable the inclusion of these headers by defining _LIBCPP_REMOVE_TRANSITIVE_INCLUDES. The intent is that vendors will enable that macro and start fixing downstream issues immediately. We can then remove the macro (and the transitive includes) by default in a future release. That way, we will break users only once by removing transitive includes in bulk instead of doing it bit by bit a every release, which is more disruptive for users. Note 1: The set of headers to re-add was found by re-generating the transitive include test on a checkout of release/14.x, which provided the list of all transitive includes we used to provide. Note 2: Several includes of <vector>, <optional>, <array> and <unordered_map> have been added in this commit. These transitive inclusions were added when we implemented boyer_moore_searcher in <functional>. Note 3: This is a best effort patch to try and resolve downstream breakage caused since branching LLVM 14. I wasn't able to perfectly mirror transitive includes in LLVM 14 for a few headers, so I added a release note explaining it. To summarize, adding boyer_moore_searcher created a bunch of circular dependencies, so we have to break backwards compatibility in a few cases. Differential Revision: https://reviews.llvm.org/D128661
2022-06-23[libc++] Implement ranges::move{, _backward}Nikolas Klauser1-0/+23
This patch also adds a new optimization to `std::move`. It unwraps three `reverse_iterator`s if the wrapped iterator is a `contiguous_iterator` and the iterated type is trivially_movable. This allows us to simplify `ranges::move_backward` to a forward to `std::move` without any pessimization. Reviewed By: var-const, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D126616
2022-06-17[libc++] Mark standard-mandated includes as suchNikolas Klauser1-1/+3
Reviewed By: ldionne, Mordante, #libc, saugustine Spies: saugustine, MaskRay, arichardson, mstorsjo, jloser, libcxx-commits, arphaman Differential Revision: https://reviews.llvm.org/D127953
2022-06-16[libc++][ranges] Implement `ranges::sort`.Konstantin Varlamov1-1/+12
Differential Revision: https://reviews.llvm.org/D127557
2022-06-15[libc++] Implement ranges::lexicographical_compareNikolas Klauser1-0/+17
Reviewed By: var-const, Mordante, #libc Spies: H-G-Hristov, sstefan1, libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D127130
2022-06-15[libc++] Removes unneeded <iterator> includes.Mark de Wever1-1/+0
Reviewed By: #libc, philnik Differential Revision: https://reviews.llvm.org/D127675
2022-06-10[libc++] Granularize <iterator> includesNikolas Klauser1-1/+1
Reviewed By: ldionne, #libc Spies: libcxx-commits, wenlei Differential Revision: https://reviews.llvm.org/D127445
2022-06-10[libc++] Implement ranges::replace{, _if}Nikolas Klauser1-0/+25
Reviewed By: var-const, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D126283
2022-06-08[libc++] Implement ranges::adjacent_findNikolas Klauser1-0/+11
Reviewed By: Mordante, var-const, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D126610
2022-06-06[libc++] Implement ranges::find_first_ofNikolas Klauser1-0/+16
Reviewed By: Mordante, var-const, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D126529
2022-06-06[libc++][ranges] Implement ranges::binary_search and ranges::{lower, ↵Nikolas Klauser1-0/+34
upper}_bound Reviewed By: Mordante, var-const, ldionne, #libc Spies: sstefan1, libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D121964
2022-05-27[libc++] Implement ranges::is_sorted{, _until}Nikolas Klauser1-0/+18
Reviewed By: Mordante, var-const, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D125608
2022-05-26[libc++] Implement ranges::{all, any, none}_ofNikolas Klauser1-0/+27
Reviewed By: ldionne, var-const, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D123016
2022-05-26[libc++] Implement ranges::equalNikolas Klauser1-0/+15
Reviewed By: var-const, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D123681
2022-05-25[libc++] Implement ranges::fill{, _n}Nikolas Klauser1-0/+10
Reviewed By: var-const, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D123462
2022-05-24[libc++] Implement ranges::reverseNikolas Klauser1-0/+10
Reviewed By: var-const, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D125752
2022-05-23[libc++] Add ranges::max_element to the synopsis and ADL-proof the ↵Nikolas Klauser1-0/+9
__min_element_impl calls Reviewed By: ldionne, #libc Spies: sstefan1, libcxx-commits Differential Revision: https://reviews.llvm.org/D126167
generated by cgit v1.1 at 2024-07-23 00:16:33 +0000