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