Re: [boost] request for interest: stable vector

Subject: Re: [boost] request for interest: stable vector
From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 2008-09-15 03:17:51

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