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 // template<forward_iterator I, sentinel_for<I> S, class Proj = identity, 14 // indirect_unary_predicate<projected<I, Proj>> Pred> 15 // constexpr subrange<I> ranges::find_last_if(I first, S last, Pred pred, Proj proj = {}); 16 // template<forward_range R, class Proj = identity, 17 // indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> 18 // constexpr borrowed_subrange_t<R> ranges::find_last_if(R&& r, Pred pred, Proj proj = {}); 19 20 #include <algorithm> 21 #include <array> 22 #include <cassert> 23 #include <ranges> 24 25 #include "almost_satisfies_types.h" 26 #include "test_iterators.h" 27 28 struct Predicate { 29 bool operator()(int); 30 }; 31 32 template <class It, class Sent = It> 33 concept HasFindLastIfIt = requires(It it, Sent sent) { std::ranges::find_last_if(it, sent, Predicate{}); }; 34 static_assert(HasFindLastIfIt<int*>); 35 static_assert(HasFindLastIfIt<forward_iterator<int*>>); 36 static_assert(!HasFindLastIfIt<cpp20_input_iterator<int*>>); 37 static_assert(!HasFindLastIfIt<ForwardIteratorNotDerivedFrom>); 38 static_assert(!HasFindLastIfIt<ForwardIteratorNotIncrementable>); 39 static_assert(!HasFindLastIfIt<forward_iterator<int*>, SentinelForNotSemiregular>); 40 static_assert(!HasFindLastIfIt<forward_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>); 41 42 static_assert(!HasFindLastIfIt<int*, int>); 43 static_assert(!HasFindLastIfIt<int, int*>); 44 45 template <class Pred> 46 concept HasFindLastIfPred = requires(int* it, Pred pred) { std::ranges::find_last_if(it, it, pred); }; 47 48 static_assert(!HasFindLastIfPred<IndirectUnaryPredicateNotCopyConstructible>); 49 static_assert(!HasFindLastIfPred<IndirectUnaryPredicateNotPredicate>); 50 51 template <class R> 52 concept HasFindLastIfR = requires(R r) { std::ranges::find_last_if(r, Predicate{}); }; 53 static_assert(HasFindLastIfR<std::array<int, 0>>); 54 static_assert(!HasFindLastIfR<int>); 55 static_assert(!HasFindLastIfR<ForwardRangeNotDerivedFrom>); 56 static_assert(!HasFindLastIfR<ForwardRangeNotIncrementable>); 57 static_assert(!HasFindLastIfR<ForwardRangeNotSentinelSemiregular>); 58 static_assert(!HasFindLastIfR<ForwardRangeNotSentinelEqualityComparableWith>); 59 60 template <class It, class Sent> 61 constexpr auto make_range(auto& a) { 62 return std::ranges::subrange(It(std::ranges::begin(a)), Sent(It(std::ranges::end(a)))); 63 } 64 65 template <template <class> class IteratorT, template <class> class SentinelT> 66 constexpr void test_iterator_classes() { 67 { 68 using it = IteratorT<int*>; 69 using sent = SentinelT<it>; 70 71 { 72 int a[] = {1, 2, 3, 4}; 73 std::same_as<std::ranges::subrange<it>> auto ret = 74 std::ranges::find_last_if(it(a), sent(it(a + 4)), [](int x) { return x == 4; }); 75 assert(base(ret.begin()) == a + 3); 76 assert(*ret.begin() == 4); 77 } 78 { 79 int a[] = {1, 2, 3, 4}; 80 81 std::same_as<std::ranges::subrange<it>> auto ret = 82 std::ranges::find_last_if(make_range<it, sent>(a), [](int x) { return x == 4; }); 83 assert(ret.begin() == it(a + 3)); 84 assert(*ret.begin() == 4); 85 } 86 } 87 88 { // check that an empty range works 89 using it = IteratorT<std::ranges::iterator_t<std::array<int, 0>&>>; 90 using sent = SentinelT<it>; 91 92 { 93 std::array<int, 0> a = {}; 94 95 auto ret = std::ranges::find_last_if(it(a.begin()), sent(it(a.end())), [](auto&&) { return true; }).begin(); 96 assert(ret == it(a.end())); 97 } 98 { 99 std::array<int, 0> a = {}; 100 101 auto ret = std::ranges::find_last_if(make_range<it, sent>(a), [](auto&&) { return true; }).begin(); 102 assert(ret == it(a.end())); 103 } 104 } 105 106 { // check that last is returned with no match 107 using it = IteratorT<int*>; 108 using sent = SentinelT<it>; 109 110 { 111 int a[] = {1, 1, 1}; 112 113 auto ret = std::ranges::find_last_if(it(a), sent(it(a + 3)), [](auto&&) { return false; }).begin(); 114 assert(ret == it(a + 3)); 115 } 116 { 117 int a[] = {1, 1, 1}; 118 119 auto ret = std::ranges::find_last_if(make_range<it, sent>(a), [](auto&&) { return false; }).begin(); 120 assert(ret == it(a + 3)); 121 } 122 } 123 124 { // check that the last element is returned 125 struct S { 126 int comp; 127 int other; 128 }; 129 using it = IteratorT<S*>; 130 using sent = SentinelT<it>; 131 132 S a[] = {{0, 0}, {0, 2}, {0, 1}}; 133 134 auto ret = std::ranges::find_last_if( 135 it(std::begin(a)), sent(it(std::end(a))), [](int c) { return c == 0; }, &S::comp) 136 .begin(); 137 assert(ret == it(a + 2)); 138 assert((*ret).comp == 0); 139 assert((*ret).other == 1); 140 } 141 142 { 143 // count projection and predicate invocation count 144 { 145 int a[] = {1, 2, 3, 4}; 146 int predicate_count = 0; 147 int projection_count = 0; 148 149 using it = IteratorT<int*>; 150 using sent = SentinelT<it>; 151 152 auto ret = 153 std::ranges::find_last_if( 154 it(a), 155 sent(it(a + 4)), 156 [&](int i) { 157 ++predicate_count; 158 return i == 2; 159 }, 160 [&](int i) { 161 ++projection_count; 162 return i; 163 }) 164 .begin(); 165 assert(ret == it(a + 1)); 166 assert(*ret == 2); 167 168 if constexpr (std::bidirectional_iterator<it>) { 169 assert(predicate_count == 3); 170 assert(projection_count == 3); 171 } else { 172 assert(predicate_count == 4); 173 assert(projection_count == 4); 174 } 175 } 176 } 177 } 178 179 struct NonConstComparable { 180 friend constexpr bool operator==(const NonConstComparable&, const NonConstComparable&) { return false; } 181 friend constexpr bool operator==(NonConstComparable&, NonConstComparable&) { return false; } 182 friend constexpr bool operator==(const NonConstComparable&, NonConstComparable&) { return false; } 183 friend constexpr bool operator==(NonConstComparable&, const NonConstComparable&) { return true; } 184 }; 185 186 // TODO: this should really use `std::const_iterator` 187 template <class T> 188 struct add_const_to_ptr { 189 using type = T; 190 }; 191 template <class T> 192 struct add_const_to_ptr<T*> { 193 using type = const T*; 194 }; 195 template <class T> 196 using add_const_to_ptr_t = typename add_const_to_ptr<T>::type; 197 198 constexpr bool test() { 199 test_iterator_classes<std::type_identity_t, std::type_identity_t>(); 200 test_iterator_classes<add_const_to_ptr_t, std::type_identity_t>(); 201 test_iterator_classes<contiguous_iterator, std::type_identity_t>(); 202 test_iterator_classes<random_access_iterator, std::type_identity_t>(); 203 test_iterator_classes<bidirectional_iterator, std::type_identity_t>(); 204 test_iterator_classes<forward_iterator, std::type_identity_t>(); 205 test_iterator_classes<forward_iterator, sentinel_wrapper>(); 206 207 { 208 // check that projections are used properly and that they are called with the iterator directly 209 { 210 int a[] = {1, 2, 3, 4}; 211 auto ret = 212 std::ranges::find_last_if(a, a + 4, [&](int* i) { return i == a + 3; }, [](int& i) { return &i; }).begin(); 213 assert(ret == a + 3); 214 } 215 { 216 int a[] = {1, 2, 3, 4}; 217 auto ret = std::ranges::find_last_if(a, [&](int* i) { return i == a + 3; }, [](int& i) { return &i; }).begin(); 218 assert(ret == a + 3); 219 } 220 } 221 222 { 223 // check that ranges::dangling is returned 224 [[maybe_unused]] std::same_as<std::ranges::dangling> auto ret = 225 std::ranges::find_last_if(std::array{1, 2}, [](int) { return false; }); 226 } 227 228 { 229 // check that a subrange is returned with a borrowing range 230 int a[] = {1, 2, 3, 4}; 231 std::same_as<std::ranges::subrange<int*>> auto ret = 232 std::ranges::find_last_if(std::views::all(a), [](int) { return true; }); 233 assert(ret.begin() == a + 3); 234 assert(*ret.begin() == 4); 235 } 236 237 { 238 // check that the return type of `iter::operator*` doesn't change 239 { 240 NonConstComparable a[] = {NonConstComparable{}}; 241 242 auto ret = std::ranges::find_last_if(a, a + 1, [](auto&& e) { return e == NonConstComparable{}; }).begin(); 243 assert(ret == a); 244 } 245 { 246 NonConstComparable a[] = {NonConstComparable{}}; 247 248 auto ret = std::ranges::find_last_if(a, [](auto&& e) { return e == NonConstComparable{}; }).begin(); 249 assert(ret == a); 250 } 251 } 252 253 return true; 254 } 255 256 int main(int, char**) { 257 test(); 258 static_assert(test()); 259 260 return 0; 261 } 262