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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk