C++ Girl
  1. C++ Girl
  3. Complexité temporelle de std :: vector :: erase
Intereting Posts
Problème de conversion de codage iconv Eclipse C ++: avoir des problèmes pour inclure un fichier avec l’extension ji Comment envoyer automatiquement des SMS via une clé USB à large bande? Comment obtenir la valeur et le type de l’exception actuelle en C ++ à l’aide de gdb? Modèle d’observateur C ++ 11 (signaux, créneaux horaires, événements, changement de diffuseur / auditeur, ou quoi que vous souhaitiez l’appeler) Que fait réellement la commande delete pour la mémoire, pour les pointeurs en C ++? Que se passe-t-il lorsque le constructeur d’une variable statique dans une fonction se termine de manière inhabituelle? Est-il possible de supprimer dispatch_once dans Objective-C ++? c ++ fileIO créer / ouvrir un fichier ne fonctionne pas std :: shared_ptr thread safety Quels compilateurs C ++ supportent déjà lambda? Comment ne spécialiser que certains membres d’une classe de modèle? C ++ compréhension des Unions et des Structures Pré-allouer de l’espace pour la queue C ++ STL Indicateurs de fonction de membre C ++

Complexité temporelle de std :: vector :: erase

J’ai trouvé un moyen de supprimer un élément d’un vecteur LIST de sa valeur ici : 

vec.erase(remove(vec.begin(), vec.end(), value), vec.end());

Maintenant, j’aimerais savoir à quel point cette méthode est efficace, c’est-à-dire sa complexité temporelle en notation Big O.

vec.erase (remove (vec.begin (), vec.end (), valeur), vec.end ());

Dans ce cas, remove compacte les éléments qui diffèrent de la valeur à supprimer (valeur) au début du vecteur et renvoie l’iterator au premier élément après cette plage. Puis effacer supprime les éléments.

Donc, cela rend cette opération O (n).

La norme C ++ 11 spécifie dans [vecteur.modificateurs] / 4:

Complexité : le destructeur de T est appelé le nombre de fois égal au nombre d’éléments effacés, mais l’opérateur d’affectation de mouvement de T s’appelle le nombre de fois égal au nombre d’éléments dans le vecteur après les éléments effacés.

En particulier, effacer des éléments à la fin est assez bon marché, car on ne détruit que les éléments à effacer; la complexité temporelle de l’appel à erase doit donc être linéaire en termes de nombre d’occurrences de value dans vec – ce qui correspond à Θ (n) dans Big-Oh-Notation. La complexité de l’expression entière est toujours linéaire puisque remove a une complexité linéaire en termes de longueur de la plage à laquelle elle est appliquée. Si la taille de vec est décrite par la variable m, nous avons Θ (n + m) pour l’expression complète qui est égale à O (m) (puisque n et m + n <2m , O (2m) = O (m) )

Cela pourrait être n’importe quoi car la complexité des destructures est inconnue

Mais en supposant que ce soit constant, alors ce sera O (n)

O (N) puisque vous parcourez chaque élément de votre vecteur.