I proposed several techniques to answer to https://stackoverflow.com/q/78672409/21691539.
A classical way to answer would be to use std::index_sequence-based solution but op had two constraints:
- it should work with a non default-constructible type
- it should work for large
std::arraysizes, larger than what commonstd::index_sequenceimplementations are supporting.
This one is a second version (the first one is here: Presence of UB and memory usage of a std::array initialization) that uses a dynamically allocated array of bytes as a temporary storage.
Following advices given for the static version, I added specialization according to the default constructability and the trivial destructibility of the stored objects.
// creates an std::array<T, N> whose element i is constructed with gen(i)
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);
}
}
Live with sanitizer
Live without sanitizer
Live without sanitizer, nor string
The idea is to allocate a raw storage, construct the objects in place, alias the storage to an std::array<T,N> and "move-initialize" the created array from the aliased one (see full example below). The temporary resource is released on leaving the creator function (objects are deleted).
The heap-allocated storage is managed by a std::unique_ptr with, if necessary, a custom deleter that will destroyed non-trivially-destructible objects before releasing the storage.
I have several concerns regarding this code.
The first one is: it is UB? I believe not (see discussion there but I'm unsure).
The second one is: what is it's footprint? Honestly I didn't profile it properly, neither with respect to execution time (as I couldn't compare to the std::index_sequence-based solution which does not compile at all), nor with respect to memory usage (I believe I've got an overhead of one array).
The third one is the stack usage. For instance I had to increase stack size for msvc. But it's due principally to the array in main. As noted by @G.Sliepen, using a stack std::array for so many objects is debatable (but I was originally answering someone else requirement, see first link above).
Eventually would there be ways to improve this design?
Here is a full example, similar to the compiler explorer links above:
#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);
}
