16

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

3
  • 1
    +1 you could have just edited your deleted response & undeleted that. – John Dibling Dec 3 '10 at 13:44
  • I see, will do that in the future. – ronag Dec 3 '10 at 13:46
  • 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
5

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

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

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.

2

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.

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.

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.