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.
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)...
