Is there a container like the one I am asking for?

Question

I was looking to implementing a c++ container object with following properties:

1. Keeps all the elements contiguously in memory, so that it can be iterated over without causing any cache misses.
2. Expandable, not like arrays which are of a fixed sized, but much like vectors in stl which can adjust the memory allocated to accommodate as many elements as i add.
3. Does not reallocate elements to new place in memory when resizing like in the case of std vectors. I need to keep pointers to the elements that are in the container, so reallocation the pointers should not be invalidated when adding new elements.
4. Must be compatible with ranged based for loops, so that the contents can be efficiently iterated through.

Is there any container out there which meets these requirements, in any external library or do i have to implement my own in this case?

As some comments have pointed out, not all the desired properties can be implemented together. I had ought over this, and i have an implementation in mind. Since making things contiguous entirely is not possible, some discontinuity can be accomodated. For example, the data container allocates space for 10 elements initially, and when the cap is reached, allocates another chunk of memory double the amount of the previous block, but doesn't copy the existing elements to that new block. Instead, it fills the new block with the new elements i put into it. This minimizes the amount of discontinuity.

So, is there a data structure which already implements that?

Answer 1

IMHO, the data-structure that is the closest from your need is the deque in the STL. Basically it stores chunk of contiguous memories and provides both random access iterators and stability regards to push_back (your elements stays at the same place although iterators are invalidated). The only problem with your constrains is that the memory is not contiguous everywhere but as others commented, your set of needs is incompatible if you want to fully satisfy them all. By the way one sweet thing with this container is that you can also push on the front.