J'étais en train de parcourir cette Référence C ++ et j'ai constaté que l'utilisation de vector :: size () renvoie la taille du vecteur en temps constant. Mais, je me demande comment on pourrait obtenir la taille sans réellement traverser le vecteur.
3 Réponses :
Il ne fait que suivre le nombre d'éléments.
Si cela change, ce numéro est mis à jour. Par exemple, le nombre d'éléments augmente de 1 lorsque push_back ou emplace_back est appelé. C'est l'une des nombreuses raisons pour lesquelles std :: vector n'est pas intrinsèquement thread-safe.
Comme vous pouvez l'imaginer, cela rend l'implémentation de std :: vector assez fastidieuse - la même chose peut être dite pour d'autres conteneurs de bibliothèques standard C ++ également - ce qui est une bonne raison pour ne pas essayer d'écrire classes de conteneurs vous-même.
Pourquoi avons-nous besoin de garder une autre variable pour le nombre d'éléments si nous pouvons obtenir directement le nombre d'éléments simplement en divisant la capacité du vecteur par la taille du premier élément?
Je n'ai pas dit cela - je suis un chat prudent vous savez!
La capacité et la taille de @HimanshuKumar sont des choses différentes pour std :: vector . Vous ne voulez pas augmenter la capacité à chaque fois que vous ajoutez un élément (car cela implique de réallouer le tableau interne et de copier / déplacer tous les éléments), donc vous augmentez la capacité de gros morceaux (généralement de façon exponentielle) même si vous n'êtes qu'un élément trop court.
@HimanshuKumar taille et capacité sont deux choses différentes, où taille <= capacité . La capacité est le nombre maximum d'éléments que la mémoire actuellement allouée peut contenir au total. La taille est le nombre d'éléments réels qui sont valides dans la mémoire actuellement allouée. La mémoire est réallouée lors des insertions lorsque la nouvelle taille dépasserait la capacité actuelle.
Pour comprendre cela, vous devez comprendre comment fonctionne le vecteur.
Un bon modèle mental est:
T& push_back(T const& t)
{
if (size == capacity)
grow();
constructAtEnd(t);
++ size;
return back();
}
Chaque fois qu'un élément est ajouté:
Lorsqu'il n'y a pas assez de capacité, nous devons augmenter les données. Bref, si vous regardez le code de push_back, il ressemblera à:
class vector
{
T *data;. // Pointer to the first element
size_t size; // Number of elements in use
size_t capacity; // Number of elements available
};
En pratique, c'est un peu plus complexe à cause des garanties d'exception. Cependant, compte tenu de ce qui précède, vous devriez être en mesure de vérifier votre implémentation de vector et de reconnaître ce qui se passe, pour toutes les méthodes.
"La plupart des implémentations" stockent données + taille et données + capacité au lieu de la taille et de la capacité (cela n'affecte cependant pas le modèle mental).
@MarcGlisse: Peut-être, mais notez que tous doivent utiliser std :: vector <> :: size_type comme type pour le nombre d'éléments. Ce n'était pas l'intention du répondant d'aller aussi loin; Je suis sûr. Ayez un vote positif!
@Marc MSVC ne le fait certainement pas. Libc ++ fait quelque chose de similaire basé sur 3 pointeurs
Les traits @Marc Type rendent en effet les choses plus complexes, j'ai tendance à les ignorer si vous n'utilisez pas d'allocateurs personnalisés
Personnellement, je laisserais tomber "(la plupart des implémentations l'implémentent même de cette façon)" - cela ruine la réponse.
Il devrait être if (size> = capacity) grow ();
@chtz Si size> capacité vous avez déjà foiré, alors size == capacity est le seul cas pertinent.
@MaxLanghof, oui == c'est bien aussi. Avant mon commentaire, il était dit size + 1> = capacité qui augmenterait prématurément.
@chtz Apologies, vérifiera l'historique des modifications la prochaine fois.
std :: vector est un conteneur de séquence dans la STL et il a une variable avec le nombre d'éléments à chaque fois. Lorsque nous push_back () n'importe quel élément du std :: vector cette variable s'incrémente et lorsque nous pop_back () élément du std :: vector cette variable décrémente.
Donc je pense que ça marche comme ça
Donc std :: vector :: size () renvoie la taille de cette variable
comment obtiendriez-vous la taille en parcourant le vecteur? vous devez connaître la taille pour savoir où arrêter de parcourir
Question potentiellement pertinente: C ++ sizeof Vector est 24? .
La taille est stockée dans une variable membre.
@Shawn Pas nécessairement.