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);
}

score 11 · Accepted Answer · edited Dec 03 '10 at 13:45

11

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.

edited Dec 03 '10 at 13:45

Armen Tsirunyan

130,161
59
324
434

answered Dec 03 '10 at 13:42

ronag

49,529
25
126
221

1

+1 you could have just edited your deleted response & undeleted that. – John Dibling Dec 03 '10 at 13:44
I see, will do that in the future. – ronag Dec 03 '10 at 13:46
1

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. – Bogatyr Jul 23 '19 at 19:56

score 6 · Answer 2 · answered Dec 03 '10 at 13:49

6

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

answered Dec 03 '10 at 13:49

Daniel Lidström

9,930
1
27
35

2

Wow, I never knew string had no such guarantee. Interesting, thanks. Upvoting, although this is irrelevant to my question – Armen Tsirunyan Dec 03 '10 at 13:50

score 2 · Answer 3 · answered Dec 03 '10 at 13:42

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.

score 2 · Answer 4 · answered Dec 03 '10 at 13:43

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.

score 1 · Answer 5 · answered Dec 03 '10 at 13:44

1

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.

answered Dec 03 '10 at 13:44

ereOn

53,676
39
161
238

3

That's why he specified `std::vector` as the container type I guess :) – Stuart Golodetz Dec 03 '10 at 13:46
@sgolodetz: Just realized this ;) I'm still not fully awake right now. – ereOn Dec 03 '10 at 13:47

SingleNegationElimination · Answer 6 · 2010-12-03T13:51:18.907

Edit: initial statement redacted, the standard actually does provide a full definition for the stack adaptor, nothing left to implentors. see top answer.

You want a container that has a push and pop method and allows you to inspect elements anywhere in the container and uses a std::vector for storage. There is such a container in the standard template library

it is called std::vector.

Use std::stack only for bondage purposes

Copy std::stack into an std::vector

6 Answers6

Linked