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-03 06:47:10

On Sun, Mar 3, 2013 at 7:38 PM, Martin Knoblauch Revuelta <
mkrevuelta_at_[hidden]> wrote:

> On Sun, Mar 3, 2013 at 3:22 AM, Jonathan Wakely
> <jwakely.boost_at_[hidden]> wrote:
> > [..] existing algorithms
> > work with both standard and non-standard containers if they model the
> > required concepts.
>
> The containers we are proposing here are sequence containers. The
> computational complexity of their operations are somehow in between
> those of std::list and std::vector. They provide random access in
> O(log N) time _and_ insertion/removal in O(log N) time.
>
> Therefore, their iterators are _not_ as random-access as those of
> std::vector. If we declare them random-access, existing algorithms
> will perform poorly on them. And if we declare them sequential-access
> (Bidirectional), it will be worse.
>
> For example, if the contents of the iterator are sorted, we can make a
> binary search in O(log N) time, since the implementation is based on a
> self balanced tree. If we declare the iterators random-access, the
> existing binary_search algorithm will treat the sequence like a
> vector, and it will take O(log N log N) time.
>
>
The main point is that asymptotically this is much more efficient than
linear search.

> Existing algorithms are tailored for the existing sequence containers.
> In order to integrate the use of these new containers ---even as
> non-standard containers--- we need the standard library to at least
> acknowledge the possibility of their existence by declaring a new
> iterator category.
>
>
I am not sure that adding a new category of an iterator will be helpful,
since this can affect the generality of design and user algorithms. To some
degree it is equivalent to the current C++ specification of computational
complexities. This approach will make acceptable one class of augmented
trees, but at the same time it will create problems for integration of
other potentially useful data structures. For example, suppose there is a
new data structure that supports random access to elements with O(log(log
N)) running time. Should we again introduce a new iterator category?

Regards,
Vadim Stadnik