Populate std::array with non-default-constructible type (no variadic templates)

Question

Suppose I have a type A with no default constructor:

struct A
{
  int x;
  A(int x) : x(x) {}
};

I want to make an std::array of A. I can easily make it with initializer list:

std::array<A, 5> arr = { 0, 1, 4, 9, 16 };

You can see a pattern here. Yes, I can have a generator function to compute each value of the array:

int makeElement(size_t i)
{
  return i * i;
}

std::array<A, 5> arr = { 
  makeElement(0), 
  makeElement(1),
  makeElement(2),
  makeElement(3),
  makeElement(4)
};

And yes, in fact I have much more than 5 elements (64, namely). So it would be nice not to repeat makeElement 64 times. The only solution I came up with is to use variadic templates to unpack parameter pack into the initializer list: https://ideone.com/yEWZVq (it also checks that all copies are properly elided). This solution was inspired by this question.

It works, but I would like not to abuse variadic templates for such a simple task. You know, bloating executable size, slowing down the compilation, all that stuff. I would like to do something like this:

1. Create some uninitialized storage with a proper size
2. Initialize all elements in the loop with placement new
3. Magically convert the storage to std::array and return it

I can do some dirty hacks to implement this in dynamic memory: https://ideone.com/tbw5lm But this is not better than a std::vector, where I do not have such problems at all.

And I have no idea how I can do it in automatic memory. I.e. to have the same convenient function returning std::array by value with all this stuff behind the hood. Any ideas?

I suppose, that boost::container::static_vector might be good solution for me. Unfortunately, I cannot use boost for that particular task.

PS. Note please that this question is more like of research interest. In a real world both variadic templates and std::vector would work just fine. I just want to know maybe I am missing something.

Answer 1

Here's another way which allows an arbitrary range of inputs to the generator:

Here's the use case:

/// generate an integer by multiplying the input by 2
/// this could just as easily be a lambda or function object
constexpr int my_generator(int x) {
    return 2 * x;
}

int main()
{
    // generate a std::array<int, 64> containing the values
    // 0 - 126 inclusive (the 64 acts like an end() iterator)
    static constexpr auto arr = generate_array(range<int, 0, 64>(),
                                               my_generator);

    std::copy(arr.begin(), arr.end(), std::ostream_iterator<int>(std::cout, ", "));
    std::cout << std::endl;
}

Here's the boilerplate to allow it to work

#include <utility>
#include <array>
#include <iostream>
#include <algorithm>
#include <iterator>

/// the concept of a class that holds a range of something
/// @requires T + 1 results in the next T
/// @requires Begin + 1 + 1 + 1.... eventually results in Tn == End
template<class T, T Begin, T End>
struct range
{
    constexpr T begin() const { return Begin; }
    constexpr T end() const { return End; }

    constexpr T size() const { return end() - begin(); }
    using type = T;
};

/// offset every integer in an integer sequence by a value
/// e.g offset(2, <1, 2, 3>) -> <3, 4, 5>
template<int Offset, int...Is>
constexpr auto offset(std::integer_sequence<int, Is...>)
{
    return std::integer_sequence<int, (Is + Offset)...>();
}

/// generate a std::array by calling Gen(I) for every I in Is
template<class T, class I, I...Is, class Gen>
constexpr auto generate_array(std::integer_sequence<I, Is...>, Gen gen)
{
    return std::array<T, sizeof...(Is)> {
        gen(Is)...
    };
}

/// generate a std::array by calling Gen (x) for every x in Range
template<class Range, class Gen>
constexpr auto generate_array(Range range, Gen&& gen)
{
    using T = decltype(gen(range.begin()));
    auto from_zero = std::make_integer_sequence<typename Range::type, range.size()>();
    auto indexes = offset<range.begin()>(from_zero);
    return generate_array<T>(indexes, std::forward<Gen>(gen));
}

/// generate an integer by multiplying the input by 2
constexpr int my_generator(int x) {
    return 2 * x;
}

int main()
{
    static constexpr auto arr = generate_array(range<int, 0, 64>(),
                                               my_generator);

    std::copy(arr.begin(), arr.end(), std::ostream_iterator<int>(std::cout, ", "));
    std::cout << std::endl;
}

here's the code bloat as viewed prior to assembly:

.LC0:
    .string ", "
main:
;; this is the start of the code that deals with the array
    pushq   %rbx
    movl    main::arr, %ebx
.L2:
    movl    (%rbx), %esi
    movl    std::cout, %edi
    addq    $4, %rbx
;; this is the end of it

;; all the rest of this stuff is to do with streaming values to cout
    call    std::basic_ostream<char, std::char_traits<char> >::operator<<(int)
    movl    $2, %edx
    movl    $.LC0, %esi
    movl    std::cout, %edi
    call    std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
    cmpq    main::arr+256, %rbx
    jne     .L2
    movl    std::cout, %edi
    call    std::basic_ostream<char, std::char_traits<char> >& std::endl<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&)
    xorl    %eax, %eax
    popq    %rbx
    ret
    subq    $8, %rsp
    movl    std::__ioinit, %edi
    call    std::ios_base::Init::Init()
    movl    $__dso_handle, %edx
    movl    std::__ioinit, %esi
    movl    std::ios_base::Init::~Init(), %edi
    addq    $8, %rsp
    jmp     __cxa_atexit

main::arr:
    .long   0
    .long   2
    .long   4
    .long   6
    .long   8
    .long   10
    .long   12
    .long   14
    .long   16
    .long   18
    .long   20
    .long   22
    .long   24
    .long   26
    .long   28
    .long   30
    .long   32
    .long   34
    .long   36
    .long   38
    .long   40
    .long   42
    .long   44
    .long   46
    .long   48
    .long   50
    .long   52
    .long   54
    .long   56
    .long   58
    .long   60
    .long   62
    .long   64
    .long   66
    .long   68
    .long   70
    .long   72
    .long   74
    .long   76
    .long   78
    .long   80
    .long   82
    .long   84
    .long   86
    .long   88
    .long   90
    .long   92
    .long   94
    .long   96
    .long   98
    .long   100
    .long   102
    .long   104
    .long   106
    .long   108
    .long   110
    .long   112
    .long   114
    .long   116
    .long   118
    .long   120
    .long   122
    .long   124
    .long   126

i.e. none whatsoever.

Answer 2

I think, your worries about code bloat are misconstrued. Here is a sample:

#include <utility>
#include <array>

template<std::size_t... ix>
constexpr auto generate(std::index_sequence<ix...> ) {
    return std::array<int, sizeof...(ix)>{(ix * ix)...};
}

std::array<int, 3> check() {
 return generate(std::make_index_sequence<3>());
}

std::array<int, 5> glob = generate(std::make_index_sequence<5>());

It produces very neat assembly:

check():
        movl    $0, -24(%rsp)
        movl    $1, -20(%rsp)
        movl    $4, %edx
        movq    -24(%rsp), %rax
        ret
glob:
        .long   0
        .long   1
        .long   4
        .long   9
        .long   16

As you see, no code bloat in sight. Static array is statically initialized, and for automatic array it just a bunch of moves. And if you think bunch of moves is a dreaded code bloat, consider it loop unrolling - which everybody loves!

By the way, there is no other conforming solution. Array is initialized using aggregate initialization at construction time, so elements should either be default constructible or be initialized.