From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2005-01-21 04:07:48
I'm considering the possibility of devising a new type of index
for Boost.MultiIndex with random-access capabilities, modeled
pretty much after the interface of std::vector (with some significant
pros and cons.) The basic features of such an index would be:
1. Traversal order is set by the user as with sequenced types. A
vector-like insertion interface is provided (push_back/front, positional
2. Iterators are random-access. The index provides an operator/at()
interace. Advancing/incrementing an iterator involves internally an
and two pointer dereferences: not as fast as a real vector, but very
3. The memory overhead is two pointers per element.
4. Iterators and references are stable, i.e. they remain valid on the
face of insertions/deletions (std::vector does not guarantee this.)
5. Memory storage is *not* contiguous: so, (&begin)+n cannot be
used to sequentally access all the elements of the index, unlike
6. The complexity bounds are much the same as those of a vector:
amortized constant insertion/deletion at the end, linear otherwise.
My questions are:
A. Is there interest in having this in Boost.MultiIndex? I wouldn't like
add stuff just for the fun of it.
B. Any suggestion for the name of such an index?
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
Boost list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk