Maison >développement back-end >C++ >Quelles sont les garanties de complexité standard pour les opérations sur différents types de conteneurs C ?
Quelles sont les garanties de complexité standard pour les opérations sur différents types de conteneurs C ?
- Patricia Arquetteoriginal
- 2024-12-26 00:00:18196parcourir
Garanties de complexité des conteneurs standard
Les conteneurs standard en C offrent une gamme de garanties de complexité qui régissent le comportement de leurs opérations. Le tableau suivant résume ces garanties pour différents types de conteneurs :
| Type de conteneur | Constructeur de copie | Remplir Constructeur | begin() | end() | rbegin() | rend() | front() | appuyer _front() | pop_front() | push_back() | pop_back() | insert() | insérer : remplir | insérer : plage | size() | swap() | effacer la clé | effacer l'élément | effacer range | count() | find() | plage égale | Limite inférieure/Limite supérieure | Égalité | InEgalité | Élément Accès | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Conteneur avant | O(n) | O(n) | O(1 ) | O(1) | O(1) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(ln( n)) | O(1) | O(ln(n) S) | O(log(n) k) | O(ln(n)) | O(ln(n)) | O(ln(n)) | O(n) | O(n) | O(1) | ||||||
| Inverse Conteneur | O(1) | O(1) | O(1) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(1) | O(n) | O(n) | O(1) | ||||||||||||||
| Conteneur à accès aléatoire | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(n) | O(n) | O(1) | |||||||||||||||||
| Séquence | O(1) | O(1) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(ln(n)) | O(ln(n) )S) | O(ln(n)) | O(ln(n)) | |||||||||||||||
| Insertion avant/arrière Séquence | O(1) | O(1) | O(1) | O(1) | O(1) | O(n) | O(1) | O(1) | O(1) | O(n) | O(n) | O(1) | |||||||||||||||
| Retour/ Séquence d'insertion avant | O(1) | O(1) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(1) | O(1) | |||||||||||||||||
| Conteneur associatif | O(1) | O(1) | O(kln(n) n) | O(1) | O(1) | O(1) | O(ln(n)) | O(ln(n)) | O(ln(n)) | O(n) | O(n) | ||||||||||||||||
| Conteneur associatif simple/trié/unique | O(1) | O(1 ) ) | O(ln(n)) | O (n) | O(1) | O(1) | O(1) | O(ln(n)) | O(n) | O(n) | |||||||||||||||||
| Paire/Trié/Unique Associatif Conteneur | O(1) | O(1) | O(1) | O(1) | O(1) | O(ln(n)) | O(n) | O(n) | |||||||||||||||||||
| Associatif Multiple/Trié/Unique Conteneur | O(1) | O(1) | O(1) | O(1) | O(1) | O(ln(n)) | O(n) | O(n) |
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
Déclaration：
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Article précédent：Comment puis-je terminer de force un seul thread dans C 11 sans coopération ?Article suivant：Comment puis-je terminer de force un seul thread dans C 11 sans coopération ?
Articles Liés
Voir plus- Erreur de compilation C++ : Un fichier d'en-tête est référencé plusieurs fois, comment le résoudre ?
- Erreur de compilation C++ : paramètres de fonction incorrects, comment y remédier ?
- Erreur C++ : Le constructeur doit être déclaré dans l'espace public, comment y faire face ?
- Gestion des processus et synchronisation des threads en C++
- Comment gérer les problèmes de fractionnement des données dans le développement C++