Neat. Here's what I'd keep: just an epoch saying when the last valid element of the vector is. The iterator just needs a ptr to the vector and the vector's data. It's a constant time lookup, with somewhat heavier iterators. I guess this is something like MSFT's old debug iterators?