From: Hervé Brönnimann (hervebronnimann_at_[hidden])
Date: 2008-08-18 21:05:18
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
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_at_[hidden] 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk