143 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_or_output_iterator O, copy_constructible F>14// requires invocable<F&> && indirectly_writable<O, invoke_result_t<F&>>15// constexpr O generate_n(O first, iter_difference_t<O> n, F gen); // Since C++2016 17#include <algorithm>18#include <array>19#include <concepts>20#include <functional>21#include <ranges>22 23#include "almost_satisfies_types.h"24#include "test_iterators.h"25 26struct IntGen {27 int operator()() const;28};29 30struct UncopyableGen {31 UncopyableGen(const UncopyableGen&) = delete;32 int operator()() const;33};34static_assert(!std::copy_constructible<UncopyableGen>);35static_assert(std::invocable<UncopyableGen>);36 37struct UninvocableGen {38};39static_assert(std::copy_constructible<UninvocableGen>);40static_assert(!std::invocable<UninvocableGen>);41 42struct IntPtrGen {43 int* operator()() const;44};45 46// Test type constraints.47// ======================================================48 49template <class Iter = int*, class Gen = IntGen>50concept HasGenerateNIter =51 requires(Iter&& iter, Gen&& gen) {52 std::ranges::generate_n(std::forward<Iter>(iter), 0, std::forward<Gen>(gen));53 };54 55static_assert(HasGenerateNIter<int*, IntGen>);56 57// !input_or_output_iterator<O>58static_assert(!HasGenerateNIter<InputIteratorNotInputOrOutputIterator>);59 60// !copy_constructible<F>61static_assert(!HasGenerateNIter<int*, UncopyableGen>);62 63// !invocable<F&>64static_assert(!HasGenerateNIter<int*, UninvocableGen>);65 66// !indirectly_writable<O, invoke_result_t<F&>>67static_assert(!HasGenerateNIter<int*, IntPtrGen>);68 69template <class Iter, std::size_t N, class Gen>70constexpr void test_one(std::array<int, N> in, std::size_t n, Gen gen, std::array<int, N> expected) {71 assert(n <= N);72 73 auto begin = Iter(in.data());74 75 std::same_as<Iter> decltype(auto) result = std::ranges::generate_n(std::move(begin), n, gen);76 assert(base(result) == in.data() + n);77 assert(in == expected);78}79 80template <class Iter>81constexpr void test_iter() {82 auto gen = [ctr = 1] () mutable { return ctr++; };83 84 // Empty sequence.85 test_one<Iter, 0>({}, 0, gen, {});86 // 1-element sequence, n = 0.87 test_one<Iter>(std::array{-10}, 0, gen, {-10});88 // 1-element sequence, n = 1.89 test_one<Iter>(std::array{-10}, 1, gen, {1});90 // Longer sequence, n = 3.91 test_one<Iter>(std::array{-10, -20, -30, -40, -50}, 3, gen, {1, 2, 3, -40, -50});92 // Longer sequence, n = 5.93 test_one<Iter>(std::array<int, 5>{}, 5, gen, {1, 2, 3, 4, 5});94}95 96constexpr void test_iterators() {97 test_iter<cpp17_input_iterator<int*>>();98 test_iter<cpp20_input_iterator<int*>>();99 test_iter<cpp17_output_iterator<int*>>();100 test_iter<cpp20_output_iterator<int*>>();101 test_iter<forward_iterator<int*>>();102 test_iter<bidirectional_iterator<int*>>();103 test_iter<random_access_iterator<int*>>();104 test_iter<contiguous_iterator<int*>>();105 test_iter<int*>();106}107 108constexpr bool test() {109 test_iterators();110 111 { // Complexity: exactly N evaluations of `gen()` and assignments.112 struct AssignedOnce {113 bool assigned = false;114 constexpr AssignedOnce& operator=(const AssignedOnce&) {115 assert(!assigned);116 assigned = true;117 return *this;118 }119 };120 121 int gen_invocations = 0;122 auto gen = [&gen_invocations] { ++gen_invocations; return AssignedOnce(); };123 constexpr std::size_t N1 = 10;124 constexpr std::size_t N2 = N1 / 2;125 std::array<AssignedOnce, N1> in;126 127 auto result = std::ranges::generate_n(in.begin(), N2, gen);128 assert(std::ranges::all_of(std::ranges::subrange(in.begin(), result), &AssignedOnce::assigned));129 assert(std::ranges::none_of(std::ranges::subrange(result, in.end()), &AssignedOnce::assigned));130 assert(gen_invocations == N2);131 }132 133 134 return true;135}136 137int main(int, char**) {138 test();139 static_assert(test());140 141 return 0;142}143