InlinedVector: Yet Another SBO Container (But with a good reason)

We weren’t trying to “beat” Abseil or Boost. We just couldn’t ship them.

On mobile, every dependency is a shipping decision. We needed a small-buffer-optimized vector for lots of small, short-lived collections (token buffers, transient state), without dragging in a big ecosystem. So we built a single-header, zero-dep vector with SBO and a couple of behaviours we couldn’t find elsewhere.

The surprise benefit: it handles insert/erase on types with const members—a case where std::vector and common SBOs run into assignment requirements during in-place shifts. Our approach uses rebuild-and-swap on heap paths, so it stays well-defined for non-assignable types while keeping performance within a few percent.

---

Constraints (why we built it)

• Zero dependencies (mobile/NDK; keep the binary small)

• SBO first (most instances are tiny)

• Modern C++ (C++17/20; std::variant, traits, clean state handling)

• Production hygiene (fuzz tests, sanitizers)

• Can move heap → inline again after temporary spikes (not all SBOs do this in every version)

For what it’s worth: Abseil’s InlinedVector implements shrink_to_fit() that can move storage back into the inline buffer when size permits. That’s exactly the behaviour we wanted.

Note on Boost: Older advice says small_vector “stays on heap after a capacity change.” In recent Boost (e.g., 1.86), shrink_to_fit() can migrate back to the small buffer when size() allows. If you rely on this, check your Boost version and tests.

---

The design choice that made it simple

Most SBO vectors hand-roll a tagged union:

enum State { Inline, Heap };
union { InlineBuf inline_; HeapBuf heap_; };

We use:

std::variant<InlineBuf, std::vector<T, Alloc>>

That gets us:

• Straightforward state management

• A defined valueless_by_exception state (and an easy recovery story)

• A smaller, easier-to-audit implementation

In practice the discriminator check gets optimised away on hot paths; we saw no practical overhead vs hand-rolled tags.

---

Why const members are usually painful—and how we avoid it

Middle inserts for std::vector (and similar containers) rely on assignment-based element shifting. That imposes “MoveInsertable / effectively MoveAssignable” requirements on T—which fall over when T has const data members. You get ill-formed code or UB if you try to force it.

What we do instead: on heap paths we rebuild-and-swap:

1. Allocate a new buffer with the final size.

2. Construct elements in order (before/insertion/after).

3. Swap into place.

You pay the same big-O cost (O(n) moves/copies dominate either way), but you don’t require MoveAssignable. That keeps inserts/erases working for:

• Types with const members

• Types with deleted assignment operators

• Immutable domain objects with mutable payloads

Compatibility note (important)

• C++20 explicitly enables the “destroy-and-reconstruct” idiom for replacing subobjects via std::destroy_at / std::construct_at because of updates in basic.life. If you insist on const members and still want assignment-like updates, that’s your standards-conforming tool. It’s boilerplate—but legal.

• C++17 doesn’t give you that latitude for arbitrary non-trivial types; our container stays on the right side of the rules by avoiding assignment requirements in the first place for the operations that would need them.

If you’re following the debate: Arthur O’Dwyer’s “Don’t const all the things” is a good overview of why blanket-const can backfire. Our position isn’t “const everywhere”; it’s “if you do have non-assignable types, the container shouldn’t make them unusable.”

---

The other picky details we cared about

• Allocator-aware, including inline elements (not just heap storage)

• Heap ↔ inline transitions via shrink_to_fit() when size permits (same spirit as Abseil)

• std::variant recovery: if an operation ever leaves the variant valueless, the next mutation recovers cleanly.

• Trivial-type fast paths: for implicit-lifetime types, byte moves are standards-conforming (see implicit-lifetime rules). Cppreference

---

Where this is a win

• Mobile/embedded where you can’t bring Abseil/Boost/LLVM along

• Hot paths with tiny vectors (the usual SBO sweet spot)

• Codebases that intentionally model immutability in some fields

Where it’s not:

• You already depend on Abseil/Boost—use what you’ve got

• Your vectors are typically large—then just use std::vector and reserve

• You’re chasing the last 1% for complex inline types—Abseil may edge ahead there

---

On “don’t const members”

Some folks argue you should rarely (or never) use const data members. The core reasons: it complicates assignment/move semantics and can block otherwise straightforward container operations. Those are real trade-offs. Our view is narrower:

• If your domain model benefits from immutability (e.g., IDs), the container shouldn’t force you to redesign your type just to call insert.

• If you don’t need const members—great. Most code doesn’t. But if you do choose them, the data structure shouldn’t be the thing that breaks.

Pointers for further reading:

• The implication of const or reference member variables in C++ (Reddit discussion)

• “Don’t const all the things” (Arthur O’Dwyer) — the pitfalls of over-const.

• When to use const in C++? Part II: member variables (Sandor Dargo)

---

Quick refs you might care about

• std::vector insert requirements (why non-assignable types run into trouble).

• std::variant::valueless_by_exception (and why we recover cleanly).

• Abseil InlinedVector::shrink_to_fit (moving back to inline).

• Boost small_vector: recent versions can return to the small buffer via shrink_to_fit()—check your Boost, don’t rely on dated advice.

• Implicit-lifetime types (why memcpy is valid for trivial types). Cppreference

---

If your constraints look like ours, grab it and see if it fits:
Repo: lloyal-ai/inlined-vector • License: MIT
Vcpkg: lloyal-ai-inlined-vector

Bugs, critiques, edge cases we missed—please open an issue. We’re building this in the open and happy to adjust when the evidence says we should.