Quel est la mise en page de mémoire du vecteur de tableaux ?

Question

Est-ce que quelqu'un peut expliquer la disposition en mémoire de

std::vector> vec(2)

est-ce qu'il fournit un bloc de mémoire contigu d'un tableau 2D avec 2 lignes de 5 éléments?

À ma compréhension, le vecteur de vecteurs

std::vector> vec(2, std::vector(5))

fournissent la disposition en mémoire de deux tableaux contigus de longueur 5 éléments dans des emplacements différents en mémoire.

Est-ce que ce sera la même chose pour le vecteur d'arrays?

Answer 1

Les tableaux n'ont aucune indirecte, mais stockent simplement leurs données "directement". C'est-à-dire qu'un std::array contient littéralement cinq int à la suite, à plat. Et, comme les vecteurs, ils ne mettent pas de rembourrage entre leurs éléments, donc ils sont "internes contigus".

Cependant, l'objet std::array lui-même peut être plus grand que l'ensemble de ses éléments! Il est permis d'avoir des "choses" supplémentaires telles que du rembourrage. Donc, bien que probable, il n'est pas nécessairement vrai que vos données seront toutes contiguës dans le premier cas.

Un int
+----+
|    |
+----+

Un vecteur de 2 x int
+----+----+----+-----+        +----+----+
| ménage | ptr |        | 1  |  2 |
+----+----+----+-----+        +----+----+
                   |          ^
                   \-----------

Un std::array
+----+----+----+----+----+----------->
| 1  |  2 |  3 |  4 |  5 | des éléments supplémentaires/du rembourrage éventuel....
+----+----+----+----+----+----------->

Un vecteur de 2 x std::array
+----+----+----+-----+        +----+----+----+----+----+----------------------------+----+----+----+----+----+----------->
| ménage | ptr |        | 1  |  2 |  3 |  4 |  5 | des éléments supplémentaires/du rembourrage éventuel.... | 1  |  2 |  3 |  4 |  5 | des éléments supplémentaires/du rembourrage éventuel....
+----+----+----+-----+        +----+----+----+----+----+----------------------------+----+----+----+----+----+----------->
                   |          ^
                   \-----------

Et même si c'était le cas, en raison des règles d'aliasing, la possibilité d'utiliser un seul int* pour naviguer dans les 10 nombres serait potentiellement une question différente!

Tout bien réfléchi, un vecteur de dix int serait plus clair, complètement compact et potentiellement plus sûr à utiliser.

Dans le cas d'un vecteur de vecteurs, un vecteur est vraiment juste un pointeur plus quelques tâches ménagères, d'où l'indirection (comme vous le dites).

Answer 2

La grande différence entre std::vector et std::array est que std::vector contient un pointeur vers la mémoire qu'il enveloppe, tandis que std::array contient le tableau réel en lui-même.

Cela signifie qu'un vecteur de vecteurs est comme un tableau échelonné.

Pour un vecteur de tableaux, les objets std::array seront placés de manière contiguë mais séparée de l'objet vecteur. Notez que les objets std::array eux-mêmes peuvent être plus grands que le tableau qu'ils contiennent, et dans ce cas les données ne seront pas contiguës.

Le dernier point signifie également qu'un tableau (plain C-style ou std::array) de std::array peut également ne pas conserver les données de manière contiguë. Les objets std::array dans le tableau seront contigus, mais pas les données.

La seule manière de garantir des données contiguës pour un tableau "multi-dimensionnel" est d'utiliser des tableaux C-style imbriqués.

Answer 3

La norme C++ ne garantit pas que std::array ne contient pas de charge utile à la fin du tableau, donc malheureusement vous ne pouvez pas supposer que le premier élément d'un tableau subséquent se trouve juste après le dernier élément d'un tableau précédent.

Même si c'était le cas, le comportement en essayant d'accéder à n'importe quel élément dans un tableau par arithmétique de pointeur sur un pointeur d'un élément dans un autre tableau est indéfini. Cela est dû au fait que l'arithmétique de pointeur n'est valide qu'au sein des tableaux.

Ce qui précède s'applique également à un std::array.

Answer 4

static_assert(sizeof(std::array)==5*sizeof(int));

ce qui précède atténue tout ajout de rembourrage à la fin d'un std::array. Aucun compilateur majeur n'a à ce jour échoué à ce qui précède, et je parie qu'ils ne le feront pas à l'avenir.

Si et seulement si ce qui précède échoue, alors std::vector> v(2) aura un "écart" entre les std::arrays.

Cela ne aide pas autant que vous le voudriez; un pointeur généré comme suit :

int* ptr = &v[0][0];

n'a une validité que jusqu'à ptr+5, et le déréférencement de ptr+5 est un comportement indéfini.

Cela est dû aux règles d'aliasing; vous n'êtes pas autorisé à "marcher" au-delà de la fin d'un objet dans un autre, même si vous savez qu'il est là, à moins de faire d'abord un aller-retour vers certains types (comme char*) où des calculs de pointeurs moins restrictifs sont autorisés.

Cette règle existe pour permettre aux compilateurs de raisonner sur les données auxquelles on accède à travers quel pointeur, sans avoir à prouver que des calculs de pointeurs arbitraires vous permettront d'atteindre des objets extérieurs.

Donc:

struct bob {
  int x,y,z;
};

bob b {1,2,3};
int* py = &b.y;

peu importe ce que vous faites avec py en tant qu'int*, vous ne pouvez pas légalement modifier x ou z avec celui-ci.

*py = 77;
py[-1]=3;
std::cout << b.x;

le compilateur peut optimiser la ligne std::cout pour simplement afficher 1, car py[-1]=3 peut tenter de modifier b.x, mais le faire de cette manière est un comportement indéfini.

Le même type de restrictions vous empêche de passer du premier tableau de votre std::vector au second (c'est-à-dire au-delà de ptr+4).

Créer ptr+5 est autorisé, mais seulement en tant que pointeur d'un élément après la fin. Comparer ptr+5 == &v[1][0] n'est pas non plus spécifié dans le résultat, même si leurs valeurs binaires vont absolument être identiques dans tous les compilateurs sur tous les principaux systèmes matériels.

Si vous voulez aller plus loin dans le terrier du lapin, il n'est même pas possible de mettre en œuvre std::vector en C++ lui-même en raison de ces restrictions sur l'aliasing des pointeurs. La dernière fois que j'ai vérifié (avant c++17, mais je n'ai pas vu de résolution dans C++17) le comité standard travaillait à résoudre ce problème, mais je ne connais pas l'état de cet effort. (Ceci est moins un problème que vous pourriez le penser, car rien n'exige que std::vector soit implémenté en C++ conforme aux normes; il doit simplement avoir un comportement défini par les normes. Il peut utiliser des extensions spécifiques au compilateur en interne.)