std::stack 是连续的吗？

Question

我想找到堆栈中的最大元素，并想到使用std::max_element。

然后我才知道std::stack没有begin()和end()的功能。上网后看到了一个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);

它似乎确实有效，你可以 see it online。

但是当我提交我的代码时，它没有通过一些测试用例。 std::stack真的是连续的吗？

Answer 1

取决于std::stack的底层容器：

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

The class template acts as a wrapper to the underlying container

默认情况下，Container = deque<T>。并且 std::deque 不连续：

the elements of a deque are not stored contiguously

因此，

stack<int> s;

不连续因为std::deque不连续。

然而，

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

这就是一些测试用例失败的原因；当堆栈增长超过底层固定大小数组之一的大小时，连续性中断。

如果底层容器被明确指定（标准容器std::vector和std::list满足除std::deque之外的要求）并且如果该容器是连续的，那么该堆栈也是连续的。

例如，

stack<int, vector<int>> s;

是连续的因为std::vector是连续的。

TLDR

std::stack 的连续性由其底层容器的连续性决定。

_{我还要感谢社区向我展示了人们如何找到此类编程问题的答案，并使我能够从参考资料中挖掘解决方案。}

Answer 2

std::stack 是连续的吗？我会说，没关系。 std::stack不是容器，而是适配器，其思想是栈抽象和接口的刻意限制。

即使它是连续的，以任何方式访问 std::stack 的元素，但 .top() 将违反其语义。如果您需要这样的访问权限，则首先不应使用 std::stack。不要混淆代码的 reader。

std::stack 是连续的吗？

Is std::stack contiguous?

c++

stdstack

TLDR