constexpr std::vector and the Compile-Time Heap You Didn't Know Existed

The standard exercise of implementing vector<T> concentrates a lot of C++ into one data structure: placement new, explicit destructor calls, allocation and construction as separate concerns. Quasar Chunawala’s walkthrough on isocpp.org captures this well. But one aspect the exercise rarely touches is whether a custom vector can work in constant expressions.

Since C++20, std::vector is fully usable in constexpr contexts. That sounds contradictory at first. The container allocates heap memory; constant evaluation runs at compile time; those seem fundamentally incompatible. They were incompatible, until a set of C++20 papers resolved each obstacle in sequence.

What Made Allocation Off-Limits

Before C++20, the rules for constant evaluation were clear: no heap allocation. The rationale was that runtime addresses are not meaningful at compile time. Constant evaluation runs inside the compiler’s internal evaluator, which has no persistent heap. Allocating memory during that evaluation would produce a pointer to compiler-internal state that has no well-defined runtime address, and the compiler cannot encode such a pointer into the final binary.

This restriction made owning containers fundamentally non-constexpr. Any container that managed heap memory, including vector and string, could not be used in constexpr functions.

The Transient Allocation Model

P0784R7, adopted for C++20, introduced transient allocation in constant evaluation. The rule: memory may be allocated during constant evaluation provided every allocation is deallocated before the evaluation completes. No live heap pointer may escape into the program binary; the allocation is entirely internal to the compiler’s evaluator and disappears when the evaluation ends.

This is the mechanism that makes constexpr vector possible, and the constraint that defines its limits. A constexpr function can allocate, use, and destroy a vector. It cannot return a live heap pointer to the caller. The allocation must be transient.

The compiler enforces the rule strictly. If any allocation made during constant evaluation remains live at the end, the expression fails to be a constant expression and the compilation produces a diagnostic. The error is not runtime undefined behavior; it is a compile-time rejection.

// Valid: allocation is transient
constexpr int sum_of_squares(int n) {
    std::vector<int> v;
    for (int i = 1; i <= n; ++i)
        v.push_back(i * i);
    int total = 0;
    for (int x : v) total += x;
    return total; // v destroyed here, allocation freed
}

constexpr int result = sum_of_squares(5); // result == 55

// Invalid: allocation would escape
constexpr std::vector<int> bad() {
    return {1, 2, 3}; // ERROR: returned vector holds a live heap pointer
}

The Placement New Problem

Transient allocation is necessary but not sufficient. Construction into pre-allocated memory requires placement new:

::new(static_cast<void*>(ptr)) T(args...);

Placement new is a language construct, not a library function. The compiler’s constant evaluator handles calls to known library functions through special-casing; it does not handle arbitrary pointer casts followed by placement new syntax. Before C++20, no mechanism existed for the compiler to track object construction into raw memory during constant evaluation. Placement new could not appear in a constexpr context.

std::construct_at was added to close this gap. Its signature:

template<class T, class... Args>
constexpr T* construct_at(T* p, Args&&... args);

The function wraps placement new:

template<class T, class... Args>
constexpr T* construct_at(T* p, Args&&... args) {
    return ::new(static_cast<void*>(p)) T(std::forward<Args>(args)...);
}

The standard grants compilers explicit permission to treat calls to std::construct_at as construction operations during constant evaluation, tracking the resulting object as living at the given address within the evaluator’s allocation map. The companion function std::destroy_at handles the symmetric case:

template<class T>
constexpr void destroy_at(T* p);

For a custom vector implementation to work in constexpr contexts, every placement new call must become std::construct_at, and every explicit destructor call must become std::destroy_at:

// Not constexpr-compatible
::new(static_cast<void*>(begin_ + size_)) T(value);
(begin_ + i)->~T();

// Constexpr-compatible (C++20)
std::construct_at(begin_ + size_, value);
std::destroy_at(begin_ + i);

The allocation path also needs attention. In C++20, std::allocator<T>::allocate and deallocate are constexpr, and the compiler intercepts these calls during constant evaluation to route them through its internal allocation tracking. Routing allocation through std::allocator_traits<std::allocator<T>> rather than ::operator new directly ensures the compiler can handle the calls correctly. Custom allocators without constexpr-marked allocate and deallocate methods do not work in constexpr contexts.

Using Vector as Compile-Time Scratch Space

The transient constraint shapes how constexpr vector is used in practice. The pattern is using a vector as an intermediate data structure to compute a result, then returning that result as a fixed-size type that can survive the end of evaluation:

template<std::size_t N>
constexpr std::array<int, N> first_primes() {
    std::vector<bool> sieve(N * 15 + 50, true);
    sieve[0] = sieve[1] = false;
    for (int i = 2; (long long)i * i < (int)sieve.size(); ++i)
        if (sieve[i])
            for (int j = i * i; j < (int)sieve.size(); j += i)
                sieve[j] = false;

    std::array<int, N> result{};
    std::size_t count = 0;
    for (int i = 2; count < N; ++i)
        if (sieve[i]) result[count++] = i;
    return result;
}

constexpr auto primes = first_primes<20>(); // evaluated at compile time

The vector<bool> grows dynamically as the sieve runs. The returned std::array<int, N> is a fixed-size aggregate with no heap pointer. The sieve’s destructor runs before first_primes returns, releasing the allocation and satisfying the transient constraint.

This pattern has practical uses. Precomputed lookup tables, sorted arrays of constants, character classification masks, and hash seeds are all candidates for consteval computation using vectors as intermediate accumulators. The alternative, generating these by hand or with external scripts, requires maintaining separate tooling and produces values that cannot be verified by re-running the generating code as part of the build.

The Limits

constinit std::vector is not possible. constinit guarantees that a variable is initialized at compile time, which for a non-empty vector would require the heap allocation to survive into the running program. That violates the transient allocation rule. An empty vector has no allocation to worry about, but a zero-element constinit vector is rarely useful.

Compiler step limits constrain how much computation is feasible. Clang enforces a step count via -fconstexpr-steps (defaulting to around one million operations); GCC uses -fconstexpr-ops-limit. A computation over a few hundred elements is generally fine. A large sort over ten thousand elements may hit the limit, and the error message referencing “constexpr evaluation hit maximum step limit” can be confusing if you are not expecting it.

The underlying constant evaluator also enforces a stricter provenance model than the runtime. Writes during constant evaluation may only target objects constructed during that evaluation; writing through a pointer to external memory is rejected at compile time even if it would be well-defined at runtime. A constexpr function that tries to write through a reinterpret-cast pointer, or one obtained from a source the evaluator did not allocate, will fail to compile.

What a Custom Implementation Needs

std::vector’s constexpr support required making every method constexpr-qualified, replacing every placement new with std::construct_at, and ensuring that the reallocation path handles a failed allocation correctly during constant evaluation. At compile time, a failed std::allocator_traits::allocate terminates the evaluation as a non-constant expression rather than throwing to the caller, so the exception machinery that normally handles std::bad_alloc has a different shape at compile time than at runtime.

For a homegrown vector that aims to match this, the changes are mechanical but require attention to every site in the implementation that touches construction or destruction. std::construct_at and std::destroy_at throughout, constexpr on all member functions, and allocation routed through std::allocator_traits with std::allocator. The libc++ vector source reflects these additions directly and reads naturally alongside P0784R7 to see how the specification maps to implementation choices.

Constexpr vector is not a bolt-on feature. It is the same allocation and construction model as the rest of the container, applied to a stricter evaluator with a mandatory cleanup requirement. The implementation exercise from Chunawala’s article builds exactly the foundation you need to understand why each piece of this works the way it does.