1 //===----------------------------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 // <algorithm> 10 11 // UNSUPPORTED: c++03, c++11, c++14, c++17, c++20 12 13 // ADDITIONAL_COMPILE_FLAGS(gcc-style-warnings): -Wno-sign-compare 14 // MSVC warning C4242: 'argument': conversion from 'const _Ty' to 'ElementT', possible loss of data 15 // MSVC warning C4244: 'argument': conversion from 'const _Ty' to 'ElementT', possible loss of data 16 // ADDITIONAL_COMPILE_FLAGS(cl-style-warnings): /wd4242 /wd4244 17 18 // template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity> 19 // requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*> 20 // constexpr subrange<I> ranges::find_last(I first, S last, const T& value, Proj proj = {}); 21 // template<forward_range R, class T, class Proj = identity> 22 // requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*> 23 // constexpr borrowed_subrange_t<R> ranges::find_last(R&& r, const T& value, Proj proj = {}); 24 25 #include <algorithm> 26 #include <array> 27 #include <cassert> 28 #include <memory> 29 #include <ranges> 30 #include <vector> 31 32 #include "almost_satisfies_types.h" 33 #include "test_iterators.h" 34 35 struct NotEqualityComparable {}; 36 37 template <class It, class Sent = It> 38 concept HasFindLastIt = requires(It it, Sent sent) { std::ranges::find_last(it, sent, *it); }; 39 static_assert(HasFindLastIt<int*>); 40 static_assert(HasFindLastIt<forward_iterator<int*>>); 41 static_assert(!HasFindLastIt<cpp20_input_iterator<int*>>); 42 static_assert(!HasFindLastIt<NotEqualityComparable*>); 43 static_assert(!HasFindLastIt<ForwardIteratorNotDerivedFrom>); 44 static_assert(!HasFindLastIt<ForwardIteratorNotIncrementable>); 45 static_assert(!HasFindLastIt<forward_iterator<int*>, SentinelForNotSemiregular>); 46 static_assert(!HasFindLastIt<forward_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>); 47 48 static_assert(!HasFindLastIt<int*, int>); 49 static_assert(!HasFindLastIt<int, int*>); 50 51 template <class Range, class ValT> 52 concept HasFindLastR = requires(Range r) { std::ranges::find_last(r, ValT{}); }; 53 static_assert(HasFindLastR<std::array<int, 1>, int>); 54 static_assert(!HasFindLastR<int, int>); 55 static_assert(!HasFindLastR<std::array<NotEqualityComparable, 1>, NotEqualityComparable>); 56 static_assert(!HasFindLastR<ForwardRangeNotDerivedFrom, int>); 57 static_assert(!HasFindLastR<ForwardRangeNotIncrementable, int>); 58 static_assert(!HasFindLastR<ForwardRangeNotSentinelSemiregular, int>); 59 static_assert(!HasFindLastR<ForwardRangeNotSentinelEqualityComparableWith, int>); 60 61 template <class It, class Sent = It> 62 constexpr void test_iterators() { 63 using ValueT = std::iter_value_t<It>; 64 auto make_range = [](auto& a) { 65 return std::ranges::subrange( 66 It(std::to_address(std::ranges::begin(a))), Sent(It(std::to_address(std::ranges::end(a))))); 67 }; 68 { // simple test 69 { 70 ValueT a[] = {1, 2, 3, 4}; 71 72 std::same_as<std::ranges::subrange<It>> auto ret = std::ranges::find_last(It(a), Sent(It(a + 4)), 2); 73 assert(base(ret.begin()) == a + 1); 74 assert(*ret.begin() == 2); 75 } 76 { 77 ValueT a[] = {1, 2, 3, 4}; 78 79 std::same_as<std::ranges::subrange<It>> auto ret = std::ranges::find_last(make_range(a), 2); 80 assert(base(ret.begin()) == a + 1); 81 assert(*ret.begin() == 2); 82 } 83 } 84 85 { // check that an empty range works 86 { 87 std::array<ValueT, 0> a = {}; 88 89 auto ret = std::ranges::find_last(It(a.data()), Sent(It(a.data())), 1).begin(); 90 assert(ret == It(a.data())); 91 } 92 { 93 std::array<ValueT, 0> a = {}; 94 95 auto ret = std::ranges::find_last(make_range(a), 1).begin(); 96 assert(ret == It(a.data())); 97 } 98 } 99 100 { // check that last is returned with no match 101 { 102 ValueT a[] = {1, 1, 1}; 103 104 auto ret = std::ranges::find_last(It(a), Sent(It(a + 3)), 0).begin(); 105 assert(ret == It(a + 3)); 106 } 107 { 108 ValueT a[] = {1, 1, 1}; 109 110 auto ret = std::ranges::find_last(make_range(a), 0).begin(); 111 assert(ret == It(a + 3)); 112 } 113 } 114 } 115 116 template <template <class> class IteratorT> 117 constexpr void test_iterator_classes() { 118 { // check that the last element is returned 119 struct S { 120 int comp; 121 int other; 122 }; 123 using it = IteratorT<S*>; 124 S a[] = {{0, 0}, {0, 2}, {0, 1}}; 125 126 auto ret = std::ranges::find_last(it(std::begin(a)), it(std::end(a)), 0, &S::comp).begin(); 127 assert(ret == it(a + 2)); 128 assert((*ret).comp == 0); 129 assert((*ret).other == 1); 130 } 131 132 { 133 // count invocations of the projection 134 using it = IteratorT<int*>; 135 136 int a[] = {1, 2, 3, 4}; 137 int projection_count = 0; 138 139 auto ret = std::ranges::find_last(it(std::begin(a)), it(std::end(a)), 2, [&](int i) { 140 ++projection_count; 141 return i; 142 }).begin(); 143 assert(ret == it(a + 1)); 144 assert(*ret == 2); 145 if (std::bidirectional_iterator<it>) { 146 assert(projection_count == 3); 147 } else { 148 assert(projection_count == 4); // must go through entire list 149 } 150 } 151 } 152 153 template <class ElementT> 154 class TriviallyComparable { 155 ElementT el_; 156 157 public: 158 constexpr TriviallyComparable(ElementT el) : el_(el) {} 159 bool operator==(const TriviallyComparable&) const = default; 160 }; 161 162 constexpr bool test() { 163 types::for_each(types::type_list<char, int, TriviallyComparable<char>>{}, []<class T> { 164 types::for_each(types::forward_iterator_list<T*>{}, []<class Iter> { 165 test_iterators<Iter>(); 166 test_iterators<Iter, sentinel_wrapper<Iter>>(); 167 test_iterators<Iter, sized_sentinel<Iter>>(); 168 }); 169 }); 170 171 test_iterator_classes<forward_iterator>(); 172 test_iterator_classes<bidirectional_iterator>(); 173 test_iterator_classes<random_access_iterator>(); 174 test_iterator_classes<std::type_identity_t>(); 175 176 { 177 std::vector<std::vector<int>> vec = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; 178 179 auto view = vec | std::views::join; 180 assert(std::ranges::find_last(view.begin(), view.end(), 4).begin() == std::next(view.begin(), 3)); 181 assert(std::ranges::find_last(view, 4).begin() == std::next(view.begin(), 3)); 182 } 183 184 { 185 // check that an iterator is returned with a borrowing range 186 int a[] = {1, 2, 3, 4}; 187 188 std::same_as<std::ranges::subrange<int*>> auto ret = std::ranges::find_last(std::views::all(a), 1); 189 assert(ret.begin() == a); 190 assert(*ret.begin() == 1); 191 } 192 193 { 194 // check that dangling ranges are dangling 195 std::same_as<std::ranges::dangling> auto ret = std::ranges::find_last(std::vector<int>(), 0); 196 (void)ret; 197 } 198 199 return true; 200 } 201 202 int main(int, char**) { 203 test(); 204 static_assert(test()); 205 return 0; 206 } 207