How to safely access every n-th element in a container in a succinct way?

Question

Consider an STL container C that is forward-iteratable. I need to access every step element, starting from idx. If C is a vector (i.e. has a random-access iterator) I can just use index arithmetic:

template <class Container>
void go(const Container& C) {
    for(size_t i = idx; i<C.size(); i+=step) {
        /* do something with C[i] */
    }
}

However, if C does not support that, e.g. C is a list, one needs to rewrite the above solution. A quick attempt would be:

template <class Container>
void go(const Container& C) {
    size_t max = C.size();
    size_t i = idx;
    for(auto it = std::next(C.begin(),idx); i < max; i+=step, it+=step) {
        /* do something with *it */
    }
}

Not much longer and it works... except that most likely it will trigger the undefined behavior. Both std::next and it+=step can potentially step way beyond the C.end() before i < max check is performed.

The solution I am currently using (not shown) is really bloated when compared to the initial for. I have separate check for the first iteration and those that follows. A lot of boilerplate code...

So, my question is, can the above pattern be written in a safe, and succinct way? Imagine you want to nest these loops 2 or 3 times. You don't want the whole page of code for that!

• The code should be reasonably short
• The code should have no overhead. Doing std::next(C.begin(), i) in each iteration over i is unnecessairly long, if you can just std::advance(it, step) instead.
• The code should benefit from the case when it is indeed a random-access iterator when std::advance can be performed in constant time.
• C is constant. I do not insert, erase or modify C within the loop.

Answer 1

You might use helper functions:

template <typename IT>
IT secure_next(IT it, std::size_t step, IT end, std::input_iterator_tag)
{
    while (it != end && step--) {
        ++it;
    }
    return it;
}


template <typename IT>
IT secure_next(IT it, std::size_t step, IT end, std::random_access_iterator_tag)
{
    return end - it < step ? end : it + step;
}


template <typename IT>
IT secure_next(IT it, std::size_t step, IT end)
{
   return secure_next(it, step, end, typename std::iterator_traits<IT>::iterator_category{});
}

And then:

for (auto it = secure_next(C.begin(), idx, C.end());
     it != C.end();
     it = secure_next(it, step, C.end()) {
    /* do something with *it */
}

Alternatively, with range-v3, you could do something like:

for (const auto& e : C | ranges::view::drop(idx) | ranges::view::stride(step)) {
    /* do something with e */
}

Answer 2

The comment in the question about the requirements inspired me to implement this in terms of k * step instead of some other mechanism controlling the number of iterations over the container.

template <class Container>
void go(const Container& C)
{
    const size_t sz = C.size();

    if(idx >= sz) return;

    size_t k_max = (sz - idx) / step + 1;

    size_t k = 0
    for(auto it = std::advance(C.begin(), idx); k < k_max && (std::advance(it, step), true); ++k) {
        /* do something with *it */
    }
}