开发者

Copy std::stack into an std::vector

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


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.


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


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.


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.


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.


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

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜