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 09:22:26

On Sun, Mar 31, 2013 at 1:37 PM, Dave Abrahams <dave_at_[hidden]> wrote:

>
> on Mon Mar 04 2013, Vadim Stadnik <vadimstdk-AT-gmail.com> wrote:
>
> > On Mon, Mar 4, 2013 at 7:35 PM, Stefan Strasser <strasser_at_[hidden]
> >wrote:
> >
> >> Am 04.03.2013 08:48, schrieb Martin Knoblauch Revuelta:
> >>
> >>  Do you mean that you would declare them RandomAccess iterators?
> >>>
> >>> We can expect to have containers with millions of elements. For that
> >>> size, O(log N) is about 20 times faster than O(log N log N). That
> >>> makes a big difference.
> >>>
> >>
> >> isn't that a reason for providing optimized specializations of some STL
> >> algorithms, instead of introducing another iterator category?
> >>
> >> how would a new iterator category even help?
> >> as long as your iterator is a forward iterator, the user is allowed to
> >> call std::binary_search on your iterator, which uses the same algorithm
> on
> >> any iterator category. (only functions used by binary_search like
> >> std::advance are specialized on the category)
> >> where in all this would your tree-optimized binary_search code be
> called?
> >>
> >> the standard doesn't require random access iterator ops to be constant
> >> time.
> >>
> >>
> > Unfortunately, there is a problem of iterator categories with augmented
> > trees. The C++ standard specifies computational complexity for iterator
> > operations, although they are not shown in tables, since all of them are
> > required to be constant time. In both C++03 and C++11 this is formulated
> in
> > the section 24.1.8.
>
> Are you sure these iterators don't fall under the *amortized* constant
> time requirements, just like those of the ordered associative containers?
>
>
Yes, I am sure.

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.

Regards,
Vadim Stadnik