Intrusive and structure-of-arrays containers

The standard containers make two decisions for you: they own their elements (a std::list allocates a node and copies or moves your object into it), and they store each element as one object (a std::vector of structs puts each struct's fields side by side). Game engines, kernels and databases routinely want the opposite of one or both. EASTL — EA's standard-library replacement — ships a toolbox for exactly that: its design notes list "useful extensions that game programmers find useful (e.g. intrusive_list)" among the reasons it exists (EASTL doc/Design.md; WG21 N2271). This skill walks through that toolbox: what each container is, what it costs, and when it pays.

1. Intrusive lists: the link lives in the object

With an intrusive list the element carries its own prev/next (a hook), usually by deriving from a node type. Consequences:

• No allocation to insert or remove — the memory is already there.
• O(1) removal from the element: given an Enemy&, you can unlink it without searching, because it knows its neighbours. With std::list<Enemy*> you'd need to find (or remember) the node first.
• Several lists at once: give the type one hook per membership. Tags tell them apart:

#include <print>

template <class Tag>
struct Hook {
    Hook* prev = this;
    Hook* next = this;
};

struct Active {};
struct Render {};

struct Enemy : Hook<Active>, Hook<Render> {
    int id;
    explicit Enemy(int i) : id(i) {}
};

// Link e after `at` in the list for Tag.
template <class Tag>
void link_after(Hook<Tag>& at, Enemy& e) {
    Hook<Tag>& h = e;
    h.prev = &at;
    h.next = at.next;
    at.next->prev = &h;
    at.next = &h;
}

template <class Tag>
void print_list(Hook<Tag>& head) {
    for (Hook<Tag>* p = head.next; p != &head; p = p->next)
        std::print("{} ", static_cast<Enemy*>(p)->id);  // downcast: p is a hook inside an Enemy
    std::println();
}

int main() {
    Hook<Active> active;
    Hook<Render> visible;
    Enemy a(1), b(2), c(3);
    link_after(active, a);
    link_after(active, b);
    link_after(active, c);
    link_after(visible, b);
    print_list(active);   // 3 2 1  (each insert goes at the front)
    print_list(visible);  // 2
}

static_cast<Enemy*>(hook) is a well-defined downcast because the hook really is a base subobject of an Enemy. (C code does the same with container_of and an offset; with member hooks in C++ that offset arithmetic is on shaky ground — base-class hooks keep it clean.)

EASTL's intrusive_list is the same design: derive from intrusive_list_node, and the list threads through it.

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

struct Enemy : eastl::intrusive_list_node {
    int id;
    explicit Enemy(int i) : id(i) {}
};

int main() {
    Enemy a(1), b(2), c(3);
    eastl::intrusive_list<Enemy> active;
    active.push_back(a);
    active.push_back(b);
    active.push_back(c);
    active.remove(b);  // O(1): b knows its neighbours
    for (const Enemy& e : active) std::printf("%d ", e.id);
    std::printf("(size walks the list: %zu)\n", active.size());
    active.clear();    // unlink before the Enemies go out of scope
}

The price is ownership: the list doesn't own its elements, and an element destroyed while linked leaves its neighbours pointing at freed memory. Either make "unlink before destroy" a rule, or give the hook a destructor that unlinks (a "safe" or auto-unlink hook) — one branch per destruction. And because an element can unlink itself without telling the list, the list can't cheaply keep a count: EASTL's notes say caching the size of an intrusive list "would do additional harm". size() walks.

intrusive_ptr is the same idea for reference counting: the count lives in the object (add_ref/release hooks), so a pointer is one word and intrusive_ptr<T> can be rebuilt from a raw T* — unlike shared_ptr, whose control block is separate.

2. Sorted vectors as maps: vector_map, vector_set

EASTL's vector_map<K, V> is a std::vector<std::pair<K, V>> kept sorted by key, with a map interface. Lookups are a binary search over contiguous memory; inserts and erases shift elements (O(n)). It is the same trade as C++23's std::flat_map (the flat containers skill), with one layout difference:

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

int main() {
    eastl::vector_map<int, const char*> names;
    names.insert({30, "cy"});
    names.insert({10, "ana"});
    names.insert({20, "bo"});
    for (auto& [id, name] : names) std::printf("%d=%s ", id, name);  // real pairs, sorted
    std::printf("| find(20) -> %s\n", names.find(20)->second);
}

Large values → flat_map's split layout searches faster. Code that needs real pair&s (to pass to existing APIs) → vector_map. Both: build once, sort once, then mostly read. vector_multimap keeps duplicates in insertion order (insert at upper_bound).

3. Structure of arrays: tuple_vector

An array of structs (AoS) stores each object's fields together; a structure of arrays (SoA) stores each field in its own array:

When a loop touches one or two fields of many objects, SoA reads only those bytes — less memory traffic, and contiguous same-typed data the compiler can vectorise (the data-oriented design skill measured this). EASTL's tuple_vector<Ts...> gives SoA a vector interface: push_back(x, y, z, alive), get<0>() returns the whole x array, and all arrays live in one allocation, carved into consecutive regions — one malloc instead of four, and growth moves everything together.

#include <cstddef>
#include <print>

struct ParticleAoS {
    float x, y, z;
    bool alive;
};

int main() {
    constexpr std::size_t n = 1000;
    // Bytes a loop over every particle's x has to bring in, at least:
    std::println("AoS: {} bytes (whole structs)", n * sizeof(ParticleAoS));
    std::println("SoA: {} bytes (just the x array)", n * sizeof(float));
}

With EASTL's tuple_vector, each field is its own contiguous array, all carved out of one allocation:

#include <EASTL/bonus/tuple_vector.h>
#include <cstdio>

int main() {
    eastl::tuple_vector<float, float, bool> particles;  // x, vx, alive
    for (int i = 0; i < 4; ++i) particles.push_back(float(i), 0.5f, i % 2 == 0);

    float* x = particles.get<0>();
    const float* vx = particles.get<1>();
    for (eastl_size_t i = 0; i < particles.size(); ++i) x[i] += vx[i];  // touches two arrays only

    for (auto [px, pvx, alive] : particles) std::printf("%.1f%s ", px, alive ? "" : "(dead)");
    std::printf("\n");
}

The costs: one object is now scattered across arrays (p.x becomes xs[i]), adding or removing an element touches every array, and there's no Particle& to hand to a function — you pass indices or proxies.

4. Segmented vectors: stable addresses, chunked growth

std::vector reallocates when it grows, so every pointer, reference and iterator into it dies. A segmented vector (EASTL's segmented_vector<T, Count>) allocates fixed-size segments and never moves an element: growth adds a segment. Indexing is segments[i / Count][i % Count] (cheap when Count is a power of two); iteration is nearly as fast as a vector's.

#include <deque>
#include <print>

int main() {
    std::deque<int> d;           // a segmented structure in the standard library
    d.push_back(1);
    int* first = &d[0];
    for (int i = 0; i < 10'000; ++i) d.push_back(i);
    std::println("{}", *first);  // still valid: push_back at the ends never moves elements
}

std::deque is a segmented container too, but with a big constant overhead in many implementations and blocks you can't size. A segmented vector with a chosen segment size is a good home for objects other things point to — like the elements of an intrusive list.

5. The rest of the toolbox

• bitvector: one bit per bool, with a proxy reference type — the honest version of std::vector<bool>. count() is a popcount per 64-bit word. Watch the last, partial word: bits past size() must stay zero.
• ring_buffer<T, Container>: a circular adaptor over a container; pushing onto a full ring overwrites the oldest element. Great for "the last N frames of input".
• linked_ptr: shared ownership without a control block — the owners of one object form a circular list, and the last one out deletes. No allocation, but O(1) work spread across copies and not thread-safe.
• fixed_* containers — the previous skill.

6. Choosing

The build

Write IntrusiveList<T, Tag> with ListHook<Tag>: base-class hooks with tags, a sentinel, bidirectional iterators, O(1) erase from the element, auto-unlink when an element dies, and a move constructor that re-points the boundary links.