Subject: Re: [boost] [MultiIndex] Random Access mental model?
Date: 2008-11-05 08:54:11
David Abrahams escribiÃ³:
> on Sat Nov 01 2008, Joaquin M Lopez Munoz <joaquin-AT-tid.es> wrote:
>> Not that this can't be done, at least in principle, but
>> it breaks the current index orthogonality in (IMHO) nasty ways.
>> What's more, the following type
>> couldn't provide any O(1) erase method.
> How do you erase in O(1) from the middle of a random-access container?
Ouch... Yep' you're right again. I have thought about this more
carefully, and an
no-up-pointer random access index might be designed with the following
respect to the current random_access:
* no stable iterators
* no constant iterator projection
Other than that, the big-O complexities (constant push_back, etc) can be
kept, I think.
Do you think this would be a useful addition to B.MI? A suggestion for a
with the current random_access (which should be kept for the current
Anyway, I don't think this new index would serve your purposes, since
you need some
of the elements to be "disconnected" from the list: there might be
workarounds like considering
the sequence divided into two ranges
but I don't know if this holds water.
> Suppose you wrote a library that provided only deque, and not vector, as
> a random access container. Your premise seems analogous to one that
> says, "not having O(1) push_front for a random access container is a
> problem." I'm saying it's not a problem to lose a feature unless you
> need it, especially if you get something in exchange.
Understood. I was meaning that it was a problem to incorporate this
feature lacking components
into the whole system in a coherent way, but maybe I spoke too fast (see
JoaquÃn M LÃ³pez MuÃ±oz
TelefÃ³nica, InvestigaciÃ³n y Desarrollo
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk