Reversing range-based for loop on a custom container class

Question

I'm trying to improve my C++ skills by porting the major examples in Algorithms, 4th Edition by Sedgewick and Wayne. I wrote a generic stack implementation based on their Java example.

My stack works fine, but I'd like to make a performance improvement and got stuck trying to write a reverse iterator.

template<typename T> class ResizingArrayStack {
public:
    T* begin() { return &array_ptr[0]; }
    T* end() { return &array_ptr[N]; }

...

// Here we're iterating forward through the array, with an unused variable `i`.
// It would be nice performance-wise to iterate in reverse without calling pop(), and without triggering a resize.
for ( auto& i : lifo_stack ) {
    cout << "Current loop iteration has i = " << i << endl;
}
// // Alternatively, pop from the stack N times.
// cout << "Popped an item from the stack: " << lifo_stack.pop() << endl;

I tried switching the begin and end member functions above, but found that the expanded for-loop always increments with ++__begin, even if __end is at a lower memory address. How can we get i to loop in reverse (LIFO with respect to the stack)?

Please feel free to comment on my code style if there are egregious errors or aspects that look out of date. I want stay in-line with good 'modern' C++.

Answer 1

If you want to use the range-for loop with reverse iterators, you can use a wrapper class Reverse that stores a range and returns the reverse_iterators corresponding to begin and end

#include <iostream>
#include <iterator>
#include <vector>

template<class Rng>
class Reverse
{
    Rng const& rng;    
public:    
    Reverse(Rng const& r) noexcept
    : 
        rng(r)
    {}

    auto begin() const noexcept { using std::end; return std::make_reverse_iterator(end(rng)); }
    auto end()   const noexcept { using std::begin; return std::make_reverse_iterator(begin(rng)); }
};

int main()
{
    std::vector<int> my_stack;
    my_stack.push_back(1);
    my_stack.push_back(2);
    my_stack.push_back(3);

    // prints 3,2,1
    for (auto const& elem : Reverse(my_stack)) {
        std::cout << elem << ',';    
    }
}

Live Example

Note that this uses C++1z template deduction, only supported by g++ 7.0 SVN and clang 5.0 SVN. For earlier compilers you could add a helper function

    template<class Rng>
    auto MakeReverse(Rng const& rng) { return Reverse<Rng>(rng); }

    for (auto const& elem : MakeReverse(my_stack)) {
        std::cout << elem << ',';    
    }

Live Example (works as of gcc 5.1 or clang 3.5)

Alternatively, you can use the Boost.Range library and simply do (will work any C++11 compiler)

#include <iostream>
#include <vector>
#include <boost/range/adaptor/reversed.hpp>

int main()
{
    std::vector<int> my_stack;
    my_stack.push_back(1);
    my_stack.push_back(2);
    my_stack.push_back(3);

    for (auto const& elem : boost::adaptors::reverse(my_stack)) {
        std::cout << elem << ',';    
    }
}

Live Example

Note that you have to be careful about passing temporary variables to such adaptors, both mine and the Boost adaptor do not work when passing e.g. a raw std::vector<int>{3,2,1}, as pointed out by @Pixelchemist in the comments.