"Joaquín Mª López Muñoz" <joaquin@tid.es> wrote in message news:437879AE.D786AA7D@tid.es... Hello, Some months ago I prompted for interest in a new type of indices for Boost.MultiIndex featuring random access facilities, and received a couple of expressions of itnerest. The preliminary specification was published at: http://195.235.93.150/rnd_indices_spec.html I've just uploaded a preview version of random access indices at FileVault -> Containers (http://tinyurl.com/9zlmj) This preview follows the previous specification save for one point: reserve/capacity is provided for control of an internal array of pointers to the nodes, as explained in http://195.235.93.150/rnd_indices_spec.html#interface. There's no docs yet on this type of indices, but the usage should be straightforward from the preliminay specification notes. Random access indices act as a functional drop-in replacement of sequenced indices, so you can start playing with them very easily. My requests: * Do you find these indices worth including in Boost.MultiIndex? * If so, do you have comments on the specification? Things you'd change/add? There's a list of concrete issues at the end of the specification page, * Do you envision any interesting use case for random access indices? Have you experimented with them? One possible alternative implementation is a modification of the order-statistic tree from "Introduction to Algorithms" by Corman et. all. Basically this is a balanced binary tree where every node contains the size of its left subtree. This results in a data structure where insertion, deletion, indexing and iterator arithmetic are all O(log n) and for which insertion and deletion do not invalidate iterators. Note that while the version shown in "Introduction to Algorithm" is a binary search tree, for your version you can omit the condition that the nodes are in sorted order and just keep the balancing and order-statistic structures. Joe Gottman