Reversing range-based for loop on a custom contain

问题:

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++.

回答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.

回答2:

Here a scratch for your problem. Don't consider this as working code. Use it to just get an idea of how reverse iterator MAY be implemented (just one many possible ways).

template<typename T> class ResizingArrayStack {
public: 
    class reverse_iterator
    {       
        ResizingArrayStack & _storage;
        int _pointer;

    public:
        inline reverse_iterator(ResizingArrayStack & storage,
                                int pointer)
            : _storage(storage)
            , _pointer(pointer)
        {}

        inline reverse_iterator & operator++() // prefix
        {
            --_pointer;
            return *this;
        }

        inline reverse_iterator operator++() // postfix
        {
            reverse_iterator tmp(*this);
            --_pointer;
            return tmp;
        }

        inline T & operator*()
        {
            return _storage.getByIndex(_pointer);
        }

        // TODO: == != etc
    };      

    reverse_iterator rbegin() { return reverse_iterator(*this, N - 1); }
    reverse_iterator rend() { return reverse_iterator(*this, -1); }
    // ...  //
};

回答3:

once you have functioning (regular) iterators, implement reverse iterators using the standard library helper class template std::reverse_iterator

#include <iterator>

class XX { 

    // your code

    typedef std::reverse_iterator<iterator> reverse_iterator;

    reverse_iterator rbegin() { return reverse_iterator{end()}; }
    reverse_iterator rend() { return reverse_iterator{begin()}; }

回答4:

Looking at your full codelifo_stack.pop() invalidates your iterators, so it cannot be used inside a ranged for. You have Undefined Behavior

Moreover it doesn't make much sense to use a range for for a stack. If you can iterate over its elements then it's not a stack now isn't it? A stack has the property that you can only access the most recent inserted element.

---

Based on your comment:

Consider the case where you add items slowly and individually, but wish to dump them out of the stack as quickly as possible. I don't want the overhead of copying and resizing arrays which pop() would trigger at that moment.

I still think that ranged-for does not make sense for a stack.

Here is how I see your problem solved:

lifo_stack.disable_resizing(); // prevents resizing 
while (!lifo_stack.is_empty()
{
    lifo_stack.pop(); // maybe use the poped element
}
lifo_stack.enable_resizing(); // re-enables resizing and triggers a resize

If you don't need the popped elements and just want to emtpy the stack, there is a faster way (based on your class implementation):

// empties the stack
void clear()
{
   delete[] array_ptr;
   array_ptr = new T[1];;
   max_size = 1;
   N = 0;
}

One last final though if you want to use modern C++ then use unique_ptr instead of manual new and delete. It is easier but most importantly safer. And read on the rule of 0/3/5.

回答5:

This solution does not introduce unnecessary copies and does not exhibit incorrect forwarding as suggested by some comments. Explanation below.

You can use some wrapper which has begin and end functions that actually return reverse iterators.

template<class T>
struct revert_wrapper
{
    T o;
    revert_wrapper(T&& i) : o(std::forward<T>(i)) {}
};

template<class T>
auto begin(revert_wrapper<T>& r)
{
    using std::end;
    return std::make_reverse_iterator(end(r.o));
}

template<class T>
auto end(revert_wrapper<T>& r)
{
    using std::begin;
    return std::make_reverse_iterator(begin(r.o));
}

template<class T>
auto begin(revert_wrapper<T> const& r) 
{ 
    using std::end;
    return std::make_reverse_iterator(end(r.o));
}

template<class T>
auto end(revert_wrapper<T> const& r)
{
    using std::begin;
    return std::make_reverse_iterator(begin(r.o));
}

template<class T>
auto reverse(T&& ob)
{
    return revert_wrapper<T>{ std::forward<T>(ob) };
}

Used like this:

std::vector<int> v{1, 2, 3, 4};
for (auto i : reverse(v))
{
    std::cout << i << "\n";
}

or in your case

for ( auto& i : reverse(lifo_stack) ) {
    cout << "Current loop iteration has i = " << i << endl;
    cout << "Popped an item from the stack: " << lifo_stack.pop() << endl;
}

---

Since fowarding is not an easy topic and there is misconception around I'll further explain some details. I'll use std::vector<int> as an example for the "to be reversed" type T.

1. The function template reverse.

1.1 Passing an lvalue std::vector<int>:

std::vector<int> v{1, 2, 3, 4};
auto&& x = reverse(v);

The compiler created instance of reverse in this case would look like:

template<>
auto reverse<std::vector<int>&>(std::vector<int>& ob)
{
    return revert_wrapper<std::vector<int>&>{ std::forward<std::vector<int>&>(ob) };
}

We see two things here:

• The T of revert_wrapper will be std::vector<int>&, so no copy involved.
• we're forwarding an lvalue as an lvalue to the constructor of revert_wrapper

1.2 Passing an rvalue std::vector<int>

std::vector<int> foo();
auto&& x = reverse(foo());

We look again at the instantiation of the function template:

template<>
auto reverse<std::vector<int>>(std::vector<int>&& ob)
{
    return revert_wrapper<std::vector<int>>{ std::forward<std::vector<int>>(ob) };
}

And can again note two things:

• The T of revert_wrapper will be std::vector<int>, thus copy the vector, preventing the rvalue from going out of scope before any range based loop can run
• an rvalue std::vector<int>&& will be forwarded to the constructor of revert_wrapper

 

2. The class template revert_wrapper and its constructor

2.1 The revert_wrapper created by reverse in case of an lvalue std::vector<int>&

template<>
struct revert_wrapper<std::vector<int>&>
{
    std::vector<int>& o;
    revert_wrapper(std::vector<int>& i) : 
        o(std::forward<std::vector<int>&>(i)) {}
};

As noted above: No copies involved as we store a reference. The forward also seems familiar and indeed it is just the same as above within reverse: We forward an lvalue as lvalue reference.

2.2 The revert_wrapper created by reverse in case of an rvalue std::vector<int>&&

template<>
struct revert_wrapper<std::vector<int>>
{
    std::vector<int> o;
    revert_wrapper(std::vector<int>&& i) : 
        o(std::forward<std::vector<int>>(i)) {}
};

This time we have the object stored by value to prevent a dangling reference. Also the forwarding is fine: We forwarded the rvalue reference from reverse to the revert_wrapper constructor and we forward it on to the std::vector constructor. We could've used static_cast<T&&>(i) in the same way but we're not (std::)mov(e)ing from an lvalue, we're forwarding:

• lvalues as lvalues and
• rvalues as rvalues.

We can also see one more thing here: The only available constructor of the revert_wrapper instance that stores by value takes an rvalue. Therefore, we can't (easily) trick this class to make unnecessary copies.

Note that replacing std::forward with std::move inside the initializer of o in the revert_wrapper constructor would actually be wrong.

回答6:

Please see an excellent answer from TemplateRex here. I was able to solve the problem without a wrapper class, so I'll give a shot at answering my own question.

Here is the most helpful example I found on implementing iterators at http://en.cppreference.com, and you can find my updated ResizingArrayStack code at the same GitHub link as found the question.

template<typename T> class ResizingArrayStack {
public:

    //----- Begin reversed iteration section -----//
    // Please see the example here, (http://en.cppreference.com/w/cpp/iterator/iterator).
    // Member typedefs inherit from std::iterator.
    class stackIterator: public std::iterator<
                        std::input_iterator_tag,   // iterator_category
                        T,                         // value_type
                        T,                         // difference_type
                        const T*,                  // pointer
                        T                          // reference
                        >{
        int index = 0;
        T* it_ptr = nullptr;
    public:
        // Prefix ++, equal, unequal, and dereference operators are the minimum required for range based for-loops.
        stackIterator(int _index = 0, T* _it_ptr = nullptr) { index = _index; it_ptr = _it_ptr; }
        // Here is where we reverse the sequence.
        stackIterator& operator++() { --index; return *this; }
        bool operator==(stackIterator other) { return index == other.index; }
        bool operator!=(stackIterator other) { return !( *this == other ); }
        T operator*() { return it_ptr[index-1]; }
    };

    stackIterator begin() { return stackIterator(N, array_ptr); }
    stackIterator end() {
        N = 0;  // 'Empty' the array.
        max_size = 1;  // Don't waste time calling resize() now. 
        return stackIterator(0, array_ptr);
    }
    //----- End reversed iteration section -----//

private:
    // Allocate space for a traditional array on the heap.
    T* array_ptr = new T[1];
    // Keep track of the space allocated for the array, max_size * sizeof(T).
    int max_size = 1;
    // Keep track of the current number of items on the stack.
    int N = 0;

Calling code where the range based for-loop iterates in reversed (or LIFO) order by default.

// It's nice performance-wise to iterate in reverse without calling pop() or triggering a resize.
for ( auto i : lifo_stack) {
    cout << "Current loop iteration has i = " << i << endl;
}