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