Subject: Re: [boost] [GSOC] Regarding the project Boost.DeVector
From: Eugene Wee (crystalrecursion_at_[hidden])
Date: 2009-03-22 11:21:03
Thanks for clarifying that. Since we can use any implementation for
> this, (which satisfies the requirements and an appropriate interface
> of course), I suggest using a dynamic array which grows on both sides.
As in you allocate one contiguous block, and start using it from the middle?
The problem would be that you lose the property that
pointers/iterators/references are not invalidated if the container only
grows at the ends, since you may need to perform re-allocation after the
beginning or end of the single contiguous block is reached.
Also, with a list of blocks approach, wouldn't it be rather difficult
> to provide amortized O(1) random access?
The list of blocks could be a vector of pointers, as described in the
"Segmented Iterators and Hierarchical Algorithms" article that the ideas
page links to.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk