Re: [boost] Can multi-index do this?

From: Daryle Walker (darylew_at_[hidden])
Date: 2008-08-15 01:48:42

On Aug 14, 2008, at 2:08 AM, Daryle Walker wrote:

> Is it possible for Boost.Multi-index, or anything else in Boost, to  
> make a container that is generally random-access (like vector or  
> deque) but efficiently allows removals anywhere (like list)?

It seems from the responses so far that these conditions are  
generally mutually exclusive.  Maybe it'll help to say what my needs  
are.

I'm going to redo the "hat" project I have in the sandbox.  It  
currently is a brand new container design; I want to change it into  
an adaptor, like std::stack.  I can do a push like c.push_back() or  
c.insert()[1].  Getting the top would involve randomly generating an  
index and returning the element offset with that index from c.begin 
().  This is really easy for random-access containers, but linear for  
anything else.  I would do a pop by calling "top" and then erasing  
the returned iterator.  So the pop has two contrasting parts: I can  
have speedy search for the element with a deque, at the cost of slow  
erasure (moving all the following elements down), or I can have  
speedy searches with a list, at the cost of slow indexing (which also  
hits "top").  Which one should I use as the default base container,  
if either?  That's why I was wonder if there's a dream container with  
both properties that I could use as the default.

Hmm, as I was writing this, I thought of an alternative.  Maybe I  
could use a deque, but swap the found element with the rear one  
before popping.  Then erasure would be cheaper.  Would that work?   
The problem is that I couldn't use an associative container as a  
base, since their elements are quasi-constant and their ordering is  
strict.  However, the standard container adaptors don't work with  
associative containers anyway, so I could do the same.

[1]  Why isn't adaptor pushing done with "c.insert(c.end(), t)"  
instead of "c.push_back(t)"?  The "insert" method will work with  
associative containers too.

-- 
Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT hotmail DOT com