Suppose I have a function T foo(size_t i). What would be an elegant and succinct way of constructing an object arr, of type std::array<T, N>, so that we have arr[i] == foo(i)?
If possible, I would like for this construction to work even when T is not a default-initializable type.
Notes:
T is not default-initializable, the code can't start with std::array<T, N> arr; and then some initialization.N, generically.You could implement a helper function template:
template<std::size_t N, typename Generator>
auto generate_array(Generator gen) -> std::array<decltype(gen(0)), N>;
using some template metaprogramming voodoo:
namespace detail {
template<typename T, std::size_t... Is, typename Generator>
auto generate_array(std::index_sequence<Is...>, Generator gen)
-> std::array<T, sizeof...(Is)>
{
return std::array<T, sizeof...(Is)>{ gen(Is) ... };
}
} // namespace detail
template<std::size_t N, typename Generator>
auto generate_array(Generator gen) -> std::array<decltype(gen(0)), N>
{
return detail::generate_arr<decltype(gen(0))>(
std::make_index_sequence<N>{}, std::forward<Generator>(gen));
}
(this uses a technique known as the "indices trick".)
If you write:
auto gen = [](std::size_t i) { return 11*(i+1); };
auto arr = generate_array<5>(gen);
for(auto i : arr) { std::cout << i << ' ';}
std::cout << '\n';
the program should produce:
11 22 33 44 55
And you can see it in action on GodBolt.
std::index_sequence; if you implement it yourself in C++11, you can adapt the generator function and have a pure-C++11 solution.N of 500,000 may well fail.std::array of constant values.detail::generate_array() as a templated lambda inside the "outer" generate_array().N, it is limited by the implementation limit of template instantiations. godbolt.org/z/TzEvdTs89 –
Spenser N. –
Spenser arr in the lambda and the lambda is used as the initializer for arr. Edit: Sorry I missed your emoji. –
Spenser 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 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:
std::unique_ptr;std::array and Int (copy or move);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)...
std::align_val_t(alignof(Int)) to new but I'm unsure. I don't find the doc really clear. Notice that std::aligned_alloc is not suitable as it does not start objects lifetime. –
Zinc N, than succeeding only to be hit by the UB or the extra construction, in some oblique and surprising way at some point down the line. –
Amagasaki std::move *reinterpret_cast<std::array<T, N>*>(p.get() + Offset) –
Zinc std::array is the same as a plain array (aggregate type and so on). But I'm far from being sure of that. A [language-lawyer] would be necessary. –
Zinc © 2022 - 2024 — McMap. All rights reserved.
doubletoGeneratorandptop(I)it starts working. Here is the demo after doing the changes. Also the answer is just a copy of the answer in the dupe with some minor rephrasing. – OlenN" due to limits related to templates in the implementation, as I have already pointed out in the comment in the only answer so far. The other obvious option, which is constructing a local array from a lambda and returning it to initialize the actual array, works forconstarray cases but not when the type is not default-constructible. So there are solutions that is specific to the question here to address that issue. I don't agree it's a dupe. – Spenser::operator newand take advantage of the fact that arrays are implicit lifetime to create a local array in a lambda, then returning it. This requires C++20 though. – Spenserstd::array– Zincstd::arrayitself is implicit lifetime (I suppose it is). On the other hand, I have tried to construct a plain array as you described and convert it usingstd::to_array, but I'm surprised to see thatstd::to_arrayhas the same limitation forNlikestd::index_sequence, I had thought that the implementation can do it via intrinsics without relying onstd::index_sequence. – Spenserstd::arrayis also. I could go with that but it's unsurprisingly leaking. It may work only if your keeping a smart pointer tostd::arrayinstead of a plain one. Maybe it's possible to improve on that. I don't see for now Besides it won't work in constant initialization context. – Zincstd::arraythat is initialized from yourreinterpret_castresult, deallocate the buffer in the lambda, then return the localstd::array. This will result in extra copy and/or moves, but fixes the leak (except when the constructor ofTthrows). I don't see how it can be done in a better way either. Also I'm not sure whether you need tostd::launderthe pointer in the lambda. – Spensernew), that is sad. You may consider posting it as an answer (after fixing the alignment issue), and list the caveats you mentioned in the answer. – Spenserstd::stringseems to have issues. – Spenser