74
votes

C ou C ++ garantit-il le tableau

Supposons que vous ayez un tableau:

int *array = new(int[SIZE]);

ou

int array[SIZE];

CORD C ou C ++ garantit que array , et si oui, où?

Je comprends que quelle que soit la spécification du langage, de nombreux systèmes d'exploitation garantissent cette propriété en réservant le haut de l'espace d'adressage virtuel pour le noyau. Ma question est de savoir si cela est également garanti par la langue , plutôt que simplement par la grande majorité des implémentations.

À titre d'exemple, supposons qu'un noyau de système d'exploitation vit de basse mémoire et parfois Donne à la page la plus élevée de la mémoire virtuelle aux processus utilisateur en réponse aux demandes mmap de mémoire anonyme. Si malloc ou :: opératrice new [] appelle directement mmap pour l'allocation d'un tableau immense, et la fin du tableau abrite le haut de l'espace d'adressage virtuel tel que array + taille s'enroule à zéro, cela équivaut-il à une implémentation non conforme de la langue?

Clarification

Notez que la question est pas demander array + (size-1) , qui est l'adresse du dernier élément du tableau. Celui qui est garanti d'être supérieur à array . La question concerne un pointeur un au-delà de la fin d'un tableau , ou aussi p + 1 lorsque p est un pointeur vers un non-réseau objet (que la section de la norme indiquée par la réponse sélectionnée rend clairement est traitée de la même manière).

StackOverflow m'a demandé de clarifier pourquoi cette question n'est pas la même chose que celui-ci . L'autre question demande comment mettre en œuvre la commande totale des pointeurs. Cette autre question se résume essentiellement à la façon dont une bibliothèque pourrait implémenter std :: moins de telle sorte qu'elle fonctionne même pour les pointeurs à des objets alloués différemment, qui, selon la norme, ne peut être comparé que pour l'égalité, pas plus grande et moins que.

En revanche, ma question était de savoir si l'une des passes de la fin d'un tableau est toujours garantie d'être plus grande que le tableau. Que la réponse à ma question soit oui ou non ne change pas la façon dont vous implémenteriez std :: moins , donc l'autre question ne semble pas pertinente. S'il est illégal de comparer à un passé la fin d'un tableau, alors std :: moins pourrait simplement présenter un comportement non défini dans ce cas. (En outre, généralement la bibliothèque standard est implémentée par les mêmes personnes que le compilateur, et est donc libre de profiter des propriétés du compilateur particulier.)


17 commentaires

Qui a dit qu'un pointeur devait être une véritable adresse mémoire?


Afaik, un programme C pourrait être compilé pour un processeur hypothétique ayant seulement deux mots de mémoire, puis votre hypothèse est fausse


L'exemple est juste un exemple de la raison pour laquelle cela pourrait ne pas être le cas. La question sur l'arithmétique et la comparaison du pointeur représente évidemment des architectures encore plus étranges.


Est-ce que cela répond à votre question? Comment les pointeurs peuvent-ils être totalement commandés?


@ S.M. Il s'agit de commander des pointeurs vers différents objets. Cette question concerne juste des pointeurs dans le même tableau.


@ user3188445 de la non-autoritaire mais généralement fiable cppreference , dans C ++ "< I> Si un pointeur pointe vers un élément d'un tableau, ou vers un sous-objet de l'élément du tableau, et un autre pointeur pointe un au-delà du dernier élément du tableau, ce dernier pointeur compare plus ".


@Barmar Lisez attentivement la question dupliquée. Des pointeurs du même objet / tableau sont également mentionnés.


@dxiv Oui, ce lien est très utile. Il est également agréable de savoir que cela fonctionne même pour les non-terrains, donc pour tout pointeur vers un objet réel, p

.


Heureusement, c'est garanti, car sinon beaucoup de code serait brisé. Il est très courant de voir pour (int * p = array; p


@ user3188445: Tout objet peut être considéré comme un tableau de 1 élément, donc & obj <& obj + 1 .


Mais l'arithmétique du pointeur n'est garanti que dans std :: begin (arr), std :: end (arr) . Ainsi, arr n'est pas nécessaire (il est même UB).


@ Jarod42 La valeur du pointeur contient le numéro de page de mémoire virtuelle dans la table descripteurs (il a un long nom réel) donc et quelque chose + 1 peut incarner ce numéro à une page absente


@ Алек Ceйнеудачин & obj + 1 est un pointeur valide mais pas déréciviable.


@Caleth dépend de ce que vous voulez dire. Si le tableau des descripteurs de page n'a même pas de page avec ce numéro est-il valide ou non?


@ Алек Ceйнеудачин Je veux dire que la norme C ++ définit ce qui est et ce qui n'est pas un pointeur valide, et promet que vous pouvez comparer les pointeurs valides. Sur une telle plate-forme, l'implémentation devrait faire face à cette possibilité dans la définition de << / code>


@Caleth C'est une plate-forme Windows


@ Алек Ceйнеудачин La norme ne mentionne pas les adresses virtuelles, ou les pages ou les tables de descripteur. S'il dit que & obj <& obj + 1 doit être vrai, alors tout compilateur qui ne fait pas cela (pour une raison quelconque) est bogué. Et, en pratique, la comparaison << / code> ne doit pas lire les adresses comparées, donc le pointeur invalide n'a pas d'importance.


6 Réponses :


22
votes

c nécessite cela. Section 6.5.8 para 5 dit:

Les pointeurs vers des éléments de tableau avec des valeurs d'indice plus importantes se comparent plus que les pointeurs aux éléments du même tableau avec des valeurs d'indice inférieures

Je suis sûr qu'il y a quelque chose d'analogue dans la spécification C ++.

Cette exigence empêche efficacement les objets qui s'enroulent autour de l'espace d'adressage sur le matériel commun, car il ne serait pas pratique de mettre en œuvre toute la comptabilité nécessaire pour implémenter efficacement l'opérateur relationnel.


12 commentaires

Remarque que array + size ne pointe à aucun élément de array . Il indique l'élément juste après le dernier.


Je pense que les tableaux sont définis à leur taille + 1, mais je ne sais pas comment rechercher cela.


Je n'ai pas remarqué que la question concernait spécifiquement le pointeur juste après la fin du tableau, je pensais qu'il s'agissait d'un indice. @tstanisl


@Neil Vous êtes autorisé à former un pointeur juste après la fin, mais pas autorisé à le déréférence.


Ce comportement est apparemment documenté dans C90 Sec. 6.3.6, comme on l'a mentionné dans le c-faq , mais je pense que c'est 6.4. .6 en C99.


Vous aimez la bonne section de la spécification de langue, mais vous citez la mauvaise partie. La langue sur Q + 1 répond exactement à ma question.


@ user3188445 Je me rends compte que, voyez mon commentaire ci-dessus.


La «comptabilité nécessaire pour implémenter efficacement l'opérateur relationnel» est triviale: p q équivalent à p - Q <0, p - Q = 0 et p - Q> 0, où p −Q est calculé dans la largeur des bits d'espace d'adressage. Tant que chaque objet supporté est inférieur à la moitié de la taille de l'espace d'adressage, P - Q doit tomber dans la bonne région.


@EricPostPischil bon point. Je me souviens de la logique similaire utilisée dans la validation du numéro de séquence TCP. Cela dépend également de la taille maximale de la fenêtre étant inférieure à la moitié de l'espace de numéro de séquence.


À l'exception d'une cartographie définie par l'implémentation entre la machine abstraite C et le matériel physique, je ne me souviens rien dans la spécification qui nécessite des valeurs de pointeur qui ont une relation avec les adresses mémoire. Le fait qu'ils le font sur certaines machines est une question de commodité pour les implémentateurs système / compilateur. Les tableaux sont une abstraction C qui peut être cartographiée de toute manière imaginable à tout stockage physique disponible. Considérez comment un compilateur pourrait utiliser un cube holographique pour le stockage? p ++ ne se traduira probablement pas par un calcul linéaire.


@jwdonahue rien l'exige, sauf l'efficacité de l'implémentation sur le matériel traditionnel.


@jwdonahue Je connais bien les implémentations non traditionnelles, j'ai utilisé C sur les machines LISP.



80
votes

Oui. De la section 6.5.8 para 5 .

Si l'expression P pointe vers un élément d'un objet de tableau Et l'expression Q pointe vers le dernier élément du même tableau objet, l'expression du pointeur Q + 1 se compare à P.

Expression array est P. L'expression array + size - 1 pointe vers le dernier élément de array , qui est Q. Ainsi:

array + size = array + size - 1 + 1 = q + 1> p = array


19 commentaires

Cela implique-t-il que vous ne pouvez pas créer une implémentation qui met un tableau en haut de l'espace d'adressage? Car (array = ((int *) 0xfffffffc)) + 1 peut être 0x00000000? (Espace d'adressage 32 bits, exemple INT de 4 octets)


@Wyck, je suppose que le compilateur permettant la création d'un tel objet ne sera pas conforme aux dernières normes C.


@Wyck, vous pourriez ne pas être en mesure de mettre quoi que ce soit en position supérieure de l'espace d'adressage, si je lis correctement cppreference.com: " Un pointeur vers un objet qui n'est pas un élément d'un tableau est traité comme s'il pointait vers un élément d'un tableau avec un élément "


@ilkkachu: les objets dont l'adresse n'est pas prise pourraient être placées en haut de l'espace d'adressage ou à n'importe quelle adresse physique correspondrait à la représentation d'un pointeur nul. Étant donné que la plupart des programmes non triviaux auront au moins deux objets dont l'adresse n'est pas prise, une exigence selon laquelle les objets dont l'adresse est prise doivent aller ailleurs ne réduit pas la quantité de stockage pratiquement utile.


@Wyck Si le compilateur ne peut garantir qu'aucun objet, il devrait s'assurer que le pointeur All-Erosos est supérieur à tous les autres pointeurs. Ceci est bien sûr possible, mais sur la plupart des architectures rendrait les comparaisons de pointeurs de mise en œuvre plus coûteuses, donc je doute que tout compilateur le fasse.


Je ne vois pas beaucoup de sens dans tout ça pour être juste. Le comité de certains gars accepte-t-il ce compilateur ou non, je m'en fiche


@Wyck - Cela n'interdit pas une telle implémentation, tant qu'il garantit que << / code> est cohérent avec elle .


@Wyck: vous semblez confondre les valeurs d'exécution des variables array , size , p et q avec des adresses de mémoire virtuelles réelles. Bien sûr, avoir des pointeurs contiennent des modèles de bits identiques aux adresses de mémoire virtuelle est une implémentation facile, mais elle n'est pas obligatoire. En tant qu'exemple concrète, un pointeur vers un mot (16 bits) à une adresse impair sur un MC68000 ne peut pas être directement déréférencé depuis non-yte déréférence une adresse impair sur cette architecture lance des exceptions .


@Erictowers Comment est-ce un contre-exemple? Une implémentation C conformée ne permettrait pas de créer des objets sur des adresses impaises. Nous appelons cela l'alignement .


La norme ne nécessite pas que la disposition de la mémoire physique soit d'abord => dernier, dernier => premier ou toute autre disposition concevable. Seulement que les mathématiques réalisées sur les pointeurs se comportent comme si la disposition était d'abord => dernier.


@Wyck, je ne pense pas que la norme dit quoi que ce soit sur l'espace d'adresse mémoire. Il définit seulement une machine abstraite qui se comporte comme si les pointeurs se comportent comme des adresses linéaires. Je suis assez certain que la standard laisse des détails de mémoire physique aux concepteurs de systèmes et aux implémenteurs du compilateur.


@ user253751: Aucune implémentation C conforme n'est requise pour appliquer l'alignement et une implémentation qui applique l'alignement rend l'écriture du pilote stupidement difficile.


@Erictowers: Une implémentation conforme est requise pour s'assurer qu'il alloue des objets avec un alignement qui sera compatible avec tous les moyens qu'il utilise pour y accéder. Si par ex. Une plate-forme matérielle a une instruction de chargement 32 bits qui fonctionne avec des adresses alignées arbitrairement et une instruction de chargeur de charge qui ne fonctionne qu'avec des adresses alignées 32 bits, une implémentation pourrait à son guise, soit s'assurer que les objets 32 bits sont alignés et utilisez les deux types d'instructions pour y accéder, ou utiliser uniquement l'ancien type d'instruction, mais placer ensuite des objets avec un alignement arbitraire.


C'est aussi pourquoi vous pouvez faire la boucle idiomatique c foreach: pour (int * a = arr; a <(& arr) [1]; ++ a) printf ("% d \ n", * a);


@Erictowers Ils sont autorisés pour appliquer l'alignement, non? Il n'y a donc rien qui empêche C d'être mis en œuvre sur une plate-forme qui applique l'alignement. Pas de problème. En fait, la grande majorité des architectures CPU appliquent l'alignement.


@Wyck - Vous confondez les tableaux et les pointeurs. Dans la spécification, un "tableau" est défini comme une séquence d'objets alloués quelque part en mémoire. La spécification citée ici indique efficacement que le tableau doit être alloué de telle sorte qu'il y a au moins un octet de plus entre la fin du tableau et la fin de l'espace d'adressage, ce qui signifie que & array [_countof (array)]> = & array [array [ 0] est garanti vrai. Même un nouvel objet ed pointe effectivement l'une de ces structures fondamentales et donc, si vous faites foo = new foo [foo_count]; , alors & foo [foo_count]> = & foo [0] ou foo + foo_count> = foo sont garantis vrai.


@tstanisl je pense, en supposant que vous êtes d'accord, que l'ajout de quelque chose dans le sens de ce que je viens de dire dans mon commentaire ci-dessus pourrait aider à expliquer ce que la spécification dit réellement et essayer d'appliquer, mais en termes plus concrètes qui pourraient aider les lecteurs à le comprendre meilleur. Je modifierais votre réponse moi-même, mais je suis hors de la boucle sur la spécification actuelle et je ne veux pas dire quelque chose que je ne suis pas sûr à 100% que j'ai raison.


@Aikendrum, à ma compréhension de C Spec, il n'y a aucune exigence sur un octet supplémentaire après un tableau. Tout ce qu'il dit, c'est que l'implémentation doit garantir que "FOO + foo_count> compter" si foo a été créé de manière standard (arraycc, nouveau, malloc (), etc.). Les détails comment il est appliqué est une entreprise de compilateur. L'allocateur peut sélectionner & foo de telle manière que (uintptr_t) & foo + foo_count> (uintptr_t) & foo mais il existe d'autres moyens. L'OP a demandé uniquement à pointer le libellé dans la spécification C. IMO, la réponse aborde cela.


@tstanisl - L'OP n'a pas demandé "seulement de pointer le libellé de la spécification C". Votre réponse est extrêmement laconique et fait très peu pour aider toutes les personnes au-delà de l'OP qui finiront par se cacher et chercher des réponses à cette question, car lorsque les gens viennent s'empiler et poser une question en double, il est fermé et redirigé vers la question existante. Peu importe, je vais faire le montage moi-même si vous ne pouvez pas être dérangé.



-8
votes

Le tableau est garanti d'avoir un espace mémoire consécutif à l'intérieur. Après C ++ 03, les vecteurs sont garantis d'en avoir un aussi pour son & vec [0] ... & vec [ve.size () - 1] . Cela signifie automatiquement que ce que vous demandez est vrai
C'est ce qu'on appelle le stockage contigu. peut être trouvé ici pour les vecteurs
http: //www.open-stdd. org / jtc1 / sc22 / wg21 / docs / papiers / 2018 / p0944r0.html

Les éléments d'un vecteur sont stockés de manière contiguë, ce qui signifie que si V est un vecteur où t est un type autre que bool, alors il obéit à l'identité et v [n] == & v [0] + n pour tous les 0 <= n

ce dernier provient des documents standard. C ++ 03 J'ai deviné à droite.


11 commentaires

Je pense que vous avez confondu * et & .


Où la spécification fait-elle cette garantie sur les tableaux? Que signifie «l'espace mémoire consécutif», exactement? (Cela semble difficile à définir, étant donné que la spécification ne dit même pas que les pointeurs sont des "nombres" dans un sens significatif.) Pourquoi "l'espace mémoire consécutif" implique-t-il "le pointeur ne déborde pas"?


@Danielwagner Il s'appelle le stockage contigu


Pourquoi le pointeur "continu" implique-t-il "ne déborde pas"?


Ma question concernait vec [size ()] pas vec [size () - 1] .


@ user3188445 Très bien. donc ce n'est pas garanti


@ Алек Ceйнеудачин Je viens de clarifier ma question pour préciser qu'il s'agissait de vec [size ()] .


Si vous cherchez une preuve que les tableaux sont contigus, c'est dans [dcl .Array] / 6 . Mais comme l'a noté Daniel Wagner, cela seul ne prouve pas strictement que array .


Non, c'est garanti. Voir la section 6.5.8 Para 5 de la spécification C LSNGUAGE, comme lié dans la réponse sélectionnée.


@ user3188445 La valeur du pointeur est vraiment uint (32/64/16 en dos), donc il enroulera si vous ajoutez quelque chose à la valeur qui est déjà sur une bordure. Mais je pense que vous vous retrouverez avec une exception «hors limites» à la place.


Mais que se passe-t-il si q + 1 est uint_max + 1? Et ce n'est pas le seul cas voir mes commentaires



8
votes

Ceci est défini en C ++, à partir de 7.6.6.4 (p139 du courant C ++ 23 Draft ):

Lorsqu'une expression j qui a un type intégral est ajoutée ou soustraite d'une expression p du type de pointeur, le résultat a le type de p.

(4.1) - Si P évalue une valeur de pointeur nulle et J évalue à 0, le résultat est une valeur de pointeur nulle.

(4.2) - Sinon, si P pointe vers un élément de tableau I d'un objet de tableau X avec n éléments (9.3.4.5) Les expressions p + j et j + p (où j a la valeur j) pointer vers le point à la (peut-être hypothétique) Élément de tableau I + j de x si 0 <= i + j <= n et l'expression p - j pointe vers l'élément de tableau (peut-être hypothétique) i - j de x si 0 <= i - j <= n.

(4.3) - Sinon, le comportement n'est pas défini.

Notez que 4.2 a explicitement "<= n", pas "

La commande des éléments du tableau est définie dans 7.6.9 (p141):

(4.1) Si deux pointeurs pointent vers différents éléments du même tableau, ou en sous-objets de ceux-ci, le pointeur vers l'élément avec l'indice supérieur est nécessaire pour comparer plus.

ce qui signifie que l'élément hypothétique N comparera plus grand que le tableau lui-même (élément 0) pour tous les cas bien définis de n> 0.


4 commentaires

Cela dit que vous pouvez créer un tel pointeur, il ne dit pas comment la comparaison se comporte avec elle.


Tu as raison. J'ai supposé que le PO était convaincu que les membres de l'arborescence étaient fortement ordonnés. Réponse mise à jour pour couvrir cela.


Votre ajout ne couvre toujours pas cela. P + N pointe vers un "élément de tableau hypothétique". Signification hypothétique (dans ce cas) "n'existe pas". P + N ne pointe pas vraiment vers un élément de tableau. Ainsi, 4.1 ne peut pas s'appliquer, car P + N ne pointe pas vers un "élément du ... Array".


Comme indiqué dans la réponse de Richard Smith ci-dessous, cela est couvert dans [Basic.Chompound] comme valide, et 4.1 s'applique explicitement.



13
votes

La garantie ne tient pas pour le cas int * array = new (int [size]); lorsque taille est nul.

Le résultat de new int [0] doit être un pointeur valide qui peut avoir 0 ajouté à lui, mais array == array + taille dans ce cas, et un test strictement moins que ce qui donnera false .


2 commentaires

Tu m'as eu, j'aurais dû spécifier que je supposais size> 0 ...


@ user3188445 @ m.m - Vraiment, le résultat ici est que la question devrait être de savoir s'il est garanti ou non que array <= array + size .



5
votes

La règle pertinente en C ++ est [expr.rel] /4.1 :

Si deux pointeurs pointent vers différents éléments du même tableau, ou en sous-objets de ceux-ci, le pointeur vers l'élément avec l'indice supérieur est nécessaire pour comparer plus.

La règle ci-dessus semble ne couvrir que les pointeurs sur les éléments du tableau, et array + size ne pointe pas vers un élément de tableau. Cependant, comme mentionné dans la note de bas de page , un seul pas -L'un pointeur est traité comme s'il s'agissait d'un élément de tableau ici. La règle de la langue pertinente se trouve dans [base.compound] / 3 :

Aux fins de l'arithmétique du pointeur ([expr.add]) et de la comparaison ([expr.rel], [expr.eq]), un pointeur après la fin du dernier élément d'un tableau x de n Les éléments sont considérés comme équivalents à un pointeur vers un élément de tableau hypothétique n de x et un objet de type t qui n'est pas un élément de tableau est considéré comme appartenant à un tableau avec un élément de type t .

Ainsi, C ++ garantit que array + taille> array (au moins lorsque size> 0 ), et que & x + 1> & x pour tout objet x .


0 commentaires