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

Subject: Re: [boost] Review managers wanted for augmented data structures
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2013-03-31 17:45:05

On Mon, Apr 1, 2013 at 12:40 AM, Dave Abrahams <dave_at_[hidden]> wrote:

>
> 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.
>
>
Asymptotically, most of operators of these new iterators have O(1) cost,
this group includes increment, decrement and comparison operators. However,
a few operators {+= , -=, +, -, [ ]} have O(log N) cost. Quite obviously,
such iterators are much closer to random access iterators than to
bidirectional. In addition to this, without std::random_access_iterator_tag
user algorithms can not take full advantage of the efficient algorithms
offered by augmented data structures. The running time can increase quite
significantly from O(log N) to O(N), since standard library algorithms
would use the subset of operators of bidirectional iterators only.

Regards,
Vadim Stadnik