Flexible array member replacement for constexpr context

Question

I want an array of objects prefixed with size/capacity. My requirements are:

1. The array elements should to be constructed on demand, like std::vector.
2. This object itself will be shared (i.e., heap allocated), so using std::vector instead would imply 2 levels of indirection and 2 allocations, which I have to avoid.

Requirements up to this point are non-negotiable. Here's my sample to get the rough idea of what I'd do:

#include <cassert>
#include <cstdio>
#include <string>

template <class T>
struct Array {
   private:
    int size_;
    int capacity_;
    alignas(T) unsigned char data_[];

    Array() = default;

   public:
    Array(Array const&) = delete;
    Array& operator=(Array const&) = delete;

    static auto newArr(int capacity) {
        auto p = new unsigned char[sizeof(Array) + capacity * sizeof(T)];
        auto pObj = new (p) Array;
        pObj->size_ = 0;
        pObj->capacity_ = capacity;
        return pObj;
    }

    static auto deleteArr(Array* arr) {
        if (!arr) return;
        for (int i = 0; i != arr->size_; ++i) arr->get(i).~T();
        arr->~Array();
        delete[] reinterpret_cast<unsigned char*>(arr);
    }

    auto& get(int index) {
        return reinterpret_cast<T&>(data_[index * sizeof(T)]);
    }

    auto push_back(T const& t) {
        assert(size_ < capacity_);
        new (&get(size_++)) T(t);
    }
};

int main() {
    auto arr = Array<std::string>::newArr(5);
    for (int i = 0; i != 3; ++i) {
        arr->push_back(std::to_string(i));
    }
    for (int i = 0; i != 3; ++i) {
        std::printf("arr[%d] = %s\n", i, arr->get(i).c_str());
    }
    Array<std::string>::deleteArr(arr);
}

It uses a flexible-array-member, which is an extension and that's OK by me (works in GCC and clang? then it's OK). But it is not constexpr friendly because it necessarily uses:

1. placement new, not allowed in constexpr context for some reason, even though that's surely what allocators do. We can't replace it with an allocator because they don't support the flexible array member trick.
2. reinterpret_cast to access the elements as T and to free the memory at the end.

My question: How do I satisfy the previously mentioned requirements and keep the class constexpr friendly?

Answer 1

Here's another approach. I've used unions to make it possible for subobjects of a single array object to have different types and different lifetimes. I'm not entirely sure if everything's strictly legal, but the major compilers don't complain.

I did need to have newArr return an object rather than pointer. If that's not an issue, it would probably make more sense to just give FlexArray an actual constructor and destructor.

#include <memory>
#include <cassert>

template <typename T>
class FlexArray
{
public:
    FlexArray(const FlexArray&) = delete;
    FlexArray& operator=(const FlexArray&) = delete;

    static constexpr FlexArray newArr(unsigned int capacity);
    constexpr void deleteArr();
    constexpr unsigned int size() const;
    constexpr unsigned int capacity() const;
    constexpr T& get(unsigned int index);
    constexpr void push_back(T const& obj);

private:
    struct Header {
        unsigned int size;
        unsigned int capacity;
    };
    static constexpr auto T_per_node =
    (sizeof(T) < sizeof(Header)) ? sizeof(Header)/sizeof(T) : 1U;
    union MaybeT {
        unsigned char dummy;
        T obj;

        constexpr MaybeT() {}
        explicit constexpr MaybeT(const T& src) : obj(src) {}
        constexpr ~MaybeT() {}
    };
    union U {
        Header head;
        MaybeT data[T_per_node];
        constexpr U() : data{} {}
        constexpr ~U() {}
    };

    U* nodes;
    explicit constexpr FlexArray(U* n) : nodes(n) {}
};

template <typename T>
constexpr FlexArray<T> FlexArray<T>::newArr(unsigned int capacity)
{
    auto new_nodes = new U[1 + (capacity + (T_per_node-1))/T_per_node];
    new_nodes[0].head = {0, capacity};
    return FlexArray{new_nodes};
}

template <typename T>
constexpr void FlexArray<T>::deleteArr()
{
    unsigned int i = size();
    while (i--) {
        get(i).~T();
    }
    delete[] nodes;
    nodes = nullptr;
}

template <typename T>
constexpr unsigned int FlexArray<T>::size() const
{
    return nodes[0].head.size;
}

template <typename T>
constexpr unsigned int FlexArray<T>::capacity() const
{
    return nodes[0].head.capacity;
}

template <typename T>
constexpr T& FlexArray<T>::get(unsigned int index)
{
    return nodes[1 + index / T_per_node].data[index % T_per_node].obj;
}

template <typename T>
constexpr void FlexArray<T>::push_back(const T& obj)
{
    assert(size() < capacity());
    auto index = nodes[0].head.size++;
    MaybeT *addr = nodes[1 + index / T_per_node].data + (index % T_per_node);
    addr->~MaybeT();
    std::construct_at(addr, obj);
}

#include <functional>

constexpr int test()
{
    int a = -1;
    int b = 2;
    int c = 5;
    auto arr = FlexArray<std::reference_wrapper<int>>::newArr(3);
    arr.push_back(std::ref(a));
    arr.push_back(std::ref(b));
    arr.push_back(std::ref(c));
    arr.get(1).get() = 7;
    auto sum = arr.get(0) + b + arr.get(2);
    arr.deleteArr();
    return sum;
}

static_assert(test() == 11);

See it on godbolt.

Answer 2

Considering @NicolBolas's answer, this can't be done as is, but if you can afford an indirection, it can be done. You do separate allocations if the object is constructed at compile-time where performance concern doesn't exist, and do the single-allocation + reinterpret_cast trick if constructed at runtime:

#include <cassert>
#include <new>
#include <type_traits>
#include <memory>

template <class T>
struct ArrayData {
   protected:
    int size_ = 0;
    int capacity_ = 0;
    T *buffer;
};

template <class T>
struct alignas(std::max(alignof(T), alignof(ArrayData<T>))) Array
    : ArrayData<T> {
   private:
    constexpr Array() = default;
    using alloc = std::allocator<T>;
    using alloc_traits = std::allocator_traits<alloc>;

   public:
    Array(Array const &) = delete;
    Array &operator=(Array const &) = delete;

    constexpr static auto newArr(int capacity) {
        if (std::is_constant_evaluated()) {
            auto arr = new Array<T>();
            alloc a;
            T *buffer = alloc_traits::allocate(a, capacity);
            arr->capacity_ = capacity;
            arr->buffer = buffer;
            return arr;
        } else {
            auto p = new unsigned char[sizeof(Array) + capacity * sizeof(T)];
            auto pObj = new (p) Array;
            pObj->capacity_ = capacity;
            pObj->buffer = std::launder(reinterpret_cast<T *>(pObj + 1));
            return pObj;
        }
    }

    constexpr static auto deleteArr(Array *arr) noexcept {
        if (!arr) return;

        auto p = arr->buffer;
        for (int i = 0, size = arr->size_; i != size; ++i)
                std::destroy_at(p + i);

        if (std::is_constant_evaluated()) {
            auto capacity = arr->capacity_;
            delete arr;
            alloc a;
            alloc_traits::deallocate(a, p, capacity);
        } else {
            arr->~Array();
            delete[] reinterpret_cast<unsigned char *>(arr);
        }
    }

    constexpr auto &get(int index) { return this->buffer[index]; }

    constexpr auto push_back(T const &t) {
        assert(this->size_ < this->capacity_);
        std::construct_at(this->buffer + this->size_++, t);
    }
};

constexpr int test() {
    auto const size = 10;
    auto arr = Array<int>::newArr(size);

    for (int i = 0; i != size; ++i) arr->push_back(i);

    int sum = 0;
    for (int i = 0; i != size; ++i) sum += arr->get(i);

    Array<int>::deleteArr(arr);
    return sum;
}

int main() {
    int rt = test();
    int constexpr ct = test();
    return rt == ct;
}

Answer 3

Ultimately, what you're trying to do is create a contiguous series of objects in unformed memory that isn't defined by a single, valid C++ struct or by a C++ array of Ts. Constexpr allocations cannot do that.

You can allocate a byte array in constexpr code. But you cannot subsequently do any of the casting that normal C++ would require in order to partition this memory into a series of objects of different types. You can allocate storage suitable for an array of Array<T> objects. Or you can allocate storage suitable for an array of T objects. But std::allocator<T>::allocate will always return a T*. And constexpr code doesn't let you cast this pointer to some other, unrelated type.

And without being able to do this cast, you cannot later call std::construct_at<T>, since the template parameter T must match the pointer type you give it.

This is of course by design. Every constexpr allocation of type T must contain zero or more Ts. That's all it can contain.