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-04 07:50:49

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.

IMO, the problem is rather theoretical than practical.
First of all, in systems with virtual memory management the value of
"constant time" can vary by almost two factors for array based and
dynamically allocated data structures. This is the reason why in some cases
dumb algorithms using std::vector outperform smart algorithms using trees.
Second, STL specification ignores the main theoretical parameter of user
algorithms - the total computational cost. This aspect has been discussed
in the very first message of this thread. Third, augmented trees easily
bypass these C++ restrictions, since they provide wider sets of efficient
operations and can replace standard containers through existing interfaces.

Also, I do not consider adding new category of iterators useful for the
reason that it works against generality by increasing the number of types.
The generalization or abstraction method reduces all the specific types to
one "ideal type". The generalization also means more unified and coherent
interfaces for various types that support the interface of this "ideal
type".

Regards,
Vadim Stadnik