Reverse iterators for C arrays

Question

For traversing a C array using STL functions, the std::begin and std::end functions are quite handy equivalents of .begin() and .end(). However, there are no std::rbegin and std::rend equivalents of the reverse iterators for bidirectional C++ containers. Does such an equivalent exist under some other name, or is one easily made? I realize one difficulty is that std::begin generally returns a raw pointer, and for the reverse case this would need a wrapper so that the ++ operation could be overloaded. A very incomplete implementation might look like

template<class T>
class ReverseArrayIterator {
public:
    ReverseArrayIterator(T* ptr) : _ptr(ptr) {}
    operator T*() {
        return _ptr;
    }
    void operator++() {
        --_ptr;
    }
    T operator*() {
        return *_ptr;
    }
    bool operator!= (ReverseArrayIterator& rhs) {
        return _ptr != rhs._ptr;
    }
private:
    T* _ptr;
};

template<class T, size_t size>
ReverseArrayIterator<T> rbegin(T (&array)[size]) {
    return ReverseArrayIterator<T>(&array[0] + size - 1);
}

template<class T, size_t size>
ReverseArrayIterator<T> rend(T (&array)[size]) {
    return ReverseArrayIterator<T>(&array[0] - 1);
}

I tested this bare-bones implementation with the following code:

int x[] = {1,2,3,4,5,6,0,0,0,10,11,12};
auto a = std::find(std::begin(x),std::end(x),0);
auto b = std::find(rbegin(x),rend(x),0);
cout << std::distance(x,a) << endl;
cout << std::distance(x,(int*)b) << endl;

Could this be fleshed out into a fully operational reverse-iterator class for C arrays, or will I run into further obstacles down the road? One possible roadblock seems to be implicit conversion to raw pointers, which I'd hoped would be used in functions like std::distance -- the above snippet won't compile with std::distance(x,b) (or similar functions, presumably) but needs the manual (int*) cast.

[They exist in C++14.](http://en.cppreference.com/w/cpp/iterator/rbegin) — chris, Oct 17 '17 at 15:20
@chris Ah, thanks; somehow I did not find that through google... — jwimberley, Oct 17 '17 at 15:20
[There's also an existing adapter](http://en.cppreference.com/w/cpp/iterator/make_reverse_iterator) — StoryTeller - Unslander Monica, Oct 17 '17 at 15:21
@StoryTeller: IMO it's better to suggest just using a span rather than bothering with individual iterator adapters for this. — einpoklum, Oct 10 '19 at 13:02
Additionally, it is also worth noting that in C++, for an array arr[N], the only addressable locations are arr till (arr+N). See this link https://devblogs.microsoft.com/oldnewthing/20211112-00/?p=105908 . Hence, your implementation is undefined behavior as it references (arr - 1) till (arr + (N-1)) — Jia Cheng Sun, Dec 25 '22 at 10:14

score 2 · Answer 1 · answered Oct 10 '19 at 12:39

(I'm turning the comments into an answer to help others. Credits to chris and StoryTeller.)

Since C++14 there are rbegin() and rend() just like you describe.

There is also an adapter class to convert a (forward) iterator into a reverse iterator. Please note the forward begin() iterator should be passed to make_reverse_iterator to make the reverse iterator, and vice versa:

    std::vector<int> v{ 1, 3, 10, 8, 22 };

    std::copy(
        std::make_reverse_iterator(v.end()), 
        std::make_reverse_iterator(v.begin()),
        std::ostream_iterator<int>(std::cout, ", "));

Hmm, apparently this got on the homepage after you answered, two years after the question was posted... but then that got me to write my own answer. No offense! :-P — einpoklum, Oct 10 '19 at 14:17

einpoklum · Answer 2 · 2019-10-10T13:05:32.057

Use a span to wrap your array, and don't bother with hand-rolling the kind of code you suggest.

Spans are lightweight wrappers for contiguous sequences of values in memory, providing you with all the "amenities" of a standard library container over those values - including reverse iterators, ranged for loops and so on.

Spans have entered the standard in C++20, but you asked about C++11, so you can use the C++ guidelines support library's span, e.g. from the GSL-lite implementation, that supports C++11 (Microsoft's GSL doesn't).

Spans are reference-types and are extremely lightweight - and very often just get optimized away. So using a span often won't cost you anything.

In your example, with a span, you can rewrite the code as follows:

#include <iterator>
#include <gsl/gsl-lite.hpp>
#include <iostream>

int main()
{
    int raw_x[] = {1, 2, 3, 4, 5, 6, 0, 0, 0, 10, 11, 12};
    auto x = gsl::span<int>{raw_x};
    auto a = std::find(x.begin(), x.end(),0);
    auto b = std::find(x.rbegin(), x.rend(),0);
    std::cout << std::distance(x.begin(), a) << std::endl;
    std::cout << std::distance(x.rend(), b) << std::endl;    
}

and this compiles (GodBolt).

Note I used the rbegin() and rend() members rather than std::rbegin() and std::rend() since the latter are not yet standardized in C++11.

Reverse iterators for C arrays

2 Answers2