Boost logo

Boost :

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

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at