3

Is it possible to implement a constexpr static_vector?

By static_vector, I mean a vector which has its storage space inside the vector (not heap allocated) and it cannot grow beyond the compile-time CAPACITY. Something like this:

template <typename T, int CAPACITY>
struct static_vector {
    unsigned char data[sizeof(T)*CAPACITY];
    int size = 0;

    template <typename ...PARAMETERS>
    constexpr void emplace_back(PARAMETERS &&...parameters) {
        new(data + size * sizeof(T)) T(std::forward<PARAMETERS>(parameters)...);
        size++;
    }

    constexpr const T &operator[](int idx) const {
        return std::launder(reinterpret_cast<const T *>(data))[idx];
    }
};

(hopefully this implementation is UB-free).

If I try to use this implementation, I get various constexpr-related errors. Here is a little test program (godbolt):

struct Foo {
    int x;

    constexpr Foo(int x) : x(x) { }
};

constexpr int fn() {
    static_vector<Foo, 3> a;
    a.emplace_back(1);
    a.emplace_back(2);
    return a[0].x + a[1].x;
}

int main() {
    constexpr int v = fn();
    printf("%d\n", v);
}

As far as I know, it is possible to do this if heap allocated storage is used. The question is, is it possible to do this using an "embedded" space, like static_vector does? I know that this is not possible with older standards, but are we going to have something in the next standard which makes this possible?

(I also tried to implement this using a union, but it fails in a different way)

Improve this question
12
  • 9
    std::inplace_vector Commented Nov 4, 2024 at 20:05
  • @NathanOliver: thanks, I didn't know about this. I think this quote answers my question: "If N > 0 and std::is_trivial_v<T> is false, then member functions of inplace_vector are not usable in constant expressions.". Commented Nov 4, 2024 at 20:08
  • 3
    If someone else is interested, this is the proposal: wg21.link/P0843 Commented Nov 4, 2024 at 20:11
  • One current (in 2024) disadvantage of std::inplace_vector is that it is proposed for C++26. So, most current implementations do not support it, and there is still potential that it will not make it into the standard. Commented Nov 4, 2024 at 22:53
  • There are various similar solutions like boost::container::static_vector, boost::container::small_vector, llvm::SmallVector, folly::small_vector, eastl::fixed_vector although I haven't check if any of them can be constexpr Commented Nov 5, 2024 at 1:00

1 Answer 1

Reset to default
6

Is it possible to implement a constexpr static_vector?

As of what's in the language for C++26 so far, not completely no.

You need to provide storage for the backing array, and you need to be able to construct and retrieve objects from there. What are our options?

We could use an array of unsigned char:

alignas(T) unsigned char a1[sizeof(T[N])];

But this requires reinterpret_cast to get an object back out, and we can't reinterpret_cast at compile time.

We could directly construct an array:

T a2[N];

But this requires us to actually construct N objects. You definitely do not want to do that if T isn't trivially default constructible — because initially you want your vector to be empty. It doesn't matter here if we use T[N] or std::array<T, N>, although the latter just directly supports N == 0.

We could stash our array in a union:

union { T a3[N]; };

The problem with a3 is that the only way to actually start the lifetime of a3 and use the array like an array is... to construct the whole array. Which has the same problem as a2 again. And if we don't start the lifetime of a3 then none of the array operations work.

Or we could try to do an array of a union:

union U { T val; };
U a4[N];

The problem with this is that you have APIs that return a T* that actually has to be a pointer to T that you can do pointer arithmetic on, not a T inside of a union.

That's why the current design for std::inplace_vector<T, N> contains this sentence:

For any N>0, if is_trivial_v<T> is false, then no inplace_vector<T, N> member functions are usable in constant expressions.

Because because if is_trivial_v<T> is true then constructing a2 is fine (that's the direct T[N] version) — no initialization happens, and now we have a proper array that all the compile time evaluation can deal with easily enough.

I have a proposal in flight that will hopefully land in C++26 that will allow the union solution to work for all T, by ensuring that the language starts the lifetime of a3 (the union { T[N] } version) without having to initialize the whole array. That will make it possible to have a completely constexpr static_vector, which is why that paper also strikes the sentence I cited earlier.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thanks for this work! I skimmed through the versions, I'm not sure whether this option was considered... I've never understood why union U { std::string z; } doesn't work in the first place (I mean the def. ctor is deleted). Why does C++ want to initialize unions so hard? I use union for the purpose of postponing the initialization. In this case, the default ctor/dtor should be trivial instead of deleted. And we should have a mechanism to switch between active members, it is your std::start_lifetime idea. But I understand that this is inconsistent with some of the already existing rules.
Personally, I like the trivial union variant the best. But without the "first alternative's lifetime is started" special case. trivial union should mean that the def. ctor/dtor is always trivial. With the usual way we can make a member active. And in case we want to make an array member active, but without calling the ctor's of the array elements, we need std::start_lifetime.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.