Vérification si un vecteur est vide

Question

Supposons que j'ai un std::vector appelé Vector

Après avoir effectué des opérations sur le vecteur (insertion ou suppression), je veux vérifier si le vecteur est vide et sur cette base, je veux effectuer certaines opérations.

Quelle approche est meilleure

Approche 1

if (Vector.size() == 0){ /* opérations */ }

Approche 2

if (Vector.empty()) { /* opérations */ }

Quelle est la meilleure approche, 1 ou 2?

Answer 1

v.size() == 0 dit "Je compare la taille", mais le fait pour vérifier si le conteneur est vide. Il y a un petit algorithme à digérer (très petit, car il ne consiste qu'en une comparaison) avant de savoir ce qu'il fait.
D'autre part, v.empty() fait exactement ce qu'il dit : il vérifie si v est vide.
Pour cette raison, je préfère clairement la seconde option, car elle fait ce qu'elle dit. C'est d'ailleurs pour cela que empty() a été inventé.

Mais il y a aussi une raison algorithmique de préférer empty() : Si quelqu'un change plus tard std::vector en std::list, v.size() pourrait avoir une complexité en O(n) (En C++ 03, c'est garanti d'être en O(1) pour std::vector, mais pas pour std::list. Selon le commentaire de James sur la réponse de Prasoon, ce sera en O(1) pour tous les conteneurs en C++1x.)

Answer 2

L'approche (2) serait meilleure car empty() s'exécute toujours en temps constant [c'est-à-dire O(1)] quelle que soit le type de conteneur.

size() s'exécute également en O(1) [pour std::vector] bien qu'il puisse s'exécuter en O(n) pour std::list [c'est défini par l'implémentation pour être honnête]

Dans Effective STL [Article 4] Scott Meyers dit

Vous devriez préférer la construction utilisant empty, et la raison est simple : empty est une opération en temps constant pour tous les conteneurs standard, mais pour certaines implémentations de listes, size prend du temps linéaire.

.....

Peu importe ce qui se passe, vous ne vous tromperez pas si vous appelez empty au lieu de vérifier si size() == 0. Appelez donc empty chaque fois que vous avez besoin de savoir si un conteneur a zéro élément.

Answer 3

Je dirais approche n° 2, car la méthode empty() a été intentionnellement conçue pour vérifier si un vecteur est vide. Vous pouvez également vérifier l'efficacité des deux approches, et décider ensuite laquelle est la meilleure.

Answer 4

Typiquement, un vecteur est implémenté en interne comme un pointeur vers un tableau alloué dynamiquement, avec des membres de données contenant la capacité et la taille du vecteur. La taille du vecteur est le nombre réel d'éléments, tandis que la capacité fait référence à la taille du tableau dynamique.

Avec cette implémentation, la fonction membre size() sera simplement un accesseur pour le membre taille.

La fonction empty() renverra le résultat de la comparaison taille == 0.

Donc, les deux sont également efficaces O(1) mais il est recommandé d'utiliser empty() si vous voulez vérifier si le vecteur est vide. Car c'est à cela que sert la fonction. Cela rendra votre code plus facile à lire.

Answer 5

En fait, vector.empty() et vector.size()==0 font la même chose. empty compare le début et la fin et renvoie true s'ils sont les mêmes, size calcule begin - end, retournant donc 0 s'il est vide, faisant ainsi la même chose en utilisant un autre calcul.