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