Safe Traversal Operations for Iterators

Motivation

I have found on occasion that I have needed to safely increment/decrement iterators by ensuring they are within some bounded range. After reading through some implementations (SO, Boost Summer code) and a proposal, I found that most of these "safe" functions did not handle the case where a negative difference type was used. From the C++ standard (C++14 Draft N4140 24.4.4):

template 
void advance(InputIterator& i, Distance n);

Requires: n shall be negative only for bidirectional and random access iterators.

If I am going to provide "safe" versions of the traversal operations advance(), next(), and prev(), I should at least meet those minimum requirements.

Implementation

```
#ifndef MY_ITERATOR_H
#define MY_ITERATOR_H

#include
#include
#include

namespace my {

template
auto safe_next(Iterator, Iterator, Iterator, Distance);

namespace details {

template
inline void safe_advance_helper(RandIt& curr, RandIt first, RandIt last,
Distance offset,
std::random_access_iterator_tag) {
std::advance(curr, std::max(std::min(std::distance(curr, last), offset),
std::distance(first, curr)));
}

template
inline void safe_advance_helper(BidirIt& curr, BidirIt first, BidirIt last,
Distance offset,
std::bidirectional_iterator_tag) {
for (; 0
inline void safe_advance_helper(FwdIt& curr, FwdIt first, FwdIt last,
Distance offset, std::forward_iterator_tag) {
if (0 > offset) {
const auto offset_from_first = std::distance(first, curr) + offset;
curr = safe_next(first, first, last, std::max(0, offset_from_first));
} else {
for (; offset && curr != last; --offset) {
std::advance(curr, 1);
}
}
}

template
inline void safe_advance_helper(InputIt& curr, InputIt first, InputIt last,
Distance offse

-
As you market yours as safe, yes, as long as it's not too costly, thus only for randomaccess-iterators by default. Remember though to treat it as an error.

Provide a paranoid mode for forward iterators and bidirectional iterators to be checked as well, and disable those checks for release.

That leads to companion-functions for checking whether the iterator is actually in the range, and additional ones for moving it to start resp. end of the range if not in there (supplied a bigger containing range) which returns whether a correction was neccessary.

-
You should not allow the algorithm take such an unanticipatedly larger time-span. Handle it just like any other programmer-error.

A different algorithm advertizing that service might be a good idea though.

-
Consider to accept a range instead of two iterators. There's a reason people are working on getting those into the standard library.

-
You shouldn't throw on programmer-error, as that introduces the need for exception-handling where previously there was none, with unpredictable consequences and loss of performance.

Instead, just go for std::terminate() directly.

-
The proposal you linked doesn't allow free choice of distance-type for any function. The standard only allows it for advance. Let's hope nobody passes an unsigned value to safe_prev...

-
The random-iterator-case can be more elegantly and succinctly and clearly written with a boost::clamp:

curr += boost::clamp(offset, first - curr, last - curr);

-
I wonder why you call the base-function instead of going on with the task for the forward-iterator-case, after finding the start.

Also, if you stay with it, invest in a std::safe_distance...

StackExchange Code Review Q#112023, answer score: 3