Re: [boost] Review managers wanted for augmented data structures

Subject: Re: [boost] Review managers wanted for augmented data structures
From: Dave Abrahams (dave_at_[hidden])
Date: 2013-03-31 10:40:04

on Sun Mar 31 2013, Vadim Stadnik <vadimstdk-AT-gmail.com> wrote:

> The algorithms that implement random access to container elements by index
> (also often named 'rank') are efficient search algorithms using counters of
> elements stored in tree nodes. These algorithms are similar to algorithms
> searching an element by a key that support functions of associative
> containers, such as c.lower_bound(key) and c.upper_bound(key). In the
> general case, both kinds of search algorithms on trees have the same
> logarithmic running time. However, the augmented array based B+ trees have
> an important advantage over red-black trees. They offer constant time
> access to the nearest container elements in the worst case against constant
> amortized time. Thus, these new data structure can provide the efficiency
> of sequential processing close to that of std::vector.

Ah.  Seems like we don't have appropriate concepts to characterize these
things.  What do you say about the big-O when the dominating factor will
always have such a small constant that it becomes insignificant? 
It feels like a cop-out, but I guess I'd go with random_access.

-- 
Dave Abrahams