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