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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk