JOAQUIN M. LOPEZ MUÑOZ skrev:
I recently wrote up the implementation of a *stable* vector, a container mimicking the interface of std::vector except that it provides iterator and reference stability at the expense of losing memory contiguity:
http://bannalia.blogspot.com/2008/09/introducing-stablevector.html
If there is interest in the community this could be grown into a full-fledged proposal for Boost (either by me or by any other interested colleague).
I think there is. In a number of situations, particular in combination with intrusive graphs, where I use deque today, that this is interesting. I briefly want to discuss an alternative design, which might be worth considering. In psudo code it would be implemented a bit like this: struct index { size_t from, to; }; struct segment { T* array; size_t size; }; class stable_vector { unordered_map<index,segment> data; }; The idea here is that we store segments of arbitrary size. To implement random access, we look up the appropriate segment. To implement iteration betwen segments, we lookup index.to+1 assuming the hash function only uses index.from. (A more effecient, segement based, non-in-order iteration can also be provided). Furthermore, I think insert/erase can know be done in O(M) time, where M is the average size of the segments. -Thorsten