Boost logo

Boost :

Subject: Re: [boost] [MultiIndex] Random Access mental model?
From: joaquin_at_[hidden]
Date: 2008-11-05 08:54:11

David Abrahams escribió:
> on Sat Nov 01 2008, Joaquin M Lopez Munoz <> 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
>> multi_index_container<random_access,random_access>
>> 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
trade-offs with
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
name coexisting
with the current random_access (which should be kept for the current
up-pointer index)?

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, gregod at, cpdaniel at, john at