diff options
| author | Adrian Vogelsgesang <avogelsgesang@tableau.com> | 2022-08-04 15:21:27 -0700 |
|---|---|---|
| committer | Adrian Vogelsgesang <avogelsgesang@salesforce.com> | 2023-02-12 14:51:08 -0800 |
| commit | 2a06757a200cc8dd4c3aeca98509d50d75bb4a27 (patch) | |
| tree | 140e7a9d72c815e222a83ccb3662d7329afbf0b6 /libcxx/include/algorithm | |
| parent | 2e6430666caf303b84dd281442533d2f3b6ad1b2 (diff) | |
| download | llvm-2a06757a200cc8dd4c3aeca98509d50d75bb4a27.zip llvm-2a06757a200cc8dd4c3aeca98509d50d75bb4a27.tar.gz llvm-2a06757a200cc8dd4c3aeca98509d50d75bb4a27.tar.bz2 | |
[libc++][spaceship] Implement `lexicographical_compare_three_way`
The implementation makes use of the freedom added by LWG 3410. We have
two variants of this algorithm:
* a fast path for random access iterators: This fast path computes the
maximum number of loop iterations up-front and does not compare the
iterators against their limits on every loop iteration.
* A basic implementation for all other iterators: This implementation
compares the iterators against their limits in every loop iteration.
However, it still takes advantage of the freedom added by LWG 3410 to
avoid unnecessary additional iterator comparisons, as originally
specified by P1614R2.
https://godbolt.org/z/7xbMEen5e shows the benefit of the fast path:
The hot loop generated of `lexicographical_compare_three_way3` is
more tight than for `lexicographical_compare_three_way1`. The added
benchmark illustrates how this leads to a 30% - 50% performance
improvement on integer vectors.
Implements part of P1614R2 "The Mothership has Landed"
Fixes LWG 3410 and LWG 3350
Differential Revision: https://reviews.llvm.org/D131395
Diffstat (limited to 'libcxx/include/algorithm')
| -rw-r--r-- | libcxx/include/algorithm | 13 |
1 files changed, 13 insertions, 0 deletions
diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm index cb2d27c..52d9cc9 100644 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -1684,6 +1684,18 @@ template <class InputIterator1, class InputIterator2, class Compare> lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp); +template<class InputIterator1, class InputIterator2, class Cmp> + constexpr auto + lexicographical_compare_three_way(InputIterator1 first1, InputIterator1 last1, + InputIterator2 first2, InputIterator2 last2, + Cmp comp) + -> decltype(comp(*b1, *b2)); // since C++20 + +template<class InputIterator1, class InputIterator2> + constexpr auto + lexicographical_compare_three_way(InputIterator1 first1, InputIterator1 last1, + InputIterator2 first2, InputIterator2 last2); // since C++20 + template <class BidirectionalIterator> constexpr bool // constexpr in C++20 next_permutation(BidirectionalIterator first, BidirectionalIterator last); @@ -1753,6 +1765,7 @@ template <class BidirectionalIterator, class Compare> #include <__algorithm/is_sorted_until.h> #include <__algorithm/iter_swap.h> #include <__algorithm/lexicographical_compare.h> +#include <__algorithm/lexicographical_compare_three_way.h> #include <__algorithm/lower_bound.h> #include <__algorithm/make_heap.h> #include <__algorithm/max.h> |