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

Subject: Re: [boost] Review managers wanted for augmented data structures
From: Stefan Strasser (strasser_at_[hidden])
Date: 2013-03-04 03:35:09

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.