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

Subject: Re: [boost] Review managers wanted for augmented data structures
From: Dave Abrahams (dave_at_[hidden])
Date: 2013-03-30 23:37:53

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?

-- 
Dave Abrahams