Is std::stack contiguous?

user_10251345 0
Viewed 379

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?

stdstack c++
2 Answers

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

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.

user_16251870
Related