Manipuler beaucoup d'éléments dans std::stack

Question

Can C++ std::stack gérer plus de 10k int items ? Et qu'en est-il de ses performances ?

Answer 1

10K quoi ? La plupart des implémentations de std::stack pourraient facilement gérer 10K primitives avec de bonnes performances, puisque c'est probablement < 80KB. Cependant, la norme ne garantit pas les performances.

Notez également que cela dépend du backend que vous utilisez. La valeur par défaut est std::deque, qui est en fait un tableau de tableaux. Cependant, vous devriez obtenir des performances décentes avec n'importe quel backend.

Answer 2

A std::stack n'est limitée que par le conteneur sous-jacent (un std::stack est un adaptateur de conteneur).

Selon la nature du conteneur sous-jacent, vous aurez des limites différentes.

A std::vector nécessitera une mémoire contiguë, tandis qu'une std::list ne sera limitée que par la taille du tas (et éventuellement par toute fragmentation du tas). Mais std::deque (le conteneur par défaut) se situe entre les deux ; il nécessite de plus petits morceaux de mémoire contigus mais sera principalement limité par la taille du tas.

Answer 3

Les performances dépendent du conteneur sous-jacent utilisé. Comme déjà mentionné, stack est un adaptateur, le conteneur sous-jacent peut être deque (par défaut), ou vector ou list (tous en std ).

Voici un exemple de comparaison des performances. Comme le type à stocker n'est pas clairement mentionné dans la question, je suppose que c'est un int non signé. N'hésitez pas à le modifier selon vos besoins. L'exemple construit une pile de 100K éléments.

Contenu de 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;
}

Comparaison des exécutions :

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

Les chiffres ci-dessus sont le résultat d'un seul passage. Pour obtenir des chiffres statistiquement significatifs, exécutez chaque variation un grand nombre de fois, et observez la moyenne et l'écart-type.

Apparemment, deque y vector donne des résultats similaires, alors que list est pire.

Answer 4

Oui, il peut supporter 10 000. Tant que vous avez les ressources mémoire pour cela. Si vous craignez qu'il utilise la pile interne, il ne le fait pas.

Les performances dépendent de la mise en œuvre, mais devraient être très rapides.

Answer 5

Std::stack n'est pas un conteneur, mais un adaptateur de conteneur. Par défaut, elle utilise un std::deque comme conteneur, mais vous pouvez aussi utiliser un std::vector ou un std::list. Les deques libèrent leur mémoire lorsque des éléments sont supprimés.