Idiom for initializing an std::array using a generator function taking the index?

einpolkum's answer provides the basics of using index sequence in C++17, and hints at simplifications available from C++20 onwards.

Here's how the updated version looks, using a template lambda:

#include <array>
#include <type_traits>

template<std::size_t N, typename Generator>
constexpr auto generate_array(Generator&& gen)
    noexcept(noexcept(gen(0uz)))
{
    using T = std::remove_reference_t<decltype(gen(0uz))>;

    return
        [&gen]<auto... I>(std::index_sequence<I...>)
        { return std::array<T, N>{gen(I)...}; }
        (std::make_index_sequence<N>{});
}

Live demo

Since we can't make arrays of references, then we deal with generators that return them. This version will copy from references (assuming the type has a copy constructor); depending on project needs, we might prefer to constrain the function:

constexpr auto generate_array(Generator&& gen)
    noexcept(noexcept(gen(0uz)))
    requires (!std::is_reference_v<decltype(gen(0uz))>)

or provide a compilation error:

using T = decltype(gen(0uz));
static_assert(!std::is_reference_v<T>,
                "generator must return values, not references");

Note that the latter option isn't SNIFAE-friendly like the first, but it does provide more guidance to users.

Note: the z suffix was introduced by C++23; C++20 code should use decltype(gen(std::size_t{0})) or std::invoke_result_t<Generator,std::size_t> instead.

Sorry for this quite long answer but the more I dig, the more I find (IMHO) interesting things to present and discuss.

I'm proposing two solutions:

• the first one uses directly the desired stored type at the price of low level memory handling;
• the second one is more a workaround, by wrapping the stored type.

NB two follow-up questions have been posted to ensure that following solutions are valid, especially in terms of type aliasing:

• is aliasing a plain array to an `std::array` not UB
• std::construct_at and object lifetime?

The first solution is a debatable technique, built from discussion with @WeijunZhou, aiming at overcoming the limitation of a std::index_sequence-based solution:

template <std::size_t N, std::constructible_from<std::size_t> T,
          typename Generator>
    requires(!std::is_default_constructible_v<T>)
std::array<T, N> make_array(Generator gen) {
    // is std::array<T, N> aliasable with a plain array
    static_assert(sizeof(std::array<T, N>) == N * sizeof(T));

    // T is not default constructible: low level memory manipulation

    // creating storage on std::byte to benefit from "implicit object creation"
    // adding a few bytes in order to absorb alignment
    // NB probably useless for non-overaligned or not new-extended aligned type
    constexpr std::size_t RequiredSize = sizeof(std::array<T, N>) + alignof(T);
    auto Storage = new std::byte[RequiredSize];
    void* AlignedStorage = Storage;
    auto Size = RequiredSize;
    if (!std::align(alignof(T), N, AlignedStorage, Size)) {
        delete[] Storage;
        throw std::bad_alloc();
    }
    // laundering
    std::array<T, N>* const Array =
        std::launder(static_cast<std::array<T, N>*>(AlignedStorage));

    // initializing objects in the storage
    T* it = Array->data();
    for (std::size_t i = 0; i != N; ++i) {
        new (it) T(gen(static_cast<int>(i)));
        ++it;
    }

    if constexpr (std::is_trivially_destructible_v<T>) {
        // T is trivially destructible: objects don't need to be destroyed,
        // we can merely release storage after moving the usefull data
        std::unique_ptr<std::byte[]> p(Storage);
        return std::move(*Array);
    } else {
        // T is not trivially destructible: objects explicit destruction
        // required after moving the usefull data
        auto DestroyPuned = [toDelete = Array->data()](std::byte p[]) {
            for (std::size_t i = 0; i != N; ++i) {
                toDelete[i].~T();
            }
            delete[] p;
        };
        std::unique_ptr<std::byte[], decltype(DestroyPuned)> p(Storage,
                                                               DestroyPuned);
        return std::move(*Array);
    }
}

And a working example:

#include <array>
#include <concepts>
#include <cstddef>
#include <iostream>
#include <memory>
#include <new>
#include <string>
#include <type_traits>
#include <utility>

struct Int {
    int i{};
    std::string s;
    explicit Int(int val) : i(val), s{} {}
    Int() = delete;
    ~Int() = default;

    // leaving other operators there in order to not miss one by accident
    Int(const Int&) = default;
    Int(Int&&) = default;
    Int& operator=(const Int&) = default;
    Int& operator=(Int&&) = default;
};

template <std::size_t N, std::constructible_from<std::size_t> T,
          typename Generator>
    requires(std::is_default_constructible_v<T>)
constexpr std::array<T, N> make_array(Generator gen) {
    // simple version when T is default-constructible
    std::array<T, N> Storage;
    for (std::size_t i = 0; i != N; ++i) {
        Storage[i] = gen(static_cast<int>(i));
    }
    return Storage;
}

template <std::size_t N, std::constructible_from<std::size_t> T,
          typename Generator>
    requires(!std::is_default_constructible_v<T>)
std::array<T, N> make_array(Generator gen) {
    // T is not default constructible: low level memory manipulation

    // creating storage on std::byte to benefit from "implicit object creation"
    // adding a few bytes in order to absorb alignment
    // NB probably useless for non-overaligned or not new-extended aligned type
    constexpr std::size_t RequiredSize = sizeof(std::array<T, N>) + alignof(T);
    auto Storage = new std::byte[RequiredSize];
    void* AlignedStorage = Storage;
    auto Size = RequiredSize;
    if (!std::align(alignof(T), N, AlignedStorage, Size)) {
        delete[] Storage;
        throw std::bad_alloc();
    }
    // laundering
    std::array<T, N>* const Array =
        std::launder(static_cast<std::array<T, N>*>(AlignedStorage));

    // initializing objects in the storage
    T* it = Array->data();
    for (std::size_t i = 0; i != N; ++i) {
        new (it) T(gen(static_cast<int>(i)));
        ++it;
    }

    if constexpr (std::is_trivially_destructible_v<T>) {
        // T is trivially destructible: objects don't need to be destroyed,
        // we can merely release storage after moving the usefull data
        std::unique_ptr<std::byte[]> p(Storage);
        return std::move(*Array);
    } else {
        // T is not trivially destructible: objects explicit destruction
        // required after moving the usefull data
        auto DestroyPuned = [toDelete = Array->data()](std::byte p[]) {
            for (std::size_t i = 0; i != N; ++i) {
                toDelete[i].~T();
            }
            delete[] p;
        };
        std::unique_ptr<std::byte[], decltype(DestroyPuned)> p(Storage,
                                                               DestroyPuned);
        return std::move(*Array);
    }
}

int main() {
    constexpr std::size_t N = 50000;
    auto gen = [](int i) { return Int(i); };
    std::array<Int, N> arr = make_array<N, Int>(gen);
    // // following line does not compile because make_array couldn't be made
    // // constexpr
    // constexpr std::array<Int, N> arr2 = make_array<N, Int>(gen);
    arr[10] = Int(2);
    std::cout << (arr[10].i) * (arr[3].i) << '\n';
    return (arr[10].i) * (arr[3].i);
}

Live with sanitizer
Live without sanitizer
Live without sanitizer, nor string (more readable assembly)

It allows for larger arrays than the std::index_sequence-based solution with, also, shorter build time.

The idea is to dynamically initialize a storage for a std::array<Int, N> which starts its lifetime (which is possible because its an aggregate and has implicit lifetime property). Im' laundering the array address, then doing placement new to create the objects with the desired constructor. NB the dynamically allocated storage is managed by a std::unique_ptr in order to be automatically released when leaving make_array, after having moved the data. It requires a custom deleter in order to properly destroy the objects created with placement new. NB if the given type is default-constructible, I'm providing a simpler overload It has several drawbacks though:

• might require up to 2 times the required memory, if the newly allocated array is not optimized out;
• it can't be used in constant evaluated context because of the pointer casting and, up to some point, the usage of std::unique_ptr;
• I'm unsure of the actual constructor used for std::array and Int (copy or move);
• obviously (see generated assembly) compilers are not smart enough to optimize away generation;
• for msvc, I must increase the stack with /F option.

NB The alignment management maybe simplified (see Getting heap storage with proper alignment in C++ for non-overaligned type).

Second version: here is a possible improvement replacing the dynamic array by a static one wrapped into a structure whos destructor will be used to destroy the individual objects. I keep the original version above for reference:

template <std::size_t N, std::constructible_from<std::size_t> T,
          typename Generator>
    requires(!std::is_default_constructible_v<T>)
std::array<T, N> make_array(Generator gen) {
    // creating storage on std::byte to benefit from "implicit object creation"
    alignas(alignof(T)) std::byte storage[sizeof(std::array<T, N>)];
    std::array<T, N>* const Array =
        std::launder(reinterpret_cast<std::array<T, N>*>(storage));

    // initializing objects in the storage
    T* it =
        Array->data();  // construct objects in storage through placement new
    for (std::size_t i = 0; i != N; ++i) {
        std::construct_at(it, gen(static_cast<int>(i)));
        // new (it) T(gen(static_cast<int>(i)));
        ++it;
    }

    // forcing move semantic for moving the contained objects instead of
    // copying should be legal as std::array has the correct layout and is
    // implicit lifetime
    if constexpr (!std::is_trivially_destructible_v<T>) {
        // auxiliary struct used to trigger the call of destructors on
        // the stored objects also managed alignement
        struct Deleter {
            T* toDelete;
            ~Deleter() {
                for (std::size_t i = 0; i != N; ++i) {
                    toDelete[i].~T();
                }
            }
        };
        Deleter todelete{Array->data()};
        return std::move(*Array);
    } else {
        return std::move(*Array);
    }
}

Live with sanitizer
Live without sanitizer
Live without sanitizer, nor string

Here is the workaround technique:

template <std::constructible_from<std::size_t> T>
struct MakeDefaultConstructible : public T {
    using T::T;
    constexpr MakeDefaultConstructible() : T(0) {};
};

template <std::size_t N, std::default_initializable T, typename Generator>
constexpr std::array<T, N> make_array(Generator gen) {
    // is there a way to remove the named array in order to guarantee RVO?
    // through a lambda taking a std::array<T, N>&&?
    std::array<T, N> tmp;
    for (std::size_t i = 0; i < N; ++i) {
        tmp[i] = gen(i);
    }
    return tmp;
};

I merely inherit publicly the original type into a default constructible type using the "by integral value" constructor of the original type for default construction.

Then the initialization function is straightforward.

It can be used like this:

#include <array>
#include <concepts>
#include <cstddef>

#define USESTRING
#ifdef USESTRING
#include <string>
#endif

struct Int {
    int i;
#ifdef USESTRING
    std::string s;
    Int(int val) : i(val), s{} {}
#else
    constexpr Int(int val) : i(val) {}
#endif
    Int() = delete;
    Int(const Int&) = default;
    Int(Int&&) = default;
    Int& operator=(const Int&) = default;
    Int& operator=(Int&&) = default;
    ~Int() = default;
};

template <std::constructible_from<std::size_t> T>
struct MakeDefaultConstructible : public T {
    using T::T;
    constexpr MakeDefaultConstructible() : T(0) {};
};

template <std::size_t N, std::default_initializable T, typename Generator>
constexpr std::array<T, N> make_array(Generator gen) {
    // is there a way to remove the named array in order to guarantee RVO?
    // through a lambda taking a std::array<T, N>&&?
    std::array<T, N> tmp;
    for (std::size_t i = 0; i < N; ++i) {
        tmp[i] = gen(i);
    }
    return tmp;
};

int main() {
    constexpr std::size_t N = 50000;
    auto gen = [](std::size_t i) {
        return MakeDefaultConstructible<Int>(static_cast<int>(i));
    };
    std::array<MakeDefaultConstructible<Int>, N> arr =
        make_array<N, MakeDefaultConstructible<Int>>(gen);
    arr[10] = MakeDefaultConstructible<Int>(2);
#ifdef USESTRING
    return (arr[10].i) * (arr[3].i);
#else
    constexpr std::array<MakeDefaultConstructible<Int>, N> arr2 =
        make_array<N, MakeDefaultConstructible<Int>>(gen);
    return (arr[10].i) * (arr2[3].i);
#endif
}

Live with sanitizer
Live without sanitizer
Live without sanitizer, nor string

NB the concept check can be used also in the first solution

This time the compiler can optimize more aggressively. Yet in make_array, tmp is not required to be optimized out (NRVO not mandatory). I think that it can be improved to use RVO but I don't see how at the moment. An idea in the comments would be appreciated.

Open question: the first solution, in both versions, scales up fine with the number of elements (I tried 500000 in compiler explorer, without std::string, successfuly) but it fails with the second one:

note: constexpr evaluation hit maximum step limit; possible infinite loop?

while, when in works, the code is fully optimized out:

main:
        mov     eax, 6
        ret

I don't feel it worth another question but if someone understands why, a comment could be left.
(my guess, as hinted by the compiler note, is that in first version, I cannot use constexpr initialization and in second one, it's when I try to initialize a constexpr array that the compiler fails (and, indeed, if I remove the constexpr the code compiles successfully on clang and times out on gcc (which is merely a compiler explorer limitation, I think)).
Strangely enough, is also the fact that the most agressive optimization is reached even though one of the array is not constexpr. I thought it was because arr[10] value was in plain sight for compilers but if I remove its modification gcc still optimizes everything away (but not clang)...

Here is a way to (partially) overcome the size limitation of @einpoklum 's solution. It consists in using an alternate version of std::integer_sequence (Details::seq in the snippet below) whose implementation requires less recursion depth for the compiler and allows for much larger sequences:

namespace Details {
// my one std::integer_sequence
template <typename T, T... Values>
struct seq {};

// merges 2 seq into on1
template <typename S1, typename S2>
struct merge_seq {};
template <typename T, T... First, T... Second>
struct merge_seq<seq<T, First...>, seq<T, Second...>> {
    using type = seq<T, First..., Second...>;
};

// makes 2 sub-sequences, half the size, then merges them
// specialization provided for the cases with 0 or 1 element only
// tag is required because a NTTP type in a specialization cannot depend on the
// type template parameters...
template <typename T, T I, T N,
          int tag = (N == T{0} ? 0 : (N == T{1} ? 1 : -1))>
struct make_seq_impl {
    using first = make_seq_impl<T, I, N / 2>::type;
    using second = make_seq_impl<T, I + N / 2, N - N / 2>::type;
    using type = merge_seq<first, second>::type;
};
// cannot directly specialized on N == T{0} as it depends on T, thus using the
// default initialized tag instead
template <typename T, T I, T N>
struct make_seq_impl<T, I, N, 0> {
    using type = seq<T>;
};
// cannot directly specialized on N == T{0} as it depends on T, thus using the
// default initialized tag instead
template <typename T, T I, T N>
struct make_seq_impl<T, I, N, 1> {
    using type = seq<T, I>;
};
// make a sequence of N "T" starting from T{0}
template <typename T, std::size_t N>
struct make_seq {
    using type = make_seq_impl<T, T{0}, T{N}>::type;
};

// make an array of N "T" starting from gen(T{0})
// using the indices trick
template <typename T, typename Generator, std::size_t... Is>
constexpr std::array<T, sizeof...(Is)> make_array(seq<std::size_t, Is...>,
                                                  Generator gen) {
    return std::array<T, sizeof...(Is)>{gen(Is)...};
}

}  // namespace Details

// make an array of N "T" starting from gen(T{0}) calling the helper version
template <std::size_t N, typename T, typename Generator>
constexpr std::array<T, N> make_array(Generator gen) {
    return Details::make_array<T>(
        typename Details::make_seq<std::size_t, N>::type{}, gen);
}

LIEV I just post it for information but not as a proper solution as it scales poorly in terms of compilation time: it can compile for large sequence but the compilation time gets unbearable.
It's usable for larger sequences than with std::integer_sequence but not as large I'm my first solutions