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++.
Looking at your full code
lifo_stack.pop()
invalidates your iterators, so it cannot be used inside a ranged for. You have Undefined BehaviorMoreover 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:
I still think that ranged-for does not make sense for a stack.
Here is how I see your problem solved:
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):
One last final though if you want to use modern C++ then use
unique_ptr
instead of manualnew
anddelete
. It is easier but most importantly safer. And read on the rule of 0/3/5.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.
Calling code where the range based for-loop iterates in reversed (or LIFO) order by default.
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).
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 thereverse_iterator
s corresponding tobegin
andend
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
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)
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.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.
Used like this:
or in your case
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" typeT
.1. The function template
reverse
.1.1 Passing an lvalue
std::vector<int>
:The compiler created instance of
reverse
in this case would look like:We see two things here:
T
ofrevert_wrapper
will bestd::vector<int>&
, so no copy involved.revert_wrapper
1.2 Passing an rvalue
std::vector<int>
We look again at the instantiation of the function template:
And can again note two things:
T
ofrevert_wrapper
will bestd::vector<int>
, thus copy the vector, preventing the rvalue from going out of scope before any range based loop can runstd::vector<int>&&
will be forwarded to the constructor ofrevert_wrapper
2. The class template
revert_wrapper
and its constructor2.1 The
revert_wrapper
created byreverse
in case of an lvaluestd::vector<int>&
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 withinreverse
: We forward an lvalue as lvalue reference.2.2 The
revert_wrapper
created byreverse
in case of an rvaluestd::vector<int>&&
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 therevert_wrapper
constructor and we forward it on to thestd::vector
constructor. We could've usedstatic_cast<T&&>(i)
in the same way but we're not(std::)mov(e)
ing from an lvalue, we're forwarding: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
withstd::move
inside the initializer ofo
in therevert_wrapper
constructor would actually be wrong.once you have functioning (regular) iterators, implement reverse iterators using the standard library helper class template
std::reverse_iterator