comment est push_back mis en œuvre dans le vecteur STL?

J'ai été demandé à cette question dans une interview.

Les points que j'ai répondu sont comme ça

1) un index indiquant la position actuelle;

2) redimensionner si nécessaire.

Quelqu'un peut-il donner plus de détails?

La question était de savoir spécifiques de mise en œuvre? Toutes les implémentations sont autorisés à être différent.
La réponse est "c'est de la mise en œuvre définies". Sérieusement, stupides questions de l'entrevue devrait être sanctionnée par un grand nombre de coups sur la tête par un cluebat...
Je pense que c'est les programmeurs qui ne peut pas écrire un vecteur doit être puni. Nous avons tous les deux un point (et une chauve-souris).
pourquoi les entreprises devraient-elles être puni pour montrer la façon dont beaucoup qu'ils font ou ne savent pas à propos de C++ et de la STL? Semble que l'information est bon d'avoir.
Semble que l'employeur avait une chance de s'échapper.

OriginalL'auteur skydoor | 2010-04-12

c++vector

20

STL vector a un taille (le nombre d'éléments stockés) et un capacité (actuellement à l'espace de stockage alloué).
- Si size < capacity, un push_back met tout simplement le nouvel élément à la fin et incrémente le size par 1.
- Si size == capacity avant la push_back, un nouveau, plus grand tableau est alloué (deux fois la taille est commun, mais c'est dépendant de l'implémentation autant que je sache), toutes les données sont copiées (y compris le nouvel élément), et l'ancien espace alloué est libéré. Ce peut lancer une exception si l'allocation échoue.
La complexité de l'opération est amorti O(1), ce qui signifie que lors d'une push_back qui provoque un redimensionner, ce ne sera pas une constante de temps de l'opération (mais en général, au cours de nombreuses opérations, il est).

Je tiens aussi à faire remarquer que le coût amorti O(1) c'est le cas si la nouvelle capacité est k fois plus grand que l'ancien. Il est également à noter que, pour une k, chaque élément est copié 1/(k-1) fois en moyenne (pour k=2 c'est juste une copie supplémentaire).
+1 pour l'amortissement de la perspicacité.
Aussi, 2 n'est pas le facteur le plus commun. La plupart des implémentations ont changé le nombre d'or parce qu'il joue plus agréable avec de la mémoire... ce sujet a été discuté ici et une SORTE de comp.lang.c++.animé thread a été référencée.
Ah, ne le savais pas. Merci pour l'info; pouvez-vous fournir des liens vers les discussions que vous mentionnez?

OriginalL'auteur tzaman
4
```
template< typename T >
void std::vector<T>::push_back(const T& obj)
{
    this->insert(this->end(),obj);
}
```
Tu veux dire void std::vector<T>::push_back ?
Merci. Je savais que j'allais gâcher...
Parfaite réponse à une mauvaise question. Techniquement correcte, sans répondre à ce qu'ils signifie pour demander.
Peut-être que je suis dense, mais je ne suis pas sûr de ce que d'autre n'était prévu. Je pense que demandé: "Comment est push_back mis en œuvre dans std::vector?" J'aurais donné cette réponse dans l'interview.
Je suppose qu'ils sont à la recherche d'une réponse impliquant la gestion de la mémoire (comme tzaman de réponse).

OriginalL'auteur sbi
3

Que, bien sûr, est naturellement de mise en œuvre définies. En supposant que c'est une question de savoir comment quelqu'un peut mettre en œuvre un tableau dynamique, en général, ce serait quelque chose comme ceci:
1. push_back vérifie capacity() et s'assure qu'elle est au moins l'un plus grand que size().
2. Si il n'y a pas de capacité de l'élément nouveau, le vecteur de réallouer c'est l'ensemble sous-jacent de stockage, de reproduction sur le contenu de l'ancien stockage pour le stockage. L'ancien stockage est libéré.
3. Le nouvel élément est copié à la fin du tableau dynamique.
Certains STL implémentations d'éluder une partie des copies en utilisant des swaps (c'est à dire pour les conteneurs des conteneurs), mais pour la plupart, c'est exactement la façon dont il fonctionne.

OriginalL'auteur Billy ONeal
1

Éventuellement ce qu'ils cherchaient, c'est que push_back fait une copie de l'objet qui est poussé sur la vector (à l'aide de son constructeur de copie).

À l'égard de redimensionnement: que dit La norme a.push_back(x) est équivalent à a.insert(a.end(),x). La définition de insert dit, en partie: “les Causes de réaffectation si la nouvelle taille est plus grande que l'ancienne.”

Que dit la norme ce les fonctions sont censés faire. Mais la façon dont ils sont mis en œuvre est, dans la plupart des cas, la mise en œuvre spécifique.

OriginalL'auteur Nate
0

vector ne pas utiliser une liste chaînée. Il utilise de la mémoire continue.

Si il n'y a pas assez d'espace réservé push_back alloue un nouveau bloc de mémoire deux fois aussi grand que l'original vector. Ce faisant, l'amorti d'exécution est O(1).

...un nouveau morceau plus grand que l'ancien par certains facteur constant de toute façon -, mais le facteur est généralement autour de 1,5 au lieu de 2.
étrange. Pour un facteur de 1,5 à deux exemplaires pour chaque éléments est en moyenne sont nécessaires, alors que pour le facteur 2, c'est juste 1 copie.
Andrew Koenig a écrit un article il y a des années sur une raison de favoriser un plus petit facteur. Avec un facteur de deux, la somme des morceaux que vous avez jetés sera toujours plus petite que votre prochaine grande répartition, de sorte que vous n'arrivez pas à les réutiliser pour le même conteneur. Aussi longtemps que le facteur est <=le nombre d'or, ils vont éventuellement ajouter jusqu'à un assez grand morceau afin de les réutiliser pour les prochaines part plus importante des ressources.
c'est le cas seulement si le sous-jacent gestionnaire de mémoire alloue les morceaux thriftily. Toutefois, le gestionnaire peut s'en tenir à 2^n morceaux qui rend le 1.5-schéma inutile.

OriginalL'auteur Axel Gneiting
0

Grâce à certains commentaires, je suis tout à fait de la révision d'un très incorrecte réponse originale à cette question.

Selon la STL spec, votre réponse est correcte. Le vecteur est mis en œuvre comme un redimensionné dynamiquement tableau:

Vecteur des conteneurs sont mis en œuvre comme des tableaux dynamiques; en tant que matrices, vecteurs, les conteneurs sont leurs éléments stockés dans contiguë emplacements de stockage, ce qui signifie que leurs éléments peuvent être accessibles en utilisant non seulement les itérateurs, mais aussi en utilisant des décalages régulier sur les pointeurs vers des éléments.

Mais contrairement à des matrices de stockage dans des vecteurs est gérée automatiquement, permettant d'être étendue et rétractée tant que de besoin.

Pas de. Absolument pas. Un vecteur est un tableau dynamique -- la norme exige que le stockage sous-jacent être exactement le même qu'un builtin tableau. La norme exige seulement O(1) amortis de temps. Par conséquent, il suffit de O(1) dans le cas moyen.
Le sous-jacentes de la mémoire tampon d'un vecteur doivent être contiguës, ce qui signifie qu'il ne peut pas être une liste liée. Le push_back() la méthode peut toujours s'exécuter en temps constant (en moyenne) si le redimensionnement ne se produit pas lors de chaque appel. Cela nécessite généralement que le tampon de l'augmentation de la taille par un facteur (par exemple, le double de taille chaque fois que le vecteur est plein).

OriginalL'auteur
0

Comment beaucoup de détails ne l'interviewer voulez? Par exemple, il était à la recherche pour vous de percer vers le bas le niveau de détails?

En plus de l'habituel redimensionner-comme-nécessaire de conserver le O(1) sur la moyenne de la sémantique, certaines choses à considérer incluent, mais ne sont pas limités à:
- Exception de sécurité: la mise en oeuvre de fournir une garantie de l'état du vecteur ne sera pas modifié si une exception est levée lors de l'ajout de l'élément nouveau (par exemple, la sémantique de restauration)? Par exemple, une exception peut être levée lors de l'affectation, de la copie, de l'insertion, etc.
- La bonne utilisation de l'allocation: la mise en oeuvre d'utiliser correctement le vector's allocateur de la place de la plaine de vieux new en fonction de l'allocateur (les deux peuvent ou peuvent ne pas être les mêmes)? Idéalement, cela sera géré de manière transparente par le vector'redimensionnement de code, de mise en œuvre pourrait certainement être différente, cependant.
OriginalL'auteur Void
0

Comme suit:
```
void push_back(T const& param)
{
  vector temp(rbegin(), rend());
  temp.push_front(param);
  *this = vector(temp.rbegin(), temp.rend());
}
```
Cela semble être relativement coûteuse mise en œuvre. Vous d'abord copier le contenu du vecteur dans le sens inverse, ce qui nécessite l'allocation + O(n) itération à l'exemplaire de chaque élément du vecteur. Puis vous appuyez sur le paramètre à partir de de la temporaire de vecteur, qui nécessite encore une autre affectation et de O(n) élément accompagnant les opérations de copie. Ensuite, vous créez une copie de la temporaire (allocation + O(n) inverser l'itération/élément exemplaires) dont la copie est attribué au vecteur d'être opéré. Cette mission aura pour résultat la libération + O(n) opérations de destruction. Un peu lent. 🙂

OriginalL'auteur Crazy Eddie
0

Si la taille des < capasity, alors que tout semble être ok, vous venez d'insérer fr élément dans le vecteur, la complexité accures lorsque la taille de l' == capasity.

Il est facile de explaint sur les mots que vous devez allouer un nouveau tableau deux fois plus grand que celui existant et copie de tous ces éléments dans de nouveaux alocated de mémoire et après supprimer l'ancien et insérer le nouvel élément dans le tableau. Mais voici quelques moments clés que je considère votre interlocuteur attend de vous que vous mentionnez.
1. Les éléments de std::vector ne sont pas conservées dans un tableau, de sorte que le membre de données de std::vector[1000] n'est pas un int* de longueur 1000. Les éléments sont conservés dans des blocs de mémoire, donc vous devez prendre en compte lors de la copie.
2. Deuxièmement, la norme de vecteur stl exige "donnez-moi un copiable objet et je peux insérer", ce qui signifie que requierment sur std::vector est que sometype seul a avoir un copy_constructer (pas l'opérateur = ). Ainsi, lorsque vous êtes alocating une nouvelle mémoire de type sometype, vous devez prendre en compte que sometyme ne peut pas avoir un constructeur de copie par défaut. En commun des implémentations, ce qui est fait par le placement nouvel opérateur pour éviter l'appel de la copie des constructeurs.
Vieille question, mais soit je missunderstand 1) ou c'est simplement faux. std::vector garantit que tous ses éléments sont stockés de manière consécutive dans la mémoire (aka dans un seul tableau).

OriginalL'auteur Eduard Rostomyan

Vous devez vous connecter pour publier un commentaire.