Copy std::stack into an std::vector

Question

Is the following code guaranteed by the standard to work(assuming st is not empty)?

#include <vector>
#include <stack>
int main()
{
   extern std::stack<int, std::vector<int> > st;
   int* end   = &st.top() + 1;
   int* begin = end - st.size();
   std::vector<int> stack_contents(begin, end);
}

Solution 1

Yes.

std::stack is just a container adapter.

You can see that .top() is actually (§23.3.5.3.1)

reference top() { return c.back(); }

Where c is the container, which in this case is a std::vector

Which means that your code is basically translated into:

   extern std::vector<int> st;
   int* end   = &st.back() + 1;
   int* begin = end - st.size();
   std::vector<int> stack_contents(begin, end);

And as std::vector is guaranteed to be continuous there should be no problem.

However, that does not mean that this is a good idea. If you need to use "hacks" like this it is generally an indicator of bad design. You probably want to use std::vector from the beginning.

Solution 2

Only std::vector is guaranteed by C++03 to have contiguous elements (23.4.1). In C++1x this will be extended to std::string as well (defect #530).

Solution 3

Yes, it's guaranteed. Vectors are guaranteed to use contiguous storage, so your code will work. It's a bit cludgy though - and if someone changes the underlying container type of the stack, your code will continue to compile without errors, yet the runtime behaviour will be broken.

Solution 4

I don't have a reference to the standard to back this up unfortunately, but there aren't many ways in which it could go wrong I guess:

• Specifying std::vector<int> as the container type means that the elements must be stored in a std::vector<int>.
• st.top() must return a reference to an element in the underlying container (i.e. an element in the std::vector<int>. Since the requirements on the container are that it supports back(), push_back() and pop_back(), we can reasonably assume that top() returns a reference to the last element in the vector.
• end therefore points to one past the last element.
• start therefore points to the beginning.

Conclusion: Unless the assumption was wrong, it must work.

EDIT: And given the other answer's reference to the standard, the assumption is correct, so it works.

Solution 5

According to this page, std::stack uses a container class to store elements.

I guess what you suggest works only if the containter store its elements in a linear way (std::vector).

As a default, std::stack uses a std::deque which, as far as I know, doesn't meet this requirement. But If you specify a std::vector as a container class, I can't see a reason why it shoudln't work.

View more solutions

Comments

[John Dibling]

+1 you could have just edited your deleted response & undeleted that.

[ronag]

I see, will do that in the future.

[Stuart Golodetz]

That's why he specified std::vector<int> as the container type I guess :)

[ereOn]

@sgolodetz: Just realized this ;) I'm still not fully awake right now.

[Armen Tsirunyan]

Wow, I never knew string had no such guarantee. Interesting, thanks. Upvoting, although this is irrelevant to my question

[Bogatyr]

Some algorithms dictate the use of a stack, and need to return the stacked elements in some other (usually array or vector) form at the conclusion (e.g., topological sort of a DAG). Doing so using the standard stack adapter instead of rolling your own is IMHO preferred. Manually popping all the elements off of the stack at the end is slower than necessary, and considering the code here is completely compliant and correct, I see nothing wrong with it. It's a good pattern to keep in one's toolbox when needed.