Handling lot of items in std::stack

Can C++ std::stack handle more than 10k int items? And how about its performance?开发者_StackOverflow社区

10K what? Most std::stack implementations could easily handle 10K primitives with good performance, since that's probably < 80KB. However, the standard doesn't guarantee performance.

Also note that it depends what backend you use. The default is std::deque, which is basically an array of arrays. However, you should get decent performance with any backend.

A std::stack is only limited by the underlying container (a std::stack is a container adapter).

Depending on what the underlying container is, you'll have different limits.

A std::vector will require contiguous memory whereas a std::list will only be limited by the size of the heap (and possibly any heap fragmentation). But std::deque (the default container) is between the two; it requires smaller chunks of contiguous memory but will primarily be limited by the size of the heap.

The performance depends on the underlying container used. As already mentioned, stack is an adapter, the underlying container can be deque (the default), or vector, or list (all in std namespace).

Following is an example of performance comparison. As the type to be stored is not clearly mentioned in the question, I am assuming it to be unsigned int. Feel free to change it per your requirements. The example constructs a stack of 100K items.

Contents of 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;
}

Execution comparison:

$ 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
$ 

The above numbers are result of single run. To achieve statistically significant numbers run each variation large number of times, and observe the mean and standard deviation.

Apparently, deque and vector results in similar performance, whereas list is worse.

Yes, it can handle 10k. As long as you have the memory resources for it. If you are worried it uses the internal stack, it doesn't.

Performance is implementation specific, but should be very quick

std::stack is not a container, but a container adapter. By default it uses an std::deque as container, but you can also use a std::vector or std::list. Deques free their memory when elements are removed.