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 13 // template<permutable I, sentinel_for<I> S, class T, class Proj = identity> 14 // requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*> 15 // constexpr subrange<I> ranges::remove(I first, S last, const T& value, Proj proj = {}); 16 // template<forward_range R, class T, class Proj = identity> 17 // requires permutable<iterator_t<R>> && 18 // indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*> 19 // constexpr borrowed_subrange_t<R> 20 // ranges::remove(R&& r, const T& value, Proj proj = {}); 21 22 #include <algorithm> 23 #include <array> 24 #include <cassert> 25 #include <ranges> 26 27 #include "almost_satisfies_types.h" 28 #include "boolean_testable.h" 29 #include "test_iterators.h" 30 31 template <class Iter, class Sent = sentinel_wrapper<Iter>> 32 concept HasRemoveIt = requires(Iter first, Sent last) { std::ranges::remove(first, last, 0); }; 33 34 static_assert(HasRemoveIt<int*>); 35 static_assert(!HasRemoveIt<PermutableNotForwardIterator>); 36 static_assert(!HasRemoveIt<PermutableNotSwappable>); 37 static_assert(!HasRemoveIt<int*, SentinelForNotSemiregular>); 38 static_assert(!HasRemoveIt<int*, SentinelForNotWeaklyEqualityComparableWith>); 39 static_assert(!HasRemoveIt<int**>); // not indirect_binary_prediacte 40 41 template <class Range> 42 concept HasRemoveR = requires(Range range) { std::ranges::remove(range, 0); }; 43 44 static_assert(HasRemoveR<UncheckedRange<int*>>); 45 static_assert(!HasRemoveR<PermutableRangeNotForwardIterator>); 46 static_assert(!HasRemoveR<PermutableRangeNotSwappable>); 47 static_assert(!HasRemoveR<SentinelForNotSemiregular>); 48 static_assert(!HasRemoveR<SentinelForNotWeaklyEqualityComparableWith>); 49 static_assert(!HasRemoveR<UncheckedRange<int**>>); // not indirect_binary_prediacte 50 51 template <int N, int M> 52 struct Data { 53 std::array<int, N> input; 54 std::array<int, M> expected; 55 int val; 56 }; 57 58 template <class Iter, class Sent, int N, int M> 59 constexpr void test(Data<N, M> d) { 60 { // iterator overload 61 auto input = d.input; 62 63 std::same_as<std::ranges::subrange<Iter>> decltype(auto) ret = 64 std::ranges::remove(Iter(input.data()), Sent(Iter(input.data() + input.size())), d.val); 65 66 assert(base(ret.begin()) == input.data() + M); 67 assert(base(ret.end()) == input.data() + N); 68 assert(std::ranges::equal(input.begin(), base(ret.begin()), d.expected.begin(), d.expected.end())); 69 } 70 71 { // range overload 72 auto input = d.input; 73 auto range = std::ranges::subrange(Iter(input.data()), Sent(Iter(input.data() + input.size()))); 74 75 std::same_as<std::ranges::subrange<Iter>> decltype(auto) ret = std::ranges::remove(range, d.val); 76 77 assert(base(ret.begin()) == input.data() + M); 78 assert(base(ret.end()) == input.data() + N); 79 assert(std::ranges::equal(base(input.begin()), base(ret.begin()), d.expected.begin(), d.expected.end())); 80 } 81 } 82 83 template <class Iter, class Sent> 84 constexpr void tests() { 85 // simple test 86 test<Iter, Sent, 6, 5>({.input = {1, 2, 3, 4, 5, 6}, .expected = {1, 2, 3, 4, 6}, .val = 5}); 87 // empty range 88 test<Iter, Sent, 0, 0>({}); 89 // single element range - match 90 test<Iter, Sent, 1, 0>({.input = {1}, .expected = {}, .val = 1}); 91 // single element range - no match 92 test<Iter, Sent, 1, 1>({.input = {1}, .expected = {1}, .val = 2}); 93 // two element range - same order 94 test<Iter, Sent, 2, 1>({.input = {1, 2}, .expected = {1}, .val = 2}); 95 // two element range - reversed order 96 test<Iter, Sent, 2, 1>({.input = {1, 2}, .expected = {2}, .val = 1}); 97 // all elements match 98 test<Iter, Sent, 5, 0>({.input = {1, 1, 1, 1, 1}, .expected = {}, .val = 1}); 99 // the relative order of elements isn't changed 100 test<Iter, Sent, 8, 5>({.input = {1, 2, 3, 2, 3, 4, 2, 5}, .expected = {1, 3, 3, 4, 5}, .val = 2}); 101 } 102 103 template <class Iter> 104 constexpr void test_sentinels() { 105 tests<Iter, Iter>(); 106 tests<Iter, sentinel_wrapper<Iter>>(); 107 tests<Iter, sized_sentinel<Iter>>(); 108 } 109 110 constexpr void test_iterators() { 111 test_sentinels<forward_iterator<int*>>(); 112 test_sentinels<bidirectional_iterator<int*>>(); 113 test_sentinels<random_access_iterator<int*>>(); 114 test_sentinels<contiguous_iterator<int*>>(); 115 test_sentinels<int*>(); 116 } 117 118 constexpr bool test() { 119 test_iterators(); 120 121 { // check that ranges::dangling is returned 122 [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret = 123 std::ranges::remove(std::array{1, 2, 3, 4}, 1); 124 } 125 126 { // check complexity requirements 127 struct CompCounter { 128 int* comp_count; 129 130 constexpr bool operator==(const CompCounter&) const { 131 ++*comp_count; 132 return false; 133 } 134 }; 135 { 136 int proj_count = 0; 137 auto proj = [&](CompCounter i) { 138 ++proj_count; 139 return i; 140 }; 141 int comp_count = 0; 142 143 CompCounter a[] = {{&comp_count}, {&comp_count}, {&comp_count}, {&comp_count}}; 144 auto ret = std::ranges::remove(std::begin(a), std::end(a), CompCounter{&comp_count}, proj); 145 assert(ret.begin() == std::end(a) && ret.end() == std::end(a)); 146 assert(comp_count == 4); 147 assert(proj_count == 4); 148 } 149 { 150 int proj_count = 0; 151 auto proj = [&](CompCounter i) { 152 ++proj_count; 153 return i; 154 }; 155 int comp_count = 0; 156 157 CompCounter a[] = {{&comp_count}, {&comp_count}, {&comp_count}, {&comp_count}}; 158 auto ret = std::ranges::remove(a, CompCounter{&comp_count}, proj); 159 assert(ret.begin() == std::end(a) && ret.end() == std::end(a)); 160 assert(comp_count == 4); 161 assert(proj_count == 4); 162 } 163 } 164 165 { // check that std::invoke is used 166 struct S { 167 constexpr S& identity() { return *this; } 168 bool operator==(const S&) const = default; 169 }; 170 { 171 S a[4] = {}; 172 auto ret = std::ranges::remove(std::begin(a), std::end(a), S{}, &S::identity); 173 assert(ret.begin() == std::begin(a)); 174 assert(ret.end() == std::end(a)); 175 } 176 { 177 S a[4] = {}; 178 auto ret = std::ranges::remove(a, S{}, &S::identity); 179 assert(ret.begin() == std::begin(a)); 180 assert(ret.end() == std::end(a)); 181 } 182 } 183 184 { 185 // check that the implicit conversion to bool works 186 { 187 StrictComparable<int> a[] = {1, 2, 3, 4}; 188 auto ret = std::ranges::remove(a, a + 4, StrictComparable<int>{2}); 189 assert(ret.begin() == a + 3); 190 } 191 { 192 StrictComparable<int> a[] = {1, 2, 3, 4}; 193 auto ret = std::ranges::remove(a, StrictComparable<int>{2}); 194 assert(ret.begin() == a + 3); 195 } 196 } 197 198 return true; 199 } 200 201 int main(int, char**) { 202 test(); 203 static_assert(test()); 204 205 return 0; 206 } 207