I’m building an on-device LLM runtime for mobile and needed a small-buffer-optimized (SBO) vector for lots of short-lived, small collections (token buffers, KV-cache bookkeeping). Pulling in a big dependency just for an SBO wasn’t an option, so I wrote a single-header container. Along the way I hit — and solved — a constraint I don’t see discussed much:
>
std::vector::insert/erase effectively requires the value type to be MoveAssignable (elements are shifted in place). If your type has const members, it isn’t assignable, which makes middle insert/erase a non-starter.Concrete example:
struct CacheEntry {
const uint64t tokenid; // invariant we want to enforce
std::vector<float> embedding;
};
std::vector<CacheEntry> v;
// v.insert(v.begin(), entry); // ill-formed or UB territory: shifting needs MoveAssignable
The core issue is not “std::vector bad”; it’s the algorithmic choice: in-place shifts assume assignment. Many SBO vectors mirror this behavior for speed on the heap path. The net effect is the same: types with
const members don’t work for middle insert/erase. (Top-of-vector push_back isn’t the problem.)My approach For heap paths I use rebuild-and-swap: construct a new buffer in the final layout and swap it in. That avoids assignment entirely; only construction/destruction is required. Yes, it looks more expensive on paper, but in practice the cost is dominated by O(n) element moves either way. Benchmarks on my side show \~2–3% overhead vs
std::vector for middle inserts, while keeping SBO wins on the inline path.Other design choices:
`std::variant` to track storage mode (inline vs. heap), which gives you a well-defined `valueless_by_exception` state and simpler lifetime management.
Trivial-type fast paths use
memcpy/memmove under the C++ “implicit-lifetime” rules (P0593), so copying bytes is standards-compliant for trivially copyable T. (GitHub)Why bother with
const members? Not for magic thread-safety — const doesn’t do that — but to enforce invariants at the type level (e.g., a token’s ID should never change). Making that field immutable prevents accidental mutation across layers and simplifies reasoning when multiple threads read the structure. You still need proper synchronization for the mutable parts.If you’ve run into this “non-assignable type in a
vector” wall before, I’d be interested in alternatives you used (e.g., node-based containers, index indirection, or custom gap-buffers).Blog post with benchmarks & design notes: [https://lloyal.hashnode.dev/inlinedvector-yet-another-sbo-container-but-with-a-good-reason](https://lloyal.hashnode.dev/inlinedvector-yet-another-sbo-container-but-with-a-good-reason)
Code (MIT, single header, available via vcpkg/Conan): https://github.com/lloyal-ai/inlined-vector
https://redd.it/1oiqyj6
@r_cpp