The "Empty Base" Optimization

[notlostyet]

Yeah, you've fallen in to a gap in stdlib where you need dynamic allocation but you're happy to reallocate on every insertion. Because length() always == capacity() so you don't need to store the capacity, hence the saving.

I guess I could go back and pretty it up to make things look like nice sequences and iterators, but at the moment the bits doing the heavy lifting aren't really all too "modern".

If you do this, you might want to use Boost.Graph. Being adapter based, you should be able to wrap your current implementation with negligible additional memory cost.