What's the Right Behavior of Reference to the Return Value of stack.top() in C++

Question

I am confused by the reference to the top element of a stack.

#include <iostream>
#include <stack>
using namespace std;

int main()
{
    stack<int> s;
    s.push(1);

    int        x = s.top();
    int&       y = s.top();
    const int& z = s.top();

    cout << x << '\t' << y << '\t' << z << endl;

    s.pop();
    s.push(2);

    cout << x << '\t' << y << '\t' << z << endl;
}
/* Output:
1       1       1
1       2       2
 */

I thought the reference to the top element should NOT be changed, but after a new element is pushed to the stack, the value that reference refers to is changed.

This is weird to me, because if the type is NOT int for the stack, say it's type of MyClass (very big data), is there a way to safely refer to the old top element? (Because I don't want to make an expensive copy operation).

I guess this behavior might be implementation-dependent, sign!

Saving references are like saving iterators - not guaranteed to still work correctly after the container is modified. — Jonathan Potter, Aug 12 '13 at 05:42
@JonathanPotter: That depends on the container. E.g. `std::list` guarantees it for all non-removed iterators (and obviously, any container invalidates iterators to removed elements) — MSalters, Aug 12 '13 at 06:54
Wait a minute: are you expecting Java behavior here? The value `1` is removed from the stack. Are you expecting that `int& y` somehow prevents garbage collection? — MSalters, Aug 12 '13 at 06:57

score 3 · Accepted Answer · edited May 23 '17 at 10:25

As stated in the C++11 standard (23.6.5.2 - stack definition)

reference top() { return c.back(); }
const_reference top() const { return c.back(); }
...
void push(const value_type& x) { c.push_back(x); }
void push(value_type&& x) { c.push_back(std::move(x)); }
...
void pop() { c.pop_back(); }

Where you are using the default underlying container std::deque, iterator/reference invalidation rules states that (quoting from this answer):

deque: erasing the last element invalidates only iterators and references to the erased elements and the past-the-end iterator; erasing the first element invalidates only iterators and references to the erased elements; erasing any other elements invalidates all iterators and references (including the past-the-end iterator) [23.3.3.4/4]

By using std::stack::pop, you are necessarily calling std::deque::pop_back() which, as said above, invalidates the reference previously returned by std::stack::top (which subsequently calls std::deque::back()). Therefore, you should never rely on this behavior, as it is undefined, not portable, and is wrong.

The solution if you want to have the original value of the stack's top is to therefore copy the top element, and not have a reference to it. That is, if you want to correctly retain the original value after you have popped an element out of the stack.

score 2 · Answer 2 · answered Aug 12 '13 at 05:41

2

After pop() the references are invalid. The output shows the newly pushed value due to implementation details of the std::stack - do not rely on it, it could be rubbish, too.

answered Aug 12 '13 at 05:41

What's the Right Behavior of Reference to the Return Value of stack.top() in C++

2 Answers2