Re: [boost] [MultiIndex] Random Access mental model?

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 <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
>>
>>   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 
[begin,first_not_connected),[first_not_connected,end)
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 
above).

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