Home > front end >  Flexible array member replacement for constexpr context
Flexible array member replacement for constexpr context

Time:03-01

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?

CodePudding user response:

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.

CodePudding user response:

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;
}
  • Related