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

Subject: Re: [boost] Review managers wanted for augmented data structures
From: Martin Knoblauch Revuelta (mkrevuelta_at_[hidden])
Date: 2013-03-04 02:48:38

On Sun, Mar 3, 2013 at 4:47 PM, Vadim Stadnik <vadimstdk_at_[hidden]> wrote:
> 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.

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.

>> [..]
> 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.

Yes, I perfectly understand that introducing a new iterator category
is not as simple as editing a few lines. That's why I see this as the
mayor obstacle for the integration of augmented trees with the style
of the C++ Standard Library.

> 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?

Well, for millions of elements, this means about "4 times slower than
O(1)"... so... maybe?

Best regards,
Martín Knoblauch Revuelta