En interne, comment se développe un vecteur de vecteurs? C++

Question

Disons que j'ai un programme comme celui-ci:

#include<vector> 

int main() 
{ 
    std::vector< std::vector <int> > vexample(2); 
    vexample[1].push_back(0); 
    vexample[0].push_back(0); 
} 

Sur la première ligne, j'initialiser un vecteur contenant 2 vecteurs de longueur nulle de ints. Sur la deuxième ligne, je pousse push_back() un int dans le second vecteur, provoquant le redimensionnement de vexample [1]. Qu'arrive-t-il à vexample, le vecteur des vecteurs, sur la ligne suivante lorsque le premier vexample [0] est redimensionné à cause de pushback()? Est-ce que vexample [2] est déplacé de 4 octets vers l'avant?

Answer 1

Je pense que vous avez un malentendu sur la façon dont les vecteurs fonctionnent en interne.

Un vecteur typiquement magasins seulement 3 choses en interne (qui est, sur la pile):

• sa taille
• sa capacité (qui est, la taille maximale jusqu'à laquelle il peut se développer sans redimensionnement)
• un pointeur vers le tableau sur le tas qui stocke les données réelles

(Souvent, pour des raisons de performance, les implémentations utilisent 3 pointeurs au lieu, mais sur le plan conceptuel, il est le même).

Cela signifie que la partie qui peut croître ou rétrécir est stockée sur le tas. Si vous push_back éléments en vexample[1] vous allez le faire grandir, et donc les valeurs de taille, capacité et le pointeur seront mis à jour au besoin, mais cela ne signifie pas qu'ils nécessitent plus d'espace sur la pile: c'est toujours 3 variables de taille, où "fixe" signifie qu'il est déterminé au moment de la compilation.

Si nous partons du principe que size et capacity sont mises en œuvre comme int et nécessitent 4 octets chacun, et un pointeur nécessite 8 octets, alors vous avez qu'un vecteur nécessite 4 + 4 + 8 = 16 octets sur la pile, quelle que soit la le type et le nombre des éléments qu'il contient, et capacity * sizeof(T) octets sur le tas. La quantité de mémoire utilisée sur le tas peut varier, contrairement à celle de la pile.

Dans votre cas, les éléments de vexample sont à nouveau des vecteurs, et donc chacun d'entre eux nécessite 16 octets, plus la taille de la capacité allouée. Ainsi, la disposition de la mémoire est comme ceci:

vexample prend 16 octets sur la pile. De ces 16 octets, 8 sont un pointeur vers une zone du tas où il y a un tableau de 2 éléments, dont chacun nécessite 16 octets, donc c'est un bloc contigu de 32 octets: les 16 premiers sont pour vexample[0], et les 16 derniers sont pour vexample[1]. Chacun d'eux contient un pointeur vers un tableau de int. Quand l'un de ces vecteurs croît, les données sur le tas peuvent devoir être réallouées, mais cela ne "repousse" rien d'autre, car s'il est vrai que les éléments des mêmes vecteurs doivent être stockés de manière contiguë, les zones de mémoire correspondant à différents vecteurs n'ont pas une telle exigence.Donc, quand vous push_back éléments en vexample[1] et le forcer à croître, ni vexample[0] ni vexample ni vexample[2] (s'il existe) besoin de faire quelque chose. En particulier, vexample[2] n'a pas besoin d'être déplacé, car vexample[1] se développe: au contraire, si vexample[1] se développe, alors vexample[1] doit trouver une nouvelle place pour lui-même. Tout cela serait un problème si la partie de taille variable d'un vecteur était sauvegardée dans la pile, où tout est stocké côte à côte. Mais c'est exactement la raison pour laquelle vous ne stockez qu'un pointeur sur le tas, et tout ce qui se passe en grandissant et en rétrécissant se produit là où il ne cause aucun dommage.

Answer 2

Chaque vecteur contient un pointeur sur la mémoire allouée sur le magasin libre pour contenir ses éléments. Donc rien ne se passe à vexample. Les données que vexample[0] peut résilier son pointeur, vexample[1] reste où il était jusqu'à ce que vous changez IT. Aucun des éléments vexample ne devient plus gros ou plus petit.