C++ an iterator "for loop" idiom which moves in step sizes > 1 and allows for non-random-access reverse iterators

Question

Sorry for the question wording. Please edit if you can think of a better way to phrase the question.

To loop over a std::vector v one step at a time, we have a lot of options. Here are some that immediately come to mind:

1. for ( auto & elem : v )
2. for ( int i = 0 ; i < v.size() ; ++i )
3. for ( auto begin = v.begin() ; begin < v.end() ; begin++ )

Now I want to restrict the discussion to the iterator based approaches, since I will eventually be interested in other containers. For instance, let's say I have a method that juts accepts the begin and end iterators:

template <typename Iterator>
void foo( Iterator begin, Iterator end ){
    for ( ; begin < end ; begin++ ){
       ...
    }
}  

The issue with this is that this will not work with more general containers since we can't simply increment the iterator for all containers. Ok let's fix that:

template <typename Iterator>
void foo( Iterator begin, Iterator end ){
    for ( ; begin < end ; std::advance( begin, 1 ) ){
       ...
    }
}  

Aha, but there is another issue, notably, what happens if somebody gave us a reverse iterator... Ok. If we are worried about that, we could simply change this to

template <typename Iterator>
void foo( Iterator begin, Iterator end ){
    for ( ; begin != end ; std::advance( begin, 1 ) ){
       ...
    }
}  

Here is my question... How do I now accommodate a step size larger than 1 while acknowledging that I could have a reverse, non-random access iterator?

Specifically, what is the most lightweight test I could insert in the following code:

template <typename Iterator>
void foo( Iterator begin, Iterator end, const size_t step ){
    for ( ; test(begin, end) ; std::advance( begin, step ) ){
       ...
    }
}  

EDIT:

It was pointed out that the advance function may be undefined if I step past the end of the container. That bug needs to get fixed as well.

Answer 1

The really big problem with hopping more than one single element is not the test you are seeking – it is avoiding incrementing the iterator past the end of the container (which is undefined behaviour)!

Following scenario:

std::vector<int> v({7});
for(auto i = v.begin(); i < v.end(); i += 2);

Yes, I even skipped std::advance deliberately for comparison...

You increment the iterator beyond the vector's end! While that might seem to run nicely, it is still undefined behaviour.

If you want to have a generic solution based on iterators, you need to know how many elements are yet left:

template <typename Iterator>
void foo(Iterator begin, Iterator end, typename Iterator::difference_type step)
{
    if(begin != end)
    {
        for(;;)
        {
            // use *begin
            if(end - begin <= step)
                break;
            begin += step;
        }
    }
}

Now this only works for random access iterators, of course. But if we replace the use of operators with if(std::distance(begin, end) <= step) and std::advance(begin, step) in the RA variant above, we get a solution that works for all types of iterators.

You might want to stay with for simplicity/maintainability.

Solely: With non-RA iterators, you need to do step single one-position hops twice, once for calculating the distance, once for actually advancing. So you might prefer doing both manually in one single go for these. In a general solution, you'd check for the type first:

for(;;)
{
    // use *begin;

    if constexpr
    (
        std::is_same_v<typename Iterator::iterator_category, std::random_access_iterator_tag>
    )
    {
        if(std::distance(begin, end) <= step)
            goto LOOP_EXIT; // alternatively (here only): break;
                            // (wanted to be consistent with else branch...)
        std::advance(begin, step);
    }
    else
    {
        for(size_t i = 0; i < step; ++i)
        {
            if(std::advance(begin, 1) == end)
                goto LOOP_EXIT;
        }
    }
}
LOOP_EXIT:
// if no further instructions follow:
(void) 0; 

If you need that more often, you might move this into your own

template <typename Iterator>
Iterator advance_not_beyond(Iterator begin, Iterator end, size_t step)
{ /* ... */ }

as long as we don't get a std::advance_not_beyond by the standard...

Answer 2

Trivial answer: replace

std::advance( begin, step )

by

for (int i=0;i<step;i++) {if (begin!=end) std::advance(begin,1);}

. INSIDE the for loop increment. Because the onliest way to check if you are past an element in an unordered manifold is if you check at each step. That is what gives modulo encryption its cryptographical strength. In the case you got an order but just do not know whether it is working forward or reversed, you could check at the beginning whether

bool bigger_at_beginning=begin > end;

and make the comparison dependent on that bool, like

bigger_at_beginning ? (begin<end) : (begin>end)

but that is not as straight-forward, and will not work on completely unordered iterators, so I prefer the former way of doing.

Answer 3

Here's a template that performs the iteration with given step size and checks for the termination condition after every increment. It also calls a function with the dereferenced iterator.

template <typename Iterator, typename Fct>
void foo(Iterator begin, Iterator end, std::size_t step, const Fct& f) {
   if (begin == end)
      return;

   while (true) {
      f(*begin);

      for (std::size_t i = 0; i < step; ++i)
         if (++begin == end)
            return;
   }
}

This should work for any non-random-access iterator, e.g.

const auto print = [](const auto& arg){ std::cout << arg << "\n";  };

std::list<int> l{42, 43, 44, 45, 46};

foo(l.crbegin(), l.crend(), 3, print);

or e.g. with input iterators.

foo(std::istream_iterator<char>(std::cin), std::istream_iterator<char>(), 2, print);