I think you have a typo in there, "validate iterators" -> "invalidate iterators".
It should be easy to build a non-invalidating version of the iterator that has a pointer to the chunk and an offset within that chunk. That's more like 12 or 16 bytes, though.
What I like about vectors is that an index is not really about the storage that the vector holds at that position. The index is a mathematical identity of an object. It's the object itself. The vector is only a materialized function that holds some attribute for each object. The nice thing is we can have multiple independent vectors for each object type. This is true modularity.
We can get an address from a simple index with deques, too. But only with significant indirection. So I think if (1) no movement cost on reallocation is allowed, and/or (2) stable pointers are needed, deques are a fine choice. But vectors are my first choice.
Given that we have huge address spaces nowadays we could also consider preallocating large global vectors at stable addresses, and expanding them with mmap(). This way the copying when growing the vector is not needed.
It should be easy to build a non-invalidating version of the iterator that has a pointer to the chunk and an offset within that chunk. That's more like 12 or 16 bytes, though.
What I like about vectors is that an index is not really about the storage that the vector holds at that position. The index is a mathematical identity of an object. It's the object itself. The vector is only a materialized function that holds some attribute for each object. The nice thing is we can have multiple independent vectors for each object type. This is true modularity.
We can get an address from a simple index with deques, too. But only with significant indirection. So I think if (1) no movement cost on reallocation is allowed, and/or (2) stable pointers are needed, deques are a fine choice. But vectors are my first choice.
Given that we have huge address spaces nowadays we could also consider preallocating large global vectors at stable addresses, and expanding them with mmap(). This way the copying when growing the vector is not needed.