std::stack 是连续的吗？

Question

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

然后我才知道std::stack没有begin()和end()功能。在网上冲浪后，我看到了一个黑客：

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

好像可以用，网上可以看看。

但是当我提交我的代码时，它在一些测试用例中失败了。std::stack真的是连续的吗？

Answer 1

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

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

类模板充当底层容器的包装器

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

双端队列的元素不是连续存储的

所以，

stack<int> s;

是不连续的，因为std::deque是不连续的。

然而，

典型的实现（of std::deque）使用一系列单独分配的固定大小的数组

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

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

例如，

stack<int, vector<int>> s;

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

TLDR

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

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