quel des deux est le plus rapide au hasard des insertions et des suppressions? Je suppose que la liste, ayant les valeurs les touches comme il est avec des décors semble être attrayant aussi bien.
La performance est similaire pour une itération sur l'ensemble du conteneur?
Merci!
Liste
Ensemble
std::hashsetfournit la sémantique, mais pas dans l'ordre de la traversée. Des récipients différents pour les différents modes d'utilisation.std::list est O(1) pour les insertions et les suppressions. Mais vous pouvez bien besoin de O(n) pour trouver l'insertion ou la suppression point. std::set est O(log(n)) pour les insertions et les suppressions, il est généralement mis en œuvre comme un rouge-noir arbre.
Considérons l'effort de trouver l'insérer/supprimer le point de faire votre choix.
D'abord penser à la sémantique, puis sur la performance.
Si vous avez un ensemble de nombres entiers, et vous insérez les nombres entiers 6, 8, 13, 8, 20, 6 et 50, vous vous retrouverez avec un ensemble contenant les cinq éléments suivants:
{ 6, 8, 13, 20, 50 }.Si vous le faites avec une liste, vous vous retrouverez avec une liste contenant les sept éléments suivants:
{ 6, 8, 13, 8, 20, 6, 50 }.Alors, que voulez-vous? Il n'est pas judicieux de comparer la vitesse de conteneurs avec de telles différences de sémantique.
Dans une std::list, de l'insertion et de la suppression de prendre lui-même un temps en O(1), ce qui signifie très rapide, et au-dessus de tous les moyens à une vitesse qui ne dépend pas du nombre d'éléments dans la liste.
Dans un std::set, l'insertion et la suppression de prendre de temps en O(log(N)), ce qui signifie un peu plus lent, si beaucoup d'éléments sont contenus dans l'ensemble. Le N dans l'expression de O(log(N)) désigne le nombre d'éléments. Grosso modo, cela signifie que le temps que l'opération est une sorte de proportionnelle au logarithme (la base n'a pas d'importance ici, car il est équivalent à multiplier par une constante, qui est ignorée par la théorique de l'algorithme d'analyse) le nombre d'éléments de l'ensemble.
Mais il est essentiel de prendre en compte le temps nécessaire pour trouver l'élément à supprimer. Si vous devez rechercher le conteneur de l'élément à supprimer, ce qui est probablement le cas, alors le std::list va prendre un temps assez long pour cette recherche, qui sera en O(N) (ce qui signifie pas rapide, parce que le temps est directement proportionnel au nombre d'éléments, ne pas le (logarithme du), tandis que le std::set va prendre un temps en O(log N) pour la recherche.
Également à noter que ces analyses théoriques deviennent absolument pas valide pour les conteneurs avec très peu d'éléments, auquel cas la multiplication des constantes ils se cachent devenu plus important que la fonction de temps de la famille, il se concentre sur.
Pour faire court:
std::list => plus Lent pour la recherche de l'élément à supprimer; plus rapide pour le supprimer.
std::set => plus Rapide pour la recherche de l'élément à supprimer; moins rapide pour le supprimer.
Mais pour l'ensemble de l'opération, et pour un grand nombre d'éléments, le std::set, c'est mieux.
Vous devriez également envisager l'utilisation de tables de hachage. Bonne implémentation de ceux-ci sont disponibles en Boost, Qt, ou C++0x. Elles font toutes ces opérations dans le temps tend vers O(1) (ce qui signifie très très vite).
Vous devez mesurer la performance réelle de l'utilisation des données réalistes. Vérifier à la fois typique et les pires performances.
Bien que std::vector a O(N) fois la complexité de l'insertion aléatoire, std::set O(log(N)) et std::list O(1), std::vector donne de meilleurs résultats dans de nombreux cas. Seulement si la performance n'est pas assez important pour passer du temps de mesure, de passer par le big-O de la complexité.
"Si vous n'êtes pas en mesure de vous n'êtes pas le génie" Rico (Mariani)
Si vous vous souciez de la vitesse, alors vous devriez probablement utiliser
std::vector.std::listeffectue une allocation de tas à chaque fois qu'un élément est inséré, et c'est souvent un goulot d'étranglement.Une exception est lorsque les éléments individuels sont très cher, de les copier, ou lorsque vous avez beaucoup d'entre eux. Dans ces cas, une liste est susceptible de faire mieux que il n'a pas à déplacer des éléments autour de quand elle est redimensionnée. Un
std::dequeest aussi une bonne option ici, mais vous aurez besoin pour votre application de profil afin de décider entre les deux.Enfin, l'utilisation
std::setseulement si vous avez besoin de garder vos objets triés (ou si vous ne voulez pas les éléments répétés). Sinon, il va être beaucoup plus lent que d'une liste ou un vecteur.vec.swap(vector<int>());