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 <ranges> 29 #include <vector> 30 31 #include "almost_satisfies_types.h" 32 #include "test_iterators.h" 33 34 struct NotEqualityComparable {}; 35 36 template <class It, class Sent = It> 37 concept HasFindLastIt = requires(It it, Sent sent) { std::ranges::find_last(it, sent, *it); }; 38 static_assert(HasFindLastIt<int*>); 39 static_assert(HasFindLastIt<forward_iterator<int*>>); 40 static_assert(!HasFindLastIt<cpp20_input_iterator<int*>>); 41 static_assert(!HasFindLastIt<NotEqualityComparable*>); 42 static_assert(!HasFindLastIt<ForwardIteratorNotDerivedFrom>); 43 static_assert(!HasFindLastIt<ForwardIteratorNotIncrementable>); 44 static_assert(!HasFindLastIt<forward_iterator<int*>, SentinelForNotSemiregular>); 45 static_assert(!HasFindLastIt<forward_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>); 46 47 static_assert(!HasFindLastIt<int*, int>); 48 static_assert(!HasFindLastIt<int, int*>); 49 50 template <class Range, class ValT> 51 concept HasFindLastR = requires(Range r) { std::ranges::find_last(r, ValT{}); }; 52 static_assert(HasFindLastR<std::array<int, 1>, int>); 53 static_assert(!HasFindLastR<int, int>); 54 static_assert(!HasFindLastR<std::array<NotEqualityComparable, 1>, NotEqualityComparable>); 55 static_assert(!HasFindLastR<ForwardRangeNotDerivedFrom, int>); 56 static_assert(!HasFindLastR<ForwardRangeNotIncrementable, int>); 57 static_assert(!HasFindLastR<ForwardRangeNotSentinelSemiregular, int>); 58 static_assert(!HasFindLastR<ForwardRangeNotSentinelEqualityComparableWith, int>); 59 60 template <class It, class Sent = It> 61 constexpr void test_iterators() { 62 using ValueT = std::iter_value_t<It>; 63 auto make_range = [](auto& a) { 64 return std::ranges::subrange(It(std::ranges::begin(a)), Sent(It(std::ranges::end(a)))); 65 }; 66 { // simple test 67 { 68 ValueT a[] = {1, 2, 3, 4}; 69 70 std::same_as<std::ranges::subrange<It>> auto ret = std::ranges::find_last(It(a), Sent(It(a + 4)), 2); 71 assert(base(ret.begin()) == a + 1); 72 assert(*ret.begin() == 2); 73 } 74 { 75 ValueT a[] = {1, 2, 3, 4}; 76 77 std::same_as<std::ranges::subrange<It>> auto ret = std::ranges::find_last(make_range(a), 2); 78 assert(base(ret.begin()) == a + 1); 79 assert(*ret.begin() == 2); 80 } 81 } 82 83 { // check that an empty range works 84 { 85 std::array<ValueT, 0> a = {}; 86 87 auto ret = std::ranges::find_last(It(a.data()), Sent(It(a.data())), 1).begin(); 88 assert(ret == It(a.data())); 89 } 90 { 91 std::array<ValueT, 0> a = {}; 92 93 auto ret = std::ranges::find_last(make_range(a), 1).begin(); 94 assert(ret == It(a.begin())); 95 } 96 } 97 98 { // check that last is returned with no match 99 { 100 ValueT a[] = {1, 1, 1}; 101 102 auto ret = std::ranges::find_last(It(a), Sent(It(a + 3)), 0).begin(); 103 assert(ret == It(a + 3)); 104 } 105 { 106 ValueT a[] = {1, 1, 1}; 107 108 auto ret = std::ranges::find_last(make_range(a), 0).begin(); 109 assert(ret == It(a + 3)); 110 } 111 } 112 } 113 114 template <template <class> class IteratorT> 115 constexpr void test_iterator_classes() { 116 { // check that the last element is returned 117 struct S { 118 int comp; 119 int other; 120 }; 121 using it = IteratorT<S*>; 122 S a[] = {{0, 0}, {0, 2}, {0, 1}}; 123 124 auto ret = std::ranges::find_last(it(std::begin(a)), it(std::end(a)), 0, &S::comp).begin(); 125 assert(ret == it(a + 2)); 126 assert((*ret).comp == 0); 127 assert((*ret).other == 1); 128 } 129 130 { 131 // count invocations of the projection 132 using it = IteratorT<int*>; 133 134 int a[] = {1, 2, 3, 4}; 135 int projection_count = 0; 136 137 auto ret = std::ranges::find_last(it(std::begin(a)), it(std::end(a)), 2, [&](int i) { 138 ++projection_count; 139 return i; 140 }).begin(); 141 assert(ret == it(a + 1)); 142 assert(*ret == 2); 143 if (std::bidirectional_iterator<it>) { 144 assert(projection_count == 3); 145 } else { 146 assert(projection_count == 4); // must go through entire list 147 } 148 } 149 } 150 151 template <class ElementT> 152 class TriviallyComparable { 153 ElementT el_; 154 155 public: 156 constexpr TriviallyComparable(ElementT el) : el_(el) {} 157 bool operator==(const TriviallyComparable&) const = default; 158 }; 159 160 constexpr bool test() { 161 types::for_each(types::type_list<char, int, TriviallyComparable<char>>{}, []<class T> { 162 types::for_each(types::forward_iterator_list<T*>{}, []<class Iter> { 163 test_iterators<Iter>(); 164 test_iterators<Iter, sentinel_wrapper<Iter>>(); 165 test_iterators<Iter, sized_sentinel<Iter>>(); 166 }); 167 }); 168 169 test_iterator_classes<forward_iterator>(); 170 test_iterator_classes<bidirectional_iterator>(); 171 test_iterator_classes<random_access_iterator>(); 172 test_iterator_classes<std::type_identity_t>(); 173 174 { 175 std::vector<std::vector<int>> vec = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; 176 177 auto view = vec | std::views::join; 178 assert(std::ranges::find_last(view.begin(), view.end(), 4).begin() == std::next(view.begin(), 3)); 179 assert(std::ranges::find_last(view, 4).begin() == std::next(view.begin(), 3)); 180 } 181 182 { 183 // check that an iterator is returned with a borrowing range 184 int a[] = {1, 2, 3, 4}; 185 186 std::same_as<std::ranges::subrange<int*>> auto ret = std::ranges::find_last(std::views::all(a), 1); 187 assert(ret.begin() == a); 188 assert(*ret.begin() == 1); 189 } 190 191 { 192 // check that dangling ranges are dangling 193 std::same_as<std::ranges::dangling> auto ret = std::ranges::find_last(std::vector<int>(), 0); 194 (void)ret; 195 } 196 197 return true; 198 } 199 200 int main(int, char**) { 201 test(); 202 static_assert(test()); 203 return 0; 204 } 205