On m'a posé cette question dans une interview.
Les points que j'ai répondu sont comme celui-ci
1) un indice pointant vers la position actuelle;
2) redimensionner si nécessaire.
Quelqu'un peut-il élaborer plus?
9 Réponses :
Grâce à certains commentaires, je révise complètement une réponse originale très incorrecte.
selon la spécification STL , votre réponse a été correcte. Le vecteur est implémenté comme une matrice redimensionnée dynamique:
Les conteneurs de vecteur sont implémentés comme des tableaux dynamiques; Tout comme des matrices régulières, les conteneurs de vecteur ont leurs éléments stockés dans des emplacements de stockage contigus, ce qui signifie que leurs éléments sont accessibles non seulement à l'aide d'itérateurs, mais également en utilisant des compensations sur des pointeurs réguliers vers des éléments.
de
Mais contrairement aux matrices régulières, le stockage dans les vecteurs est traité automatiquement, ce qui lui permet d'être étendu et contracté au besoin.
Non, absolument pas. Un vecteur est un tableau dynamique - la norme nécessite que le stockage sous-jacent soit exactement identique à celui d'une matrice intégrée. La norme nécessite uniquement O (1) amorti temps. Par conséquent, il n'a pas besoin que de O (1) dans le cas moyen.
Le tampon sous-jacent d'un vecteur doit être contigu, ce qui signifie qu'il ne peut pas être une liste liée. La méthode Push_back () peut toujours fonctionner en temps constant (en moyenne) si le redimensionnement ne se produit pas pendant chaque appel. Cela nécessite généralement que le tampon augmente de taille par un facteur (par exemple de taille double à chaque fois que le vecteur est plein).
éventuellement ce qu'ils cherchaient est que En ce qui concerne le redimensionnement: la norme indique La norme dit ce que les fonctions sont censées faire. Mais comment ils sont mis en œuvre sont, dans la plupart des cas, spécifiques à la mise en œuvre. push_back fait une copie de l'objet enfoncé sur le vecteur (code> (en utilisant son constructeur de copie).
a.push_back (x) est équivalent à a.insert (a.end (), x) . La définition de insérer dit, en partie: "Cause la réaffectation si la nouvelle taille est supérieure à l'ancienne capacité."
S'il n'y a pas assez d'espace réservé Vecteur n'utilise pas une liste liée. Il utilise la mémoire continue.
push_back attribue une nouvelle partie de mémoire deux fois aussi grande que l'original vecteur . En faisant que le temps d'exécution amorti est O (1).
... Un nouveau morceau qui est plus grand que l'ancienne par un facteur constant de toute façon - mais le facteur est typiquement d'environ 1,5 plutôt que 2.
@Jerry, étrange. Pour un facteur de 1,5 deux copies pour chaque élément en moyenne sont nécessaires, alors que pour le facteur de 2, il est juste 1 copie.
@Pavel: Andrew Koenig a écrit un article il y a des années environ une raison de favoriser un facteur moins important. Avec un facteur de deux, la somme des morceaux que vous avez jetés sera toujours plus petite que votre prochaine allocation plus importante. Vous ne devez donc jamais les réutiliser pour le même récipient. Tant que le facteur est <= la moyenne d'or, ils finiront éventuellement à ajouter un gros morceau pour réutiliser pour la prochaine allocation plus importante.
@COFFIN, c'est le cas que si le gestionnaire de mémoire sous-jacent alloue les morceaux plus tôt. Cependant, le gestionnaire peut coller à 2 ^ n morks qui rend le 1,5-schéma inutile.
Un vecteur a un Taille (nombre actuel d'éléments stockés) et un Capacité (espace de stockage actuellement attribué).
Taille , un Push_back Place simplement le nouvel élément à la fin et incrémente la taille par 1.
- si
taille == capacité avant le push_back , un nouveau tableau plus grand est attribué (deux fois la taille est courante, mais cela dépend de la mise en œuvre AFAIK), tout des données actuelles est copiée sur (y compris le nouvel élément), et l'ancien espace alloué est libéré. Cela peut lancer une exception si l'allocation échoue.
La complexité de l'opération est amortized O (1), ce qui signifie pendant un push_back qui provoque un redimensionnement, ce ne sera pas une opération de temps constant ( Mais en général sur de nombreuses opérations, c'est).
Je veux aussi commenter que le coût amorti O (1) est le cas si la nouvelle capacité est k fois plus gros que l'ancien. Il convient également de noter que, pour un k , chaque élément est copié 1 / (k-1) fois en moyenne (pour k = 2 C'est juste une copie supplémentaire).
De plus, 2 n'est pas le facteur le plus courant. La plupart des implémentations se sont déplacées vers le ratio doré car elle joue mieux avec la mémoire ... Cela avait été discuté ici et une comp.lang.c ++. Le fil modéré a été référencé.
Ah, je ne le savais pas. Merci pour l'info; Pouvez-vous fournir des liens avec les discussions que vous mentionnez?
Cela, bien sûr, est intrinsèquement défini. En supposant que c'est une question de savoir comment quelqu'un impliquerait une matrice dynamique, en général, ce serait quelque chose comme ceci:
push_back vérifie capacité () et garantit que c'est au moins une taille supérieure à () . .
- S'il n'y a pas de capacité pour le nouvel élément, le vecteur réaffiche qu'il est entièrement sous-jacent de stockage, copiant sur le contenu de l'ancien stockage vers le nouveau stockage. L'ancien stockage est distribué.
- Le nouvel élément est copié à la fin de la matrice dynamique.
Certaines implémentations stl éluent certaines des copies en utilisant des swaps (c'est-à-dire pour des conteneurs de conteneurs), mais pour la plupart, c'est exactement ce que cela fonctionne.
Combien de détails l'intervieweur a-t-il voulu? Par exemple, vous cherchais-t-il à vous échapper dans les détails de niveau inférieur?
Outre le redimensionnement habituel - comme si nécessaire pour conserver le O (1) sur la sémantique moyenne, certaines choses à prendre en compte incluent mais ne sont pas limitées à:
Nouveau Allocator (May ou peut ne pas être le même)? Idéalement, cela sera traité de manière transparente par le code de redimensionnement de vecteur , des implémentations pourrait certainement différer, cependant.
template< typename T >
void std::vector<T>::push_back(const T& obj)
{
this->insert(this->end(),obj);
}
Vous voulez dire void std :: vecteur
Réponse parfaite à une mauvaise question. Techniquement correct sans répondre à ce qu'ils signifiaient demander.
@Graphics: Peut-être que je suis dense, mais je ne suis pas sûr de quoi d'autre attendait. Je pense que "Comment est-ce que push_back implémenté dans std :: vecteur ?" J'aurais donné cette réponse dans l'entretien.
@sbi, je supposerais qu'ils recherchent une réponse impliquant une gestion de la mémoire (comme la réponse de Tzaman).
@Graphics: J'ai eu des entretiens comme ça. Ils ont posé une question et j'ai souligné l'erreur dediter. Ne pas wok sorti.
Ainsi, comme:
Cela semble être une mise en œuvre assez coûteuse. Vous copiez d'abord le contenu du vecteur en marche arrière, qui nécessite une allocation + O (n) itération de copier de chaque élément du vecteur. Ensuite, vous appuyez sur le paramètre sur le Début du vecteur temporaire, qui nécessite une autre allocation et O (n) des opérations de copie d'élément d'accompagnement. Ensuite, vous créez une autre copie des copies de l'itération / de l'issue inversée temporaire (N) d'allocation + O (N) qui est affectée au vecteur étant exploité. Cette affectation aboutira à des opérations de destruction des éléments de translocation + O (n). Un peu lent. :)
La plus grande mise en œuvre que je connaisse jusqu'à présent
Si Taille Il est facile d'expliquer les mots que vous devez attribuer un nouveau tableau deux fois plus grand, puis en existant et copiez tous ces éléments de la nouvelle mémoire aloutie et après avoir supprimé l'ancien et insérer le nouvel élément de la nouvelle matrice. Mais voici quelques moments clés que je considère que votre intervieweur s'attend à ce que vous mentionniez.
Les éléments de std :: Vecteur ne sont pas conservés dans un tableau, le membre de données de STD :: Vector [1000] n'est pas un INT * de la longueur 1000. Les éléments sont conservés dans des blocs de mémoire, Ainsi, vous devez le considérer lors de la copie.
Deuxièmement, le vecteur STL standard nécessite "Donnez-moi un objet copieux et je peux l'insérer", ce qui signifie que requis sur STD :: vecteur est que quelque party doit avoir une copie_constructeur (non opérateur =). Ainsi, lorsque vous aloutiez une nouvelle mémoire de type de type, vous devez considérer que SOITYME peut ne pas avoir de constructeur de copie par défaut. Dans les implémentations communes, cela se fait par le nouvel opérateur de placement pour éviter les constructeurs de copies.
La vieille question, mais je me méprise dans 1) ou c'est un problème clair. STD :: Vector garantit que tous ses éléments sont stockés consécutivement en mémoire (AKA dans un seul tableau).
La question était une question de mise en œuvre spécifique? Toutes les implémentations sont autorisées à être différentes.
La réponse est "c'est défini la mise en œuvre". Sérieusement, des questions d'entrevue stupides devraient être punies par une frappe sévère sur la tête par un cluebat ...
@DevSolar, je pense que c'est des programmeurs qui ne peuvent pas écrire de vecteur doivent être punis. Nous avons tous les deux un point (et une batte).
@DevSolar, pourquoi les entreprises devraient-elles être punies pour montrer à quel point ils font ou ne connaissent pas environ C ++ et STL? On dirait que cette information est bonne à avoir.
On dirait que l'employeur avait une chance chanceux.
À moins que vous vous soignez comme vous avez mis en œuvre une version de STL, il semble qu'il s'agit d'une question étrange. Aussi formulées, c'est une question de triviale. Je pourrais plutôt demander comment on pourrait la mettre en œuvre, compte tenu des exigences de la norme et de vous assurer que vous vous souviendrez de choses comme si votre taille dépasse la capacité. Mais il me semble étrange d'exiger et d'interview soumis à savoir comment les routines STL sont mises en œuvre.
@JOHNMCG La question n'était évidemment pas demandé telle que formulée, à moins que l'intervieweur n'était un cavernel. Je pense que la question (que Skydoor est généralement incapable de reproduire) était quelque chose comme - "Comment allez-vous continuer à implémenter la fonction Push_back d'un vecteur?" qui est tout à fait raisonnable.
@Neil: si votre jugement a raison ou mal, je ne pense pas que ce soit un lieu d'attaque personnelle.