Re: [boost] [multi_index][rfc] random access indices preview

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 
news:437879AE.D786AA7D_at_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