Re: [boost] Proposed templated integer_sort

From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2008-07-07 12:45:48

AMDG

Steven Ross wrote:
> I thought about what would be required to make integer_sort work with
> forward iterators:
> 1) I would have to either eliminate the check to see whether the data set is
> small enough that
> std::sort would be better,  require the user to provide a count of the
> number of items being sorted, or be able to determine that the iterator
> isn't random-access and thus not do the check.
>   

use std::distance

> 3) I would need an inlined function call for going forward n places from an
> iterator that takes constant time for a random access iterator, and the
> minimum number of operations necessary for a more limited forward iterator.
> With that said, it should add an additional pass through the data for a
> non-random-access iterator.
>   

std::advance or boost::next(iter, n)

> Given all that, I can make integer_sort work off a forward iterator, without
> impairing randomaccess iterator performance, and still having decent
> performance for a forward iterator.
> So if you can provide me all of these:
> 1) A way to determine that an iterator is not random-access.
>   

For a random access iterator Iter
typename std::iterator_traits<Iter>::iterator_category
inherits from std::random_access_iterator_tag

> 3) An efficient way to go forward n steps from an iterator that is just as
> fast as + n for a random access iterator, but also works for normal
> iterators.
>   

std::advance

In Christ,
Steven Watanabe