From: Joe Gottman (jgottman_at_[hidden])
Date: 2005-11-14 22:03:22
"Joaquín Mª López Muñoz" <joaquin_at_[hidden]> wrote in message
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
I've just uploaded a preview version of random access indices at
FileVault -> Containers
This preview follows the previous specification save for one point:
reserve/capacity is provided for control of an internal array of
to the nodes, as explained in
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
* 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk