[boost] [multi_index] interest in a random-access index?

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2005-01-21 04:07:48

Hello,

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

insert).
2. Iterators are random-access. The index provides an operator[]/at()
interace. Advancing/incrementing an iterator involves internally an
addition
and two pointer dereferences: not as fast as a real vector, but very
fast
indeed.
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[0])+n cannot be
used to sequentally access all the elements of the index, unlike
std::vector.
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
to
add stuff just for the fun of it.
B. Any suggestion for the name of such an index?

Thank you,

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