Boost logo

Boost :

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

> 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:
> 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 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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at