4

I wanted to find the maximum element in a stack, and thought of using std::max_element.

Then I came to know that std::stack does not have begin() and end() functions. After surfing the net, I saw a hack:

stack<int> s({0, 1, 2, 3, 4, 5, 6, 7, 8, 9});
auto end = &s.top() + 1;     // instead of std::end
auto begin = end - s.size(); // instead of std::begin
cout << "Max = " << *max_element(begin, end);

It does seem to work, you can see it online.

But when I submitted my code, it failed some of the test cases. Is std::stack really contiguous?

Ardent Coder
  • 3,777
  • 9
  • 27
  • 53
  • 2
    Unrelated, but the goal of the problem was to use an algorithm to find the maximum element in the stack. This hack violates OOP principles. – Amal K Jun 20 '20 at 17:34
  • 2
    @OP You've missed the point of the question being asked. How do you find the maximum value in a stack if all you have is push/pop? You have little choice except to either keep track of the elements added to the stack, or take the values out, determine the maximum, and then put the values back into the stack. – PaulMcKenzie Jun 20 '20 at 17:41
  • 1
    More than likely, the solution would look [something like this](https://godbolt.org/z/CreE4f). Now it doesn't matter what the underlying container happens to be, as long as it satisfies what the `std::stack` container requires. – PaulMcKenzie Jun 20 '20 at 17:51
  • 1
    @OP Also, what is usually done is that you control the pushing of elements onto the original stack, and have a secondary stack record whenever the newly pushed item in the main stack is greater than the current max item. Then if you pop the maximum value off the main stack, you pop an item off the secondary stack, thus always keeping track of the maximum value. If this were an interview question, this is what the interviewer would be looking for, or at the very least, will ask you further about. – PaulMcKenzie Jun 20 '20 at 18:25
  • 2
    The very idea of `std::stack` is stack abstraction. Even if it were contiguous, accessing elements of `std::stack` by any means but `.top()` would be a violation of its semantics. If you need such an access, you should not use `std::stack` in the first place. – Evg Jun 20 '20 at 18:26
  • If you need to find the maximum element, `std::stack` is not the right data structure. – Pete Becker Jun 20 '20 at 18:29
  • @PaulMcKenzie I had initially thought about it, but the problem was that the program was kinda menu-driven i.e. they had the option to pop contents off the original stack. Hence, that trick sadly fails. – Ardent Coder Jun 20 '20 at 18:42
  • 1
    @ArdentCoder -- Probably the question was an algorithms one, but you had C++ as an option for the language, and thus you took a shortcut. It depends on the shortcuts you take if the language is C++ and the question is one on algorithms -- if you can find the correct set of STL algorithms to use to answer a question, then that's a different issue. Instead you used the low-level internals of a container to take a shortcut, and I would think that would "violate the rules". – PaulMcKenzie Jun 20 '20 at 19:24

2 Answers2

8

It depends on the underlying container of the std::stack:

template <class T, class Container = deque<T>> class stack;

The class template acts as a wrapper to the underlying container

By default, Container = deque<T>. And std::deque is not contiguous:

the elements of a deque are not stored contiguously

Therefore,

stack<int> s;

is not contiguous because std::deque is not contiguous.

However,

typical implementations (of std::deque) use a sequence of individually allocated fixed-size arrays

That is why some of the test cases failed; the contiguity broke when the stack grew more than the size of one of the underlying fixed-size arrays.

If the underlying container is specified explicitly (the standard containers std::vector and std::list satisfy the requirements apart from std::deque) and if that container is contiguous, then that stack is also contiguous.

For example,

stack<int, vector<int>> s;

is contiguous because std::vector is contiguous.

TLDR

The contiguity of std::stack is determined by the contiguity of its underlying container.

I would also like to thank the community for showing me ways of how people find answers to such programming questions and making me capable of digging solutions from references.
Ardent Coder
  • 3,777
  • 9
  • 27
  • 53
  • 2
    To be more specific, this is because all a stack is is a container _adapter_ - it doesn't implement a container itself, but rather augments (or _adapts_) the API of another container implementation. Much like all container adapters, the memory and complexity semantics depend entirely on the backing container implementation. – Qix - MONICA WAS MISTREATED Jun 20 '20 at 17:23
  • 1
    @Qix-MONICAWASMISTREATED Feel free to add your answer, I don't like accepting my own answers :P Btw, `stack> s;` helped me pass all test cases :) – Ardent Coder Jun 20 '20 at 17:25
  • 2
    @ArdentCoder You might as well just use `vector`. The whole point of a stack is that you only allow access to the top element. If you need to access elements in the middle then you shouldn't be using a stack. – eesiraed Jun 20 '20 at 17:40
  • 1
    Memory layout can also be about cpu cache performance characteristics - which for many practical problems overwhelms an algorithms supposed efficiency. This is a completely reasonable question to ask and a completely reasonable answer. I prefer your own self-researched answer over the other one given here. – Josh Jul 29 '20 at 03:24
  • @Josh I appreciate how you like my answer. The other answer has some guidance on the usage of Stack API with respect to the actual problem in my question, which can prevent the reader from getting a false impression from this answer that may seem like promoting such a usage of this container. Ticking that answer put that on top of our answer stack which collectively answers the question in the order of events that lead to the main question :P By the way, thanks for your added information :) – Ardent Coder Jul 29 '20 at 07:07
3

Is std::stack contiguous? I would say, it doesn't matter. std::stack is not a container, but an adapter, and its idea is the stack abstraction and a deliberate restriction of interfaces.

Even if it were contiguous, accessing elements of std::stack by any means but .top() would be a violation of its semantics. If you need such an access, you should not use std::stack in the first place. Don't confuse the reader of your code.

Evg
  • 25,259
  • 5
  • 41
  • 83
  • 1
    `I would say, it doesn't matter.` You can't assume that for every case, it does not matter. The rest of your answer is correct, but there might be times memory requirements of the platform dictate contiguous memory and thus this becomes a bit more important. Just a thought. – Qix - MONICA WAS MISTREATED Jun 22 '20 at 04:22
  • @Qix-MONICAWASMISTREATED, my point was that it doesn't matter *semantically*. The standard allows us to specify an underlying container. If for some reason `std::deque` is not the optimal choice, another container like `std::vector` can be used instead. But that is an implementation detail that should not influence the way `std::stack` is accessed. – Evg Jun 22 '20 at 05:50