450 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 Proj = identity,14// indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>15// requires indirectly_copyable<I, O> &&16// (forward_iterator<I> ||17// (input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>) ||18// indirectly_copyable_storable<I, O>)19// constexpr unique_copy_result<I, O>20// unique_copy(I first, S last, O result, C comp = {}, Proj proj = {}); // Since C++2021//22// template<input_range R, weakly_incrementable O, class Proj = identity,23// indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>24// requires indirectly_copyable<iterator_t<R>, O> &&25// (forward_iterator<iterator_t<R>> ||26// (input_iterator<O> && same_as<range_value_t<R>, iter_value_t<O>>) ||27// indirectly_copyable_storable<iterator_t<R>, O>)28// constexpr unique_copy_result<borrowed_iterator_t<R>, O>29// unique_copy(R&& r, O result, C comp = {}, Proj proj = {}); // Since C++2030 31#include <algorithm>32#include <array>33#include <concepts>34#include <functional>35#include <ranges>36 37#include "almost_satisfies_types.h"38#include "counting_predicates.h"39#include "counting_projection.h"40#include "MoveOnly.h"41#include "test_iterators.h"42 43template <44 class InIter = int*,45 class Sent = int*,46 class OutIter = int*,47 class Comp = std::ranges::equal_to,48 class Proj = std::identity>49concept HasUniqueCopyIter =50 requires(InIter&& in, Sent&& sent, OutIter&& out, Comp&& comp, Proj&& proj) {51 std::ranges::unique_copy(52 std::forward<InIter>(in),53 std::forward<Sent>(sent),54 std::forward<OutIter>(out),55 std::forward<Comp>(comp),56 std::forward<Proj>(proj));57 };58 59static_assert(HasUniqueCopyIter<int*, int*, int*>);60 61// !input_iterator<I>62static_assert(!HasUniqueCopyIter<InputIteratorNotDerivedFrom, sentinel_wrapper<InputIteratorNotDerivedFrom>>);63 64// !sentinel_for<S, I>65static_assert(!HasUniqueCopyIter<int*, SentinelForNotSemiregular>);66 67// !weakly_incrementable<O>68static_assert(!HasUniqueCopyIter<int*, int*, WeaklyIncrementableNotMovable>);69 70// !indirect_equivalence_relation<Comp, projected<I, Proj>>71static_assert(!HasUniqueCopyIter<int*, int*, int*, ComparatorNotCopyable<int>>);72 73// !indirectly_copyable<I, O>74static_assert(!HasUniqueCopyIter<const int*, const int*, const int*>);75 76// forward_iterator<I>77// !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)78// !indirectly_copyable_storable<I, O>79struct AssignableFromMoveOnly {80 int data;81 constexpr AssignableFromMoveOnly& operator=(MoveOnly const& m) {82 data = m.get();83 return *this;84 }85};86static_assert(HasUniqueCopyIter<MoveOnly*, MoveOnly*, AssignableFromMoveOnly*>);87// because:88static_assert(std::forward_iterator<MoveOnly*>);89static_assert(!std::same_as<std::iter_value_t<MoveOnly*>, std::iter_value_t<AssignableFromMoveOnly*>>);90static_assert(!std::indirectly_copyable_storable<MoveOnly*, AssignableFromMoveOnly*>);91 92// !forward_iterator<I>93// (input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)94// !indirectly_copyable_storable<I, O>95struct CopyAssignableNotCopyConstructible {96 int data;97 constexpr CopyAssignableNotCopyConstructible(int i = 0) : data(i) {}98 CopyAssignableNotCopyConstructible(const CopyAssignableNotCopyConstructible&) = delete;99 CopyAssignableNotCopyConstructible& operator=(const CopyAssignableNotCopyConstructible&) = default;100 friend constexpr bool101 operator==(CopyAssignableNotCopyConstructible const&, CopyAssignableNotCopyConstructible const&) = default;102};103 104using InputAndOutputIterator = cpp17_input_iterator<CopyAssignableNotCopyConstructible*>;105static_assert(std::input_iterator<InputAndOutputIterator>);106static_assert(std::output_iterator<InputAndOutputIterator, CopyAssignableNotCopyConstructible>);107 108static_assert(109 HasUniqueCopyIter<110 cpp20_input_iterator<CopyAssignableNotCopyConstructible*>,111 sentinel_wrapper<cpp20_input_iterator<CopyAssignableNotCopyConstructible*>>,112 InputAndOutputIterator>);113// because:114static_assert(!std::forward_iterator< cpp20_input_iterator<CopyAssignableNotCopyConstructible*>>);115static_assert(116 std::input_iterator<InputAndOutputIterator> &&117 std::same_as<std::iter_value_t<cpp20_input_iterator<CopyAssignableNotCopyConstructible*>>,118 std::iter_value_t<InputAndOutputIterator>>);119static_assert(120 !std::indirectly_copyable_storable<121 cpp20_input_iterator<CopyAssignableNotCopyConstructible*>,122 InputAndOutputIterator>);123 124// !forward_iterator<I>125// !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)126// indirectly_copyable_storable<I, O>127static_assert(128 HasUniqueCopyIter<129 cpp20_input_iterator<int*>,130 sentinel_wrapper<cpp20_input_iterator<int*>>,131 cpp20_output_iterator<int*>>);132// because:133static_assert(!std::forward_iterator<cpp20_input_iterator<int*>>);134static_assert(!std::input_iterator<cpp20_output_iterator<int*>>);135static_assert(std::indirectly_copyable_storable<cpp20_input_iterator<int*>, cpp20_output_iterator<int*>>);136 137// !forward_iterator<I>138// !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)139// !indirectly_copyable_storable<I, O>140static_assert(141 !HasUniqueCopyIter<142 cpp20_input_iterator<MoveOnly*>,143 sentinel_wrapper<cpp20_input_iterator<MoveOnly*>>,144 cpp20_output_iterator<AssignableFromMoveOnly*>>);145// because:146static_assert(!std::forward_iterator<cpp20_input_iterator<MoveOnly*>>);147static_assert(!std::input_iterator<cpp20_output_iterator<MoveOnly*>>);148static_assert(149 !std::150 indirectly_copyable_storable<cpp20_input_iterator<MoveOnly*>, cpp20_output_iterator<AssignableFromMoveOnly*>>);151 152template < class Range, class OutIter = int*, class Comp = std::ranges::equal_to, class Proj = std::identity>153concept HasUniqueCopyRange =154 requires(Range&& range, OutIter&& out, Comp&& comp, Proj&& proj) {155 std::ranges::unique_copy(156 std::forward<Range>(range), std::forward<OutIter>(out), std::forward<Comp>(comp), std::forward<Proj>(proj));157 };158 159template <class T>160using R = UncheckedRange<T>;161 162static_assert(HasUniqueCopyRange<R<int*>, int*>);163 164// !input_range<R>165static_assert(!HasUniqueCopyRange<R<InputIteratorNotDerivedFrom>>);166 167// !weakly_incrementable<O>168static_assert(!HasUniqueCopyIter<R<int*>, WeaklyIncrementableNotMovable>);169 170// !indirect_equivalence_relation<Comp, projected<I, Proj>>171static_assert(!HasUniqueCopyIter<R<int*>, int*, ComparatorNotCopyable<int>>);172 173// !indirectly_copyable<I, O>174static_assert(!HasUniqueCopyIter<R<const int*>, const int*>);175 176// !forward_iterator<iterator_t<R>>177// !(input_iterator<O> && same_as<range_value_t<R>, iter_value_t<O>>)178// !indirectly_copyable_storable<iterator_t<R>, O>179static_assert(!HasUniqueCopyIter< R<cpp20_input_iterator<MoveOnly*>>, cpp20_output_iterator<AssignableFromMoveOnly*>>);180 181template <class InIter, class OutIter, template <class> class SentWrapper, std::size_t N1, std::size_t N2>182constexpr void testUniqueCopyImpl(std::array<int, N1> in, std::array<int, N2> expected) {183 using Sent = SentWrapper<InIter>;184 185 // iterator overload186 {187 std::array<int, N2> out;188 std::same_as<std::ranges::unique_copy_result<InIter, OutIter>> decltype(auto) result =189 std::ranges::unique_copy(InIter{in.data()}, Sent{InIter{in.data() + in.size()}}, OutIter{out.data()});190 assert(std::ranges::equal(out, expected));191 assert(base(result.in) == in.data() + in.size());192 assert(base(result.out) == out.data() + out.size());193 }194 195 // range overload196 {197 std::array<int, N2> out;198 std::ranges::subrange r{InIter{in.data()}, Sent{InIter{in.data() + in.size()}}};199 std::same_as<std::ranges::unique_copy_result<InIter, OutIter>> decltype(auto) result =200 std::ranges::unique_copy(r, OutIter{out.data()});201 assert(std::ranges::equal(out, expected));202 assert(base(result.in) == in.data() + in.size());203 assert(base(result.out) == out.data() + out.size());204 }205}206 207template <class InIter, class OutIter, template <class> class SentWrapper>208constexpr void testImpl() {209 // no consecutive elements210 {211 std::array in{1, 2, 3, 2, 1};212 std::array expected{1, 2, 3, 2, 1};213 testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected);214 }215 216 // one group of consecutive elements217 {218 std::array in{2, 3, 3, 3, 4, 3};219 std::array expected{2, 3, 4, 3};220 testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected);221 }222 223 // multiple groups of consecutive elements224 {225 std::array in{2, 3, 3, 3, 4, 3, 3, 5, 5, 5};226 std::array expected{2, 3, 4, 3, 5};227 testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected);228 }229 230 // all the same231 {232 std::array in{1, 1, 1, 1, 1, 1};233 std::array expected{1};234 testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected);235 }236 237 // empty range238 {239 std::array<int, 0> in{};240 std::array<int, 0> expected{};241 testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected);242 }243}244 245template <class OutIter, template <class> class SentWrapper>246constexpr void withAllPermutationsOfInIter() {247 testImpl<cpp20_input_iterator<int*>, OutIter, sentinel_wrapper>();248 testImpl<forward_iterator<int*>, OutIter, SentWrapper>();249 testImpl<bidirectional_iterator<int*>, OutIter, SentWrapper>();250 testImpl<random_access_iterator<int*>, OutIter, SentWrapper>();251 testImpl<contiguous_iterator<int*>, OutIter, SentWrapper>();252 testImpl<int*, OutIter, SentWrapper>();253}254 255template <template <class> class SentWrapper>256constexpr void withAllPermutationsOfInIterAndOutIter() {257 withAllPermutationsOfInIter<cpp20_output_iterator<int*>, SentWrapper>();258 withAllPermutationsOfInIter<forward_iterator<int*>, SentWrapper>();259 withAllPermutationsOfInIter<bidirectional_iterator<int*>, SentWrapper>();260 withAllPermutationsOfInIter<random_access_iterator<int*>, SentWrapper>();261 withAllPermutationsOfInIter<contiguous_iterator<int*>, SentWrapper>();262 withAllPermutationsOfInIter<int*, SentWrapper>();263}264 265constexpr bool test() {266 withAllPermutationsOfInIterAndOutIter<std::type_identity_t>();267 withAllPermutationsOfInIterAndOutIter<sentinel_wrapper>();268 269 // Test the overload that re-reads from the input iterator270 // forward_iterator<I>271 // !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)272 // !indirectly_copyable_storable<I, O>273 {274 MoveOnly in[5] = {1, 3, 3, 3, 1};275 // iterator overload276 {277 AssignableFromMoveOnly out[3] = {};278 auto result = std::ranges::unique_copy(in, in + 5, out);279 assert(std::ranges::equal(out, std::array{1, 3, 1}, {}, &AssignableFromMoveOnly::data));280 assert(result.in == in + 5);281 assert(result.out == out + 3);282 }283 // range overload284 {285 AssignableFromMoveOnly out[3] = {};286 auto result = std::ranges::unique_copy(std::ranges::subrange{in, in + 5}, out);287 assert(std::ranges::equal(out, std::array{1, 3, 1}, {}, &AssignableFromMoveOnly::data));288 assert(result.in == in + 5);289 assert(result.out == out + 3);290 }291 }292 293 // Test the overload that re-reads from the output iterator294 // !forward_iterator<I>295 // (input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)296 // !indirectly_copyable_storable<I, O>297 {298 using InIter = cpp20_input_iterator<CopyAssignableNotCopyConstructible*>;299 using Sent = sentinel_wrapper<InIter>;300 CopyAssignableNotCopyConstructible in[6] = {1, 1, 2, 2, 3, 3};301 // iterator overload302 {303 CopyAssignableNotCopyConstructible out[3];304 auto result = std::ranges::unique_copy(InIter{in}, Sent{InIter{in + 6}}, InputAndOutputIterator{out});305 assert(std::ranges::equal(out, std::array{1, 2, 3}, {}, &CopyAssignableNotCopyConstructible::data));306 assert(base(result.in) == in + 6);307 assert(base(result.out) == out + 3);308 }309 // range overload310 {311 CopyAssignableNotCopyConstructible out[3];312 auto r = std::ranges::subrange(InIter{in}, Sent{InIter{in + 6}});313 auto result = std::ranges::unique_copy(r, InputAndOutputIterator{out});314 assert(std::ranges::equal(out, std::array{1, 2, 3}, {}, &CopyAssignableNotCopyConstructible::data));315 assert(base(result.in) == in + 6);316 assert(base(result.out) == out + 3);317 }318 }319 320 // Test the overload that reads from the temporary copy of the value321 // !forward_iterator<I>322 // !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)323 // indirectly_copyable_storable<I, O>324 {325 using InIter = cpp20_input_iterator<int*>;326 using Sent = sentinel_wrapper<InIter>;327 int in[4] = {1, 1, 1, 2};328 // iterator overload329 {330 int out[2];331 auto result = std::ranges::unique_copy(InIter{in}, Sent{InIter{in + 4}}, cpp20_output_iterator<int*>{out});332 assert(std::ranges::equal(out, std::array{1, 2}));333 assert(base(result.in) == in + 4);334 assert(base(result.out) == out + 2);335 }336 // range overload337 {338 int out[2];339 auto r = std::ranges::subrange(InIter{in}, Sent{InIter{in + 4}});340 auto result = std::ranges::unique_copy(r, cpp20_output_iterator<int*>{out});341 assert(std::ranges::equal(out, std::array{1, 2}));342 assert(base(result.in) == in + 4);343 assert(base(result.out) == out + 2);344 }345 }346 347 struct Data {348 int data;349 };350 351 // Test custom comparator352 {353 std::array in{Data{4}, Data{8}, Data{8}, Data{8}};354 std::array expected{Data{4}, Data{8}};355 const auto comp = [](const Data& x, const Data& y) { return x.data == y.data; };356 357 // iterator overload358 {359 std::array<Data, 2> out;360 auto result = std::ranges::unique_copy(in.begin(), in.end(), out.begin(), comp);361 assert(std::ranges::equal(out, expected, comp));362 assert(base(result.in) == in.begin() + 4);363 assert(base(result.out) == out.begin() + 2);364 }365 366 // range overload367 {368 std::array<Data, 2> out;369 auto result = std::ranges::unique_copy(in, out.begin(), comp);370 assert(std::ranges::equal(out, expected, comp));371 assert(base(result.in) == in.begin() + 4);372 assert(base(result.out) == out.begin() + 2);373 }374 }375 376 // Test custom projection377 {378 std::array in{Data{4}, Data{8}, Data{8}, Data{8}};379 std::array expected{Data{4}, Data{8}};380 381 const auto proj = &Data::data;382 383 // iterator overload384 {385 std::array<Data, 2> out;386 auto result = std::ranges::unique_copy(in.begin(), in.end(), out.begin(), {}, proj);387 assert(std::ranges::equal(out, expected, {}, proj, proj));388 assert(base(result.in) == in.begin() + 4);389 assert(base(result.out) == out.begin() + 2);390 }391 392 // range overload393 {394 std::array<Data, 2> out;395 auto result = std::ranges::unique_copy(in, out.begin(), {}, proj);396 assert(std::ranges::equal(out, expected, {}, proj, proj));397 assert(base(result.in) == in.begin() + 4);398 assert(base(result.out) == out.begin() + 2);399 }400 }401 402 // Exactly last - first - 1 applications of the corresponding predicate and no403 // more than twice as many applications of any projection.404 {405 std::array in{1, 2, 3, 3, 3, 4, 3, 3, 5, 5, 6, 6, 1};406 std::array expected{1, 2, 3, 4, 3, 5, 6, 1};407 // iterator overload408 {409 std::array<int, 8> out;410 int numberOfComp = 0;411 int numberOfProj = 0;412 auto result = std::ranges::unique_copy(413 in.begin(),414 in.end(),415 out.begin(),416 counting_predicate{std::ranges::equal_to{}, numberOfComp},417 counting_projection{numberOfProj});418 assert(std::ranges::equal(out, expected));419 assert(base(result.in) == in.end());420 assert(base(result.out) == out.end());421 assert(numberOfComp == static_cast<int>(in.size() - 1));422 assert(numberOfProj <= static_cast<int>(2 * (in.size() - 1)));423 }424 // range overload425 {426 std::array<int, 8> out;427 int numberOfComp = 0;428 int numberOfProj = 0;429 auto result = std::ranges::unique_copy(430 in,431 out.begin(),432 counting_predicate{std::ranges::equal_to{}, numberOfComp},433 counting_projection{numberOfProj});434 assert(std::ranges::equal(out, expected));435 assert(base(result.in) == in.end());436 assert(base(result.out) == out.end());437 assert(numberOfComp == static_cast<int>(in.size() - 1));438 assert(numberOfProj <= static_cast<int>(2 * (in.size() - 1)));439 }440 }441 return true;442}443 444int main(int, char**) {445 test();446 static_assert(test());447 448 return 0;449}450