Hello Joe, Joe Gottman ha escrito:
"Joaquín Mª López Muñoz" <joaquin@tid.es> wrote in message news:437879AE.D786AA7D@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