Iterating over odd (even) elements only in a range-based loop

Question

Suppose we have a plain array (or other container which supports range-based loops):

const int N = 8;
int arr[N] = {0, 1, 2, 3, 4, 5, 6, 7};

Using indexes or iterators, we can loop over odd elements and increment the index by two:

for (int i = 0; i < N; i+=2)
{
   std::cout << arr[i] << std::endl;
}

How can I get a similar result by using a range-based loop and avoiding explicit iterators/indexes and iteration skipping? Something like this:

for (const auto& v: odd_only(arr))
{
   std::cout << v << std::endl;
}

What does a simple and elegant solution look like? Does the standard library contain something like this?

Carhart

I don't think we currently have something like that in the STL, but range-v3's view::stride might be what you're looking for (although I'm not sure how that works with plain arrays - std::array should be fine though). – Tye

Update: Definitely works with normal arrays (example). – Tye

As mentioned already, there's no direct support for. If you don't want to relay on 3rd-party libraries, all you can do is something similar to bool isEven = false /* isOdd = true */; for(...) { if((isEven = !isEven)) { ... }; }. I personally would rather just retain the original loop, though... – Cari

@hlt, thanks it works. But I think it would be good if someone gave an answer with a detailed explanation of how this works so that the question and answer were useful to the community. – Carhart

@Aconcagua, I don't like the idea with iterations ​​skipping . This is cumbersome and poorly readable. – Carhart

@DmytroDadyka I don't like it either (thus my recommendation) – just if you insist on range based for loop... – Cari

@Aconcagua, I do not insist on range based loop, but it seemed to me an interesting С++ question. I like the range-v3 solution. – Carhart

Note that your index-based example uses <. Iterators don't always have a <, and more problematically, creation of iterators past the end is usually undefined behavior, so the only alternative is to singly step and compare every single iterator to the end (but only process the corresponding data on every other iteration). Therefore there will be iteration-skipping, even if it is hidden from you. If you don't like iteration-skipping, you can't use iterators. – Chanteuse

@BenVoigt, you're right, with iterators it's a bit more complicated – Carhart

@hlt, I think it would be useful to put your example as an answer. – Carhart

@BenVoigt Not totally true: random access iterators (the appropriate tag would need to be checked in a constexpr if then) could use if(distance(b, e) < n) advance(b, n); else b = e; - sure, as is it would be possible to do so for non-RA, too, but both distance and advance would need to iterate over, thus inefficient... – Cari

@Aconcagua: Correct, distance(it, e) < n (or e - it < n) could be done with no undefined behavior, just not a direct translation of the index for loop. Probably there should be some advance_not_past(it, n, e) function that is efficient for random access iterators and still optimal (single-pass) for others. – Chanteuse

Answer 1

There's no support for what you request – but you might write your own even_only and odd_only implementations.

Basic idea is to wrap around the normal iterator of the container in question and do a double increment internally each time we increment once externally:

template <typename C, bool IsOdd>
class even_odd_only
{
    C& c;
public:
    class iterator
    {
    public:
        // all the definitions required for iterator!
        // most if not all might simply be derived from C::iterator...

        // copy/move constructor/assignment as needed

        // core of the wrapper: increment twice internally!
        // just doing += 2 is dangerous, though, we might increment beyond
        // the end iterator (undefined behaviour!)additionally, += 2 only
        // is possible for random access iterators (so we limit usability)
        void operator++() { ++b; if(b != e) ++b; }

        // operator* and operator-> (both return *b), post-increment
        // (defined in terms of pre-increment), etc...
        // comparison: only needs to compare b iterators!

    private:
        C::iterator b;
        C::iterator e; // needed for comparison to avoid incrementing beyond!
        iterator(C::iterator b, C::iterator e) : b(b), e(e) { }
    };
    // const_iterator, too; possibly make a template of above
    // and derive const and non-const iterators from?

    even_odd_only(C& c) : c(c) { }

    iterator begin()
    {
        using std::begin;
        using std::end;
        using std::empty;
        auto b = begin(c);
        // should be self-explanatory:
        // skip first element in odd variant (if there is)
        if constexpr(IsOdd) { if(!empty(c)) { ++b; } }
        return iterator(b, end(c));
    };
    iterator end()
    {
        using std::end;
        return iterator(end(c), end(c));
    }
};

template <typename T>
using even_only = even_odd_base<T, false>;
template <typename T>
using odd_only = even_odd_base<T, true>;

As is, it would work even with non-random-access and even non-bidirectional iterators. But especially for RA-iterators, it's less efficient than the classic loop (due to the intermediate if in operator++).

Defining comparison iterators: always operator== and operator!=, only for random access operators you can additionally have operator[<|>|<=|>=] (→ std::enable_if).

You'll find more details about how to write an iterator here – keep in mind when you encounter, though, that std::iterator itself is deprecated now.

Cari

Thanks, this is basically what I would like to see. It only seems to me that it makes sense to add more explanations as to how it works. This will increase the value of the answer. – Carhart

@DmytroDadyka Hm, considered it self-explanatory... - but OK, added a few lines. – Cari

Answer 2

As for what you are currently asking; I do not believe anything exists yet. Now as for iterating over a container by some integer N we can do the following; we can write our own for_each type of function. I've written one below and it works like a gem! You may also want to look into the std::advance function as well for it can be another possible implementation. I was checking that out myself as I was writing this function. However; as for c arrays I'm not sure there is much one can do without a bunch of extra code such as class templates, wrappers, etc. Here is my function.

#include <array>
#include <vector>
#include <iterator>

template<typename Container, typename Function>
void for_each_by_n( Container&& cont, Function f, unsigned increment_by = 1) {
    if ( increment_by == 0 ) return; // must check this for no op

    using std::begin;
    auto it = begin(cont);

    using std::end;
    auto end_it = end(cont);

    while( it != end_it ) {
        f(*it);
        for ( unsigned n = 0; n < increment_by; ++n ) {
            if ( it == end_it ) return;
            ++it;
        }
    }
}

int main() {
    std::array<int,8> arr{ 0,1,2,3,4,5,6,7 };
    std::vector<double> vec{ 1.2, 1.5, 1.9, 2.5, 3.3, 3.7, 4.2, 4.8 };

    auto l = [](auto& v) { std::cout << v << ' '; };

    for_each_by_n(arr, l); std::cout << '\n';
    for_each_by_n(vec, l); std::cout << '\n';

    for_each_by_n(arr, l, 2); std::cout << '\n';
    for_each_by_n(arr, l, 4); std::cout << '\n';

    for_each_by_n(vec, l, 3); std::cout << '\n';
    for_each_by_n(vec, l, 5); std::cout << '\n';

    for_each_by_n(arr, l, 8); std::cout << '\n';
    for_each_by_n(vec, l, 8); std::cout << '\n';

    // sanity check to see if it doesn't go past end.
    for_each_by_n(arr, l, 9); std::cout << '\n';
    for_each_by_n(vec, l, 9); std::cout << '\n';

    return 0;
}

-Output-

 0 1 2 3 4 5 6 7
 1.2 1.5 1.9 2.5 3.3 3.7 4.2 4.8
 0 2 4 6 
 0 4
 1.2 2.5 4.2
 1.2 3.7
 0
 1.2
 0
 1.2

What I like about this example above is that not only can you increment through a loop by some integer N; the above function also takes a function pointer, function object, functor, or lambda and it will perform the required action.

In your case you was trying to loop through your container by 2 for ever odd or every even index and within the loop you were printing the results. Here in my example; I'm printing the results in the form of a lambda that is being passed to this function.

However the only caveat with this particular implementation is that it will always start from index 0. You could easily expand on this by introducing another integer parameter as to an offset of where the iteration will begin; but I'll leave that up to you to do as an exercise.

For the time being we have to settle for what C++11 through C++17 has to offer. In the near future we should have many new and powerful features with the release of C++20.

Macaronic

Well the code looks clean, very readable, it does what it says, it's easy to maintain, and easy enough to expand upon. It also remains generic in nature towards any container's that has a begin and end iterator in which most cases is almost all std::container's... It doesn't rely on size, it doesn't rely on forward, reverse or two way iterators, just the normal basic iterators. It is also versatile due to the fact that you can pass any function to it to do the work you want just as I have shown with printing. It could be a sort, a search, a write to file, etc. and lambdas make it real nice. – Macaronic

Like that, too. There's an optimisation possibility for random access iterators, though, we might select in a constexpr if ('if RA-tag is supported'): if(distance(it, end_it) < increment_by) it += ...; /*or std::advance(...);*/ else it = end_it; – Cari

@Cari … or, going one step further and keeping a modular design: Define an algorithm limit_advance(iter, end, n) that contains the RA optimization. – Cottonwood

Answer 3

There is a ready-made solution for this problem in the Range-v3. I think this can be useful if you don’t want to write your own implementation or need more flexibility (f.e. arbitrary stride)

#include <range/v3/all.hpp>

void example()
{
    int data[8] = {0, 1, 2, 3, 4, 5, 6, 7};
    for (auto i : ranges::view::stride(data, 2))
    {
        std::cout << i << std::endl;
    }
}

(copied from @hlt comment)

Carhart

Answer 4

This isn't really an answer to the question, but—for what it is worth—whenever I run into a limitation of ranged-for, I look for a standard algorithm solution. Like...

#include <algorithm>
#include <iostream>
#include <iterator>
#include <utility>

int main()
{
    int arr[] {0, 1, 2, 3, 4, 5, 6, 7};
    std::copy_if(
        std::begin(arr), std::end(arr),
        std::ostream_iterator<int>(std::cout, "\n"),
        [is_odd_element = true](int n) mutable {
            return std::exchange(is_odd_element, not is_odd_element);
        });
}

Slippery

Hmm...I think technically I shouldn't wrapped that lambda in a std::ref call. – Slippery

Wow! This is of course too cumbersome, but it still works! – Carhart

Maybe it is too cumbersome for this problem, though I don’t know that I agree. But I think the approach might be better for a similar but more complex problem, so it is useful to learn to think about this kind of solution. Even more, I think thinking about solutions in this manner is a step towards the way we’ll need to think to make the best use of ranges. (I suspect there’s a ranges-based solution that doesn’t use an explicit loop.) – Slippery