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)? -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com
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)?
O(1) access through an always continuous key and O(1) removal anywhere are unfortunately mutually exclusive goals. The continuity of the keys enforces either O(n) removal, since the keys have to be adjusted (shifting elements in the vector, for example), or complex index calculation (consulting a list of known holes) that cannot possibly be O(1) on access. If you don't need a continuous key, you can map indices to values in some associative container. Sebastian
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)?
I think that the best you can do is a tree of contiguous fragments, i.e. a std::map<size_t, std::vector<T>>. (Are ropes implemented like this?) Random access involves an O(log #fragments) tree search to find the right fragment followed by an O(1) lookup to find the right element in the fragment. Insertions and deletions involve splitting a fragment in two (hmm, some memory-allocation magic is needed to make that possible without copying one half). This is efficient if the number of fragments is kept small, and this means merging fragments from time to time. It would be great if there were a merge strategy that would give amortised O(1) operations, but I doubt it's possible. Phil.
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
Daryle Walker wrote:
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.
Hmm, as I was writing this, I thought of an alternative. Maybe I could use a deque,
Or a vector.
but swap the found element with the rear one before popping. Then erasure would be cheaper. Would that work?
Yes, that is certainly the right way to do it. Phil.
The new hat is in the sandbox SVN. It still under the "hat" directory, but this time look at what's in the "containers" subdirectories. On Aug 15, 2008, at 12:14 PM, Phil Endecott wrote:
Daryle Walker wrote:
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.
Hmm, as I was writing this, I thought of an alternative. Maybe I could use a deque,
Or a vector.
Right now, the default is a deque. I didn't want the exponential capacity growth vector has if reserve isn't used.
but swap the found element with the rear one before popping. Then erasure would be cheaper. Would that work?
Yes, that is certainly the right way to do it.
That's the way I did it. However, the Doxygen comments mention that this will ruin attempts to maintain a sorted container. You would have to manually resort after each pop. -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com
If you allow random-access to take O(log n) time, then you can have: - search and insertion-by-value in O(log n) time - insertion at iterator (when you know where to insert) in O(log n) time, and O(1) amortized time if insertion is in order - erase at iterator in O(log n) time - random-access by index in O(log n) time. That, is, the same as std::map/set, with a small overhead in the O (log n) and additional random-access (which isn't possible with std::set/map). The data structure is called an augmented red-black tree (i.e., r/b tree with an additional field at the node, which you can compact with the r/b color in no overhead to the footprint for most implementations). You'll find it in any data structure textbook. It's fairly easy to adapt/augment, e.g., the SGI STL map implementation. In practice the cost of insertion should be a bit higher (e.g., 20%) for manipulation, and identical for search and navigation (e.g., iteration). Random access would be fast but definitely not as fast as vector. -- Hervé Brönnimann hervebronnimann@mac.com 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)?
-- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/ listinfo.cgi/boost
participants (4)
-
Daryle Walker -
Hervé Brönnimann -
Phil Endecott -
Sebastian Redl