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

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2005-11-15 03:18:04

Hello Joe,

Joe Gottman ha escrito:

> "Joaquín Mª López Muñoz" <joaquin_at_[hidden]> wrote in message
> news:437879AE.D786AA7D_at_tid.es...
> * 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.
>

I think your proposal makes a very different kind of index, since it wouldn't
provide random access iterators. FWIW, ranked indices (http://tinyurl.com/b34sb)
are based on order-statistics trees and can be used to construct ordered indices
with O(log n) positional lookup (operator [] ): not exactly what you propose,
but probably equivalent form some applications, and might be included in
Boost.MultiIndex in the future.

On the other hand, please note that middle-insertion and middle-deletion, though
technically O(n) for random access indices, are actually much faster than
for std::vector, since there's no element reallocation/shifting at all (only an
internal array of pointers is reallocated or shifted accordingly.) So the
performance characteristics of random access indices are, IMHO, not so bad.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo