Fixed-capacity containers: no hidden allocations

A console game renders a frame every 16.6 ms. A call to malloc usually takes tens of nanoseconds — and occasionally takes a lock, walks a free list or asks the OS for pages, and takes much longer. Worse, years of allocate-and-free in a long-running process fragment the heap until a large allocation fails with plenty of memory nominally free. Embedded firmware often has no heap at all.

That is the environment Electronic Arts wrote EASTL for. Its design notes are blunt about the standard library of the time: implementations had "inferior performance characteristics that make them unsuitable for game development", and "All existing versions of STL allocate memory in empty versions of at least some of their containers." EASTL's rules: "Newly constructed empty containers do no memory allocation", and no algorithm allocates behind your back. (EASTL doc/Design.md; Paul Pedriana, EASTL — Electronic Arts Standard Template Library, WG21 N2271, 2007.)

This skill is about the containers that grew out of that: storage inside the object, a fixed budget decided up front, and — sometimes — a controlled escape hatch to the heap.

1. Where the elements live

A std::vector is three words; its elements are always on the heap. A fixed-capacity container carries a buffer for N elements inside itself, so sizeof grows with N — on the stack, in a struct, in an array of structs, the elements come along for free:

#include <array>
#include <inplace_vector>
#include <print>
#include <vector>

int main() {
    std::println("vector<int>:            {} bytes", sizeof(std::vector<int>));
    std::println("inplace_vector<int, 8>: {} bytes", sizeof(std::inplace_vector<int, 8>));
    std::println("array<int, 8>:          {} bytes", sizeof(std::array<int, 8>));
}

std::inplace_vector (C++26, from the flat containers skill) is the standard's take on EASTL's fixed_vector<T, N, false>: capacity fixed at N, never allocates; push_back on a full one throws std::bad_alloc, try_push_back returns an empty optional.

2. Three policies for "full"

What should a fixed container do when element N + 1 arrives? There is no universally right answer — so name the policy instead of hiding it:

The overflow policy is what this skill's build implements. The common case (≤ N elements) costs zero allocations; the rare case is a normal vector. EASTL even lets you choose which allocator the overflow uses.

The real thing: EASTL's fixed containers

EASTL is installed here, so you can try its versions directly. The third template argument of fixed_vector is the overflow switch; has_overflowed() tells you whether the budget was ever exceeded — exactly the number a memory tracker wants:

#include <EASTL/fixed_string.h>
#include <EASTL/fixed_vector.h>
#include <cstdio>

int main() {
    eastl::fixed_vector<int, 4, true> v;  // 4 inline slots, overflow allowed
    for (int i = 0; i < 4; ++i) v.push_back(i);
    std::printf("size %zu, overflowed %d\n", v.size(), int(v.has_overflowed()));
    v.push_back(4);                       // the fifth goes to the overflow allocator
    std::printf("size %zu, overflowed %d\n", v.size(), int(v.has_overflowed()));

    eastl::fixed_string<char, 32, false> name = "player_one";  // no overflow: 31 chars max
    name += "_respawned";
    std::printf("%s (%zu chars)\n", name.c_str(), name.size());
}

3. The self-pointer, and why moves get harder

The simplest small vector keeps data_ pointing at wherever the elements are — the inline buffer or the heap — so every accessor is one pointer away, exactly like std::vector:

template <class T, std::size_t N>
class SmallVector {
    T* data_;                                     // → buffer_ or the heap
    std::size_t size_ = 0, cap_ = N;
    alignas(T) std::byte buffer_[N * sizeof(T)];  // raw memory: no T objects yet
    bool is_inline() const { return data_ == reinterpret_cast<const T*>(buffer_); }
};

buffer_ is raw bytes: elements are created with std::construct_at and ended with std::destroy_at, exactly as in your own Vec. A T buffer_[N] would default-construct N elements up front — wrong for types with no default constructor, and wasteful for the rest.

The pointer into itself is the trap. A std::vector move is three pointer swaps. A small vector's move can only steal a heap buffer. If the source is inline, its elements live inside the source object, which is about to be destroyed — there is nothing to steal:

#include <memory>
#include <print>
#include <string>
#include <utility>
#include <vector>

// Count moves of the element type.
struct Item {
    static inline int moves = 0;
    std::string name;
    explicit Item(std::string n) : name(std::move(n)) {}
    Item(Item&& o) noexcept : name(std::move(o.name)) { ++moves; }
};

int main() {
    std::vector<Item> v;
    v.reserve(3);
    for (auto n : {"a", "b", "c"}) v.emplace_back(n);
    Item::moves = 0;
    std::vector<Item> w = std::move(v);  // steals the heap buffer
    std::println("vector move: {} element moves", Item::moves);
}

Moving a heap-backed vector: zero element moves. Moving an inline small vector: one move per element, O(n) — and copying the pointer instead would leave the destination pointing into a dead object. Same story for std::string's small-string optimisation (SSO): short strings are stored in the string object itself, so moving one copies the characters.

4. Small-buffer optimisation everywhere

The pattern — a little inline storage, a heap fallback — shows up in many places, often invisibly:

• std::string: SSO keeps short strings in the object (libstdc++: 15 chars; the exact size is an implementation detail, never something to rely on). EASTL adds fixed_string<char, N, bEnableOverflow>.
• std::function: small callables are stored inline; a lambda capturing a lot is heap-allocated. EASTL's fixed_function<SizeInBytes, Sig> turns that into a compile error instead: the callable must fit.
• std::any, many small_vector / SmallVector / absl::InlinedVector implementations.

The cost is always the same: a bigger object, and moves that copy the inline part.

5. Fixed node pools: lists and maps that never call malloc

std::list and std::map allocate one node per element. EASTL's fixed_list<T, N>, fixed_map, fixed_hash_map instead carry a pool of N nodes inside the container, linked into a free list:

#include <EASTL/fixed_list.h>
#include <cstdio>

int main() {
    eastl::fixed_list<int, 8, false> live;  // a pool of 8 nodes inside the object
    for (int i = 0; i < 8; ++i) live.push_back(i);
    std::printf("full: %d\n", int(live.full()));
    live.remove(3);                         // node 3 goes back to the free list
    live.push_back(42);                     // ...and comes straight back out
    for (int x : live) std::printf("%d ", x);
    std::printf("\n");
}

Insert and erase are O(1) pointer moves on the free list — no locks, no fragmentation, and every node sits in one contiguous block (good locality for iteration). The design notes describe the trick: the fixed containers are "subclasses of regular containers which set the regular container's allocator to point to themselves". The cost of that design — one pointer from the container back into itself — is the same self-reference you met in section 3.

6. Allocators as a per-container object

Standard allocators are part of the type: std::vector<int, Arena<int>> and std::vector<int> are different types, and the allocator is rebound internally to whatever node type the container really needs. EASTL went the other way: one untyped allocator interface (allocate(n, flags), deallocate(p, n)), stored in each container, with a name — so a memory tracker can report "AI/pathfinding: 3.2 MB" per subsystem, and a container can be pointed at a different arena at run time. "Swapped containers do not swap their allocators."

C++17's std::pmr (the allocators skill) arrived at a similar place: std::pmr::vector<T> holds a memory_resource* per object, and every pmr container shares one type regardless of the resource behind it.

7. Choosing

• Known small maximum, overflow is a bug → std::inplace_vector (or std::array + a count).
• Usually small, occasionally large → small vector with heap overflow.
• Many objects allocated and freed per frame → a pool (fixed node pool, free list, arena) sized for the frame.
• Everything else → std::vector. A small vector is bigger, and its moves are O(n); don't put one where a plain vector will do.

The build

Write SmallVector<T, N>: inline storage for N elements, a heap buffer beyond that, correct moves for both states, the strong guarantee when growth throws, and shrink_to_fit back into the inline buffer. The tests count allocations, so "no allocation while it fits" is checked, not hoped.