Re: [boost] request for interest: stable vector

Subject: Re: [boost] request for interest: stable vector
From: joaquin_at_[hidden]
Date: 2008-09-15 04:57:13

Thorsten Ottosen escribió:
> 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.
>   

The structure you describe is AFAICS equivalent to the usual 
implementation of std::queue
(http://tinyurl.com/68l9e7 ), except that std::queue uses an array for 
data instead of an
unordered_map. So, I don't see how one could provide stability for 
middle insertions.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo