259 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9// UNSUPPORTED: c++03, c++11, c++14, c++1710 11// <algorithm>12 13// template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class T,14// class Proj = identity>15// requires indirectly_copyable<I, O> &&16// indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>17// constexpr remove_copy_result<I, O>18// remove_copy(I first, S last, O result, const T& value, Proj proj = {}); // Since C++2019//20// template<input_range R, weakly_incrementable O, class T, class Proj = identity>21// requires indirectly_copyable<iterator_t<R>, O> &&22// indirect_binary_predicate<ranges::equal_to,23// projected<iterator_t<R>, Proj>, const T*>24// constexpr remove_copy_result<borrowed_iterator_t<R>, O>25// remove_copy(R&& r, O result, const T& value, Proj proj = {}); // Since C++2026 27#include <algorithm>28#include <array>29#include <concepts>30#include <functional>31#include <ranges>32#include <utility>33 34#include "almost_satisfies_types.h"35#include "counting_projection.h"36#include "test_iterators.h"37 38struct ToPtr {39 int* operator()(int) const;40};41 42template <class Iter = int*, class Sent = int*, class OutIter = int*, class Proj = std::identity>43concept HasRemoveCopyIter =44 requires(Iter&& iter, Sent&& sent, OutIter&& out, Proj&& proj) {45 std::ranges::remove_copy(46 std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<OutIter>(out), 0, std::forward<Proj>(proj));47};48 49static_assert(HasRemoveCopyIter<int*>);50 51// !input_iterator<I>52static_assert(!HasRemoveCopyIter<InputIteratorNotDerivedFrom>);53static_assert(!HasRemoveCopyIter<cpp20_output_iterator<int*>>);54 55// !sentinel_for<S, I>56static_assert(!HasRemoveCopyIter<int*, SentinelForNotWeaklyEqualityComparableWith>);57static_assert(!HasRemoveCopyIter<int*, SentinelForNotSemiregular>);58 59// !weakly_incrementable<O>60static_assert(!HasRemoveCopyIter<int*, int*, WeaklyIncrementableNotMovable>);61 62// !indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>63static_assert(!HasRemoveCopyIter<int*, int*, int*, ToPtr>);64 65// !indirectly_copyable<I, O>66static_assert(!HasRemoveCopyIter<int*, int*, OutputIteratorNotIndirectlyWritable>);67static_assert(!HasRemoveCopyIter<const int*, const int*, const int*>);68 69template <class Range, class OutIter = int*, class Proj = std::identity>70concept HasRemoveCopyRange =71 requires(Range&& range, OutIter&& out, Proj&& proj) {72 std::ranges::remove_copy(73 std::forward<Range>(range), std::forward<OutIter>(out), 0, std::forward<Proj>(proj));74};75 76template <class T>77using R = UncheckedRange<T>;78 79static_assert(HasRemoveCopyRange<R<int*>>);80 81// !input_range<R>82static_assert(!HasRemoveCopyRange<InputRangeNotDerivedFrom>);83static_assert(!HasRemoveCopyRange<InputRangeNotIndirectlyReadable>);84static_assert(!HasRemoveCopyRange<InputRangeNotInputOrOutputIterator>);85static_assert(!HasRemoveCopyRange<InputRangeNotSentinelSemiregular>);86static_assert(!HasRemoveCopyRange<InputRangeNotSentinelEqualityComparableWith>);87 88// !weakly_incrementable<O>89static_assert(!HasRemoveCopyRange<R<int*>, WeaklyIncrementableNotMovable>);90 91// !indirect_binary_predicate<ranges::equal_to, projected<iterator_t<I>, Proj>, const T*>92static_assert(!HasRemoveCopyRange<R<int*>, int*, ToPtr>);93 94// !indirectly_copyable<I, O>95static_assert(!HasRemoveCopyRange<R<int*>, int*, OutputIteratorNotIndirectlyWritable>);96static_assert(!HasRemoveCopyRange<const int*, const int*, const int*>);97 98template <int N, int M>99struct Data {100 std::array<int, N> input;101 std::array<int, M> expected;102 int val;103};104 105template <class InIter, class Sent, class OutIter, int N, int M>106constexpr void test(Data<N, M> d) {107 using Result = std::ranges::remove_copy_result<InIter, OutIter>;108 109 { // iterator overload110 std::array<int, M> output;111 112 std::same_as<Result> decltype(auto) ret = std::ranges::remove_copy(113 InIter(d.input.data()), Sent(InIter(d.input.data() + d.input.size())), OutIter(output.data()), d.val);114 115 assert(base(ret.in) == d.input.data() + N);116 assert(base(ret.out) == output.data() + M);117 assert(d.expected == output);118 }119 120 { // range overload121 std::array<int, M> output;122 auto range = std::ranges::subrange(InIter(d.input.data()), Sent(InIter(d.input.data() + d.input.size())));123 124 std::same_as<Result> decltype(auto) ret =125 std::ranges::remove_copy(range, OutIter(output.data()), d.val);126 127 assert(base(ret.in) == d.input.data() + N);128 assert(base(ret.out) == output.data() + M);129 assert(d.expected == output);130 }131}132 133template <class Iter, class Sent, class OutIter>134constexpr void tests() {135 // simple test136 test<Iter, Sent, OutIter, 6, 5>({.input = {1, 2, 3, 4, 5, 6}, .expected = {1, 2, 3, 4, 6}, .val = 5});137 // empty range138 test<Iter, Sent, OutIter, 0, 0>({});139 // single element range - match140 test<Iter, Sent, OutIter, 1, 0>({.input = {1}, .expected = {}, .val = 1});141 // single element range - no match142 test<Iter, Sent, OutIter, 1, 1>({.input = {1}, .expected = {1}, .val = 2});143 // two element range - same order144 test<Iter, Sent, OutIter, 2, 1>({.input = {1, 2}, .expected = {1}, .val = 2});145 // two element range - reversed order146 test<Iter, Sent, OutIter, 2, 1>({.input = {1, 2}, .expected = {2}, .val = 1});147 // all elements match148 test<Iter, Sent, OutIter, 5, 0>({.input = {1, 1, 1, 1, 1}, .expected = {}, .val = 1});149 // the relative order of elements isn't changed150 test<Iter, Sent, OutIter, 8, 5>({.input = {1, 2, 3, 2, 3, 4, 2, 5}, .expected = {1, 3, 3, 4, 5}, .val = 2});151}152 153template <class InIter, class Sent>154constexpr void test_output_iterators() {155 tests<InIter, Sent, cpp17_output_iterator<int*>>();156 tests<InIter, Sent, forward_iterator<int*>>();157 tests<InIter, Sent, bidirectional_iterator<int*>>();158 tests<InIter, Sent, random_access_iterator<int*>>();159 tests<InIter, Sent, contiguous_iterator<int*>>();160 tests<InIter, Sent, int*>();161}162 163template <class Iter>164constexpr void test_sentinels() {165 test_output_iterators<Iter, Iter>();166 test_output_iterators<Iter, sentinel_wrapper<Iter>>();167 test_output_iterators<Iter, sized_sentinel<Iter>>();168}169 170constexpr bool test() {171 test_output_iterators<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();172 test_output_iterators<cpp17_input_iterator<int*>, sized_sentinel<cpp17_input_iterator<int*>>>();173 test_output_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();174 test_output_iterators<cpp20_input_iterator<int*>, sized_sentinel<cpp20_input_iterator<int*>>>();175 test_sentinels<forward_iterator<int*>>();176 test_sentinels<bidirectional_iterator<int*>>();177 test_sentinels<random_access_iterator<int*>>();178 test_sentinels<contiguous_iterator<int*>>();179 test_sentinels<int*>();180 181 { // check that passing a different type works182 struct S {183 constexpr operator int() const { return 3; }184 };185 186 { // iterator overload187 int a[] = {1, 2, 3, 4};188 int b[3];189 std::ranges::remove_copy(std::begin(a), std::end(a), std::begin(b), S{});190 }191 192 { // range overload193 int a[] = {1, 2, 3, 4};194 int b[3];195 std::ranges::remove_copy(a, std::begin(b), S{});196 }197 }198 199 { // check that a custom projection works200 struct S {201 constexpr operator int() const { return 3; }202 };203 204 { // iterator overload205 int a[] = {1, 2, 3, 4};206 int b[3];207 std::ranges::remove_copy(std::begin(a), std::end(a), std::begin(b), S{});208 209 }210 { // range overload211 int a[] = {1, 2, 3, 4};212 int b[3];213 std::ranges::remove_copy(a, std::begin(b), S{});214 }215 }216 217 // Complexity: Exactly last - first applications of the corresponding predicate and any projection.218 219 {220 std::array in{4, 4, 5, 6};221 std::array expected{5, 6};222 223 // iterator overload224 {225 int numberOfProj = 0;226 std::array<int, 2> out;227 std::ranges::remove_copy(228 in.begin(),229 in.end(),230 out.begin(),231 4,232 counting_projection(numberOfProj));233 234 assert(numberOfProj == static_cast<int>(in.size()));235 236 assert(std::ranges::equal(out, expected));237 }238 239 // range overload240 {241 int numberOfProj = 0;242 std::array<int, 2> out;243 std::ranges::remove_copy(244 in, out.begin(), 4, counting_projection(numberOfProj));245 assert(numberOfProj == static_cast<int>(in.size()));246 assert(std::ranges::equal(out, expected));247 }248 }249 250 return true;251}252 253int main(int, char**) {254 test();255 static_assert(test());256 257 return 0;258}259