From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2008-07-07 12:45:48
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.
> 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
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk