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:
> 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:
size_t from, to;
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk