Où puis-je trouver une comparaison de la complexité des conteneurs STL (performance)?

Question

J'ai fait un googled assez longtemps pour trouver une comparaison qui montre les différences de complexité pour tous les conteneurs STL sur insert/push erase/pop etc. Je n'en ai trouvé aucun. Aussi pas dans tous mes livres STL. Un indice?

Je connais certaines règles de base bien sûr. Mais où est une définition?

Answer 1

Essayez avec

http://www.sgi.com/tech/stl/complexity.html

http://www.sgi.com/tech/stl/table_of_contents.html

De complexity.html:

Au fond, il est difficile de définir la notion de complexité asymptotique algorithme précisément pour réel matériel informatique au lieu d'un modèle de machine abstraite. Ainsi, nous nous installons les directives suivantes:

1. Pour un algorithme A pour avoir le temps en cours d'exécution O (f (n)), il doit y avoir un algorithme correspondant A » qui est correcte sur les machines avec arbitrairement longue types pointer et size_t, tels que que A et A 'exécutent essentiellement la même séquence d'opérations sur le matériel réel . (Dans les cas simples A et A « sera le même. Dans d'autres cas A peut avoir été simplifiée avec les connaissances que les adresses sont limitée.) Pour les entrées de suffisamment grande taille n, A » doit prendre au plus temps Cf (n), où C est une constante, indépendante de n et de l'adresse . (Pointeur, size_t et ptrdiff_t opérations sont présumés prendre temps constant indépendamment de leur taille .)
2. Tous les conteneurs ou les spécifications de complexité iterator font référence à amorti complexité. Une opération individuelle peut prendre plus de spécifié. Mais toute séquence d'opérations suffisamment longue sur le même conteneur ou itérateur prendra à le plus longtemps que la somme correspondante des coûts d'opération spécifiés.
3. Les algorithmes spécifient les performances dans le cas le plus défavorable ou le cas moyen, et identifient les performances. Sauf indication contraire, les moyennes supposer que les éléments conteneurs sont choisi parmi un type fini avec plus valeurs possibles que la taille du récipient , et que les éléments conteneurs sont indépendamment uniformément distribués.
4. Une spécification de complexité pour une opération f suppose que les opérations invoquées par f nécessitent au plus l'exécution spécifiée . Mais les algorithmes restent généralement appropriés si les opérations invoquées ne sont pas supérieures à un facteur logarithmique inférieur à spécifié dans le cas prévu.

5. Si les opérations sont plus coûteuses que celles assumées par une fonction F dans la STL actuelle , alors F ralentira à en proportion du coût supplémentaire. Toutes les opérations futures qui échouent à satisfont cette propriété, ce qui rendra explicite. Pour que ceci soit précis, supposons que F est spécifié pour utiliser le temps f (m) pour l'entrée de taille m. F utilise les opérations Gk, avec des durées spécifiées gk (n) sur taille d'entrée n. Si F est utilisé dans un contexte dans lequel chaque Gk est plus lent que prévu d'au plus un facteur h (n), alors F ralentit d'au plus un facteur h (m). Cela est vrai car aucun des algorithmes actuels n'appliquent les opérations Gk aux entrées significativement plus grand que m.

Answer 2

ISO C++ standard définit la complexité des algorithmes et des méthodes d'accès aux conteneurs, le cas échéant. Partout ailleurs (sinon explicitement) tous les paris sont désactivés et un implémenteur de bibliothèque est libre de faire sa propre implémentation. Par exemple, vous pouvez supposer que les cartes et les ensembles sont implémentés en utilisant des arbres rouge-noir, mais il n'y a aucune obligation de le faire. De nombreux algorithmes sont surchargés ou spécialisés pour des catégories d'itérateurs particulières (comme Random Access Iterator) et peuvent parfois même être optimisés pour fonctionner à partir d'un matériel spécial (comme le registre XMM et exécuter quelques opérations en parallèle).

Parfois vous devez vraiment assumer logiquement combien une opération peut coûter, en raison d'autres exigences, comme splice dans std :: list doit avoir O (1) complexité => longueur a O (n). J'ai le livre de N. Josuttis C++ Standard Library - Tutorial And Reference et tous ces aspects sont bien couverts là.

Cordialement,
Ovanes

Answer 3

Jetez un oeil à ce rapport sur STL, Boost et les performances du conteneur tableau

http://landenlabs.com/code/perf-stl/perf-stl.html