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
35struct NotEqualityComparable {};
36
37template <class It, class Sent = It>
38concept HasFindLastIt = requires(It it, Sent sent) { std::ranges::find_last(it, sent, *it); };
39static_assert(HasFindLastIt<int*>);
40static_assert(HasFindLastIt<forward_iterator<int*>>);
41static_assert(!HasFindLastIt<cpp20_input_iterator<int*>>);
42static_assert(!HasFindLastIt<NotEqualityComparable*>);
43static_assert(!HasFindLastIt<ForwardIteratorNotDerivedFrom>);
44static_assert(!HasFindLastIt<ForwardIteratorNotIncrementable>);
45static_assert(!HasFindLastIt<forward_iterator<int*>, SentinelForNotSemiregular>);
46static_assert(!HasFindLastIt<forward_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>);
47
48static_assert(!HasFindLastIt<int*, int>);
49static_assert(!HasFindLastIt<int, int*>);
50
51template <class Range, class ValT>
52concept HasFindLastR = requires(Range r) { std::ranges::find_last(r, ValT{}); };
53static_assert(HasFindLastR<std::array<int, 1>, int>);
54static_assert(!HasFindLastR<int, int>);
55static_assert(!HasFindLastR<std::array<NotEqualityComparable, 1>, NotEqualityComparable>);
56static_assert(!HasFindLastR<ForwardRangeNotDerivedFrom, int>);
57static_assert(!HasFindLastR<ForwardRangeNotIncrementable, int>);
58static_assert(!HasFindLastR<ForwardRangeNotSentinelSemiregular, int>);
59static_assert(!HasFindLastR<ForwardRangeNotSentinelEqualityComparableWith, int>);
60
61template <class It, class Sent = It>
62constexpr 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
116template <template <class> class IteratorT>
117constexpr 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
153template <class ElementT>
154class TriviallyComparable {
155 ElementT el_;
156
157public:
158 constexpr TriviallyComparable(ElementT el) : el_(el) {}
159 bool operator==(const TriviallyComparable&) const = default;
160};
161
162constexpr 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
202int main(int, char**) {
203 test();
204 static_assert(test());
205 return 0;
206}
207

source code of libcxx/test/std/algorithms/alg.nonmodifying/alg.find.last/ranges.find_last.pass.cpp