处理 std::stack 中的大量项目

Question

C++ std::stack 可以处理超过 10k int 项吗？而它的表现又如何呢？

Answer 1

10K什么？大多数 std::stack 实现可以轻松处理 10K 基元并具有良好的性能，因为这可能小于 10K。 80KB。但是，该标准并不保证性能。

另请注意，这取决于您使用的后端。默认值是 std::deque，它基本上是一个数组的数组。但是，任何后端都应该获得不错的性能。

Answer 2

std::stack 仅受底层容器的限制（std::stack 是容器适配器）。

根据底层容器的不同，您将有不同的限制。

std::vector 将需要连续的内存，而 std::list 将仅受堆大小（以及可能的任何堆碎片）的限制。但 std::deque （默认容器）介于两者之间；它需要较小的连续内存块，但主要受到堆大小的限制。

Answer 3

性能取决于所使用的底层容器。正如已经提到的，stack是一个适配器，底层容器可以是deque（默认），或vector，或list< /code> （全部位于 std 命名空间中）。

以下是性能比较的示例。由于问题中没有明确提到要存储的类型，我假设它是 unsigned int。请随意根据您的要求进行更改。该示例构建了一个包含 100K 项的堆栈。

stack.cpp内容

#include <stack>
#include <vector>
#include <list>
#include <deque>
#include <assert.h>

typedef unsigned int Type;

#ifdef USE_VECTOR
typedef std::stack< Type, std::vector< Type > > StackType;
#elif USE_LIST
typedef std::stack< Type, std::list< Type > > StackType;
#else
typedef std::stack< Type, std::deque< Type > > StackType;
#endif

int main() {
    StackType mystack;
    for( unsigned int i = 0; i < 100 * 1024; ++i ) {
        mystack.push( i );
    }
    assert( mystack.size() == 100 * 1024 );
    return 0;
}

执行对比：

$ g++ -DUSE_VECTOR stack.cpp -o stack; time ./stack

real    0m0.023s
user    0m0.030s
sys     0m0.031s

$ g++ -DUSE_LIST stack.cpp -o stack; time ./stack

real    0m0.144s
user    0m0.186s
sys     0m0.030s

$ g++  stack.cpp -o stack; time ./stack

real    0m0.024s
user    0m0.030s
sys     0m0.015s

asaha@nedata8 ~/code
$ 

以上数字为单次运行结果。 为了获得统计上显着的数字，请多次运行每个变体，并观察平均值和标准偏差。

显然，deque 和 vector 会产生类似的结果性能，而 list 则较差。

Answer 4

是的，它可以处理 10k。只要你有足够的内存资源。如果您担心它使用内部堆栈，那么它不会。

性能取决于具体实现，但应该非常快

Answer 5

std::stack 不是容器，而是容器适配器。默认情况下，它使用 std::deque 作为容器，但您也可以使用 std::vector 或 std::list。当元素被删除时，双端队列释放它们的内存。