11
votes

Soustraction du pointeur et une alternative

Lorsque vous travaillez avec des tableaux, des algorithmes standards (dans les deux C et C ++) renvoient souvent des pointeurs vers des éléments. Il est parfois pratique d'avoir l'indice de l'élément, peut-être à l'index dans un autre tableau, et je reçois normalement qu'en soustrayant le début du tableau du pointeur:

int arr[100];
int *addressICareAbout = f(arr, 100);
size_t index = addressICareAbout - arr;

c pointers c++

9 commentaires

Oui std :: Distance Fait exactement ce que vous décrivez. Par exemple, votre pointeur arithmétique pointeur ne fonctionne que avec contigus contenus, il échouerait pour std :: Liste . D'autre part, std :: Distance gère des conteneurs contigus et non contigus, tant qu'ils sont commandés.


                                        
                                                                            Votre message est intéressant mais je ne peux pas voir une question. Demandez-vous: «Quel type dois-je utiliser pour stocker des compensations du pointeur?". Si tel est le cas, la réponse est un  ptrdiff_t .

                                        
                                                                            J'ai 1.5 questions: 1.0) en C ++, peut  std :: Distance  être utilisé "en toute sécurité" pour les conteneurs ou dois-je vous inquiéter que la distance peut déborder  différence_type ? 0.5) La situation est-elle en C (travaillant avec des pointeurs)  vraiment  aussi mauvais qu'il semble?

                                        
                                                                            de  en.cpprefreence.com/w/cpp/types/ptrdiff_t   Si un tableau est si grand (plus grand que PTRDIFF_max éléments, mais moins que Taille_max octets), que la différence entre deux pointeurs peut ne pas être représentable comme STD :: PTRDIFF_T, le résultat de la soustraction de deux de ces pointeurs est  non défini .  Par conséquent, bonne question.

                                        
                                                                            J'ai vu cette référence aussi, et il semblait plausible (bien que j'ai vu un mauvais code de l'échantillon sur ce site avant). Un système permettrait-il que cela soit conforme? Ces systèmes existent-ils même? Existe-t-il une alternative "simple" à la soustraction du pointeur qui fonctionnera dans de tels cas?
                                        
                                                                            Je crois que si la prémisse est vraie, il est impossible pour le compilateur de le rendre conforme (par exemple sur un modèle d'adresse 16 bits, vous ne pouvez pas stocker la possible "gamme de points arithmétiques du pointeur" de -65535 .. + 65535 dans un 16 bits mots).
                                        
                                                                             STD :: Distance (Arr, AdressageAreaBout)  sera presque certainement juste être  Retour AdressageAreaBout - Art; 

                                        
                                                                            La question liée ne fournit-elle pas la solution de contournement? Insérer  PTRDIFF_MAX  Quelque part dans votre système d'allocation pour éviter que le débordement soit une option. Oui la  standard  ne rend pas la décision sur  ptrdiff_max  être utile pour cela, mais la mise en œuvre serait effectivement cassée si vous ne pouviez pas compter sur elle pour donner une valeur utile pour donner une valeur utile ici.

                                        
                                                                            Pourriez-vous ajouter ceci à votre source,  #if pTRDIFF_max  Juste pour voir s'il s'agit d'un problème avec le compilateur / cible spécifié?

3 Réponses : -2 votes J'ai trouvé aucune preuve à suggérer autrement. Heureusement, il existe des preuves ici: http://en.cppreference.com/w/ CPP / TYPES / TIZE_T std ::ze_t peut stocker la taille maximale d'un objet théoriquement possible de tout type (y compris la matrice). Un type dont la taille ne peut pas être représenté par std ::ze_t est mal formé (car c ++ 14) 8 commentaires True, taille_t doit être suffisamment grand pour stocker la taille de Art . Mais doit ptrdiff_t être assez grand pour stocker n'importe quel index? Pour clarifier, il semble que la soustraction soit déjà non définie si la différence déborde d'un ptrdiff_t , quel que soit le type de variable, je comme d'attribuer le résultat. Ah OK, il est concevable que dans un système de mémoire segmenté (ou paginé), vous pourriez avoir des différences d'adresses supérieures à la taille maximale d'un tableau. Le problème n'est pas "plus grand que la taille maximale d'un tableau". Le problème est que PTRDIFF_T doit gérer des nombres positifs et négatifs, et vous pourriez avoir un tableau avec une taille plus grande que le plus grand PTRDIFF_T (pas plus grand que la plus grande taille possible). Cela fonctionnerait toujours à cause du débordement arithmétique. par exemple. Dans un système de mémoire de 16 bits, 0xFFFF - 0x0000 donnerait un PTRDIFF de -1 (0xFFFF). Ajouter -1 à 0x0 donnerait une adresse 0xFFFF Comment cela répond-il à la question? (Astuce: Ça ne le fait pas) Les types signés débordants sont indéfinis lors de la coulée d'un type non signé sur un type signé qui ne peut pas contenir la valeur est définie sur la mise en œuvre. Je détesterais compter de l'un ou l'autre de ces. @LightnessRacksinorbit en toute justice, il n'y a aucune question à répondre. 6 votes Il est extrêmement improbable que vous auriez jamais deux pointeurs sur le même tableau où la différence ne s'intègre pas dans PTRIFF_T. sur les implémentations 64 bits, PTRDIFF_T est signée 64 bits. Vous auriez donc besoin d'un tableau de 8 milliards de gigaoctets. Sur les implémentations 32 bits, votre espace d'adressage total est généralement limité à 3 Go, 3 1/4 Go Si vous avez de la chance (c'est l'espace d'adressage, pas la RAM, qui compte), vous auriez donc besoin d'un tableau de plus de 2 Go. ne laisse pas beaucoup pour rien d'autre. Et il est tout à fait possible que MALLOC refuse d'allouer une matrice de cette taille en premier lieu. Votre jugement bien sûr. tandis que STD :: Distance présente des avantages, je soupçonne qu'il a le même problème théorique que PTRDIFF_T, car les distances peuvent être positives et négatives, et ce n'est probablement pas un type 64 bits sur une implémentation de 32 bits. Notez que si vous pouvez allouer un réseau de 3 Go sur une implémentation 32 bits et que vous avez deux INT * au premier et le dernier élément de ce tableau, je ne serais pas surpris si la différence de pointeur est calculée de manière incorrecte même Bien que le résultat s'adapte à PTRDIFF_T. 5 commentaires La différence serait -1GigaByte, que si elle est ajoutée à la première adresse céderait la seconde (due au débordement arithmétique). @Richardhodges: Un débordement signé n'a aucune garantie en C ++. La conversion antérieure sur Unsigné pourrait vous y arriver si vous êtes prudent. Je sais que les compilateurs 32 bits peuvent prendre en charge des entiers 64 bits (comme long long int ), donc dans ces implémentations, ptrdiff_t pourrait être défini comme long LONG LONG INT , et ce serait "juste travailler" (mais vous devez vous assurer d'utiliser pTRIFF_T et pas seulement int . "Vous auriez besoin d'un tableau de plus de 2 Go" ... Non, vous auriez besoin d'un tableau avec plus de 2 milliards d'éléments . Pour un tableau de INT sur un système 32 bits, cela signifie 8 Go, qui ne peut pas s'adapter à l'espace d'adressage. Le problème ne peut potentiellement se produire que pour tailleof (t) == 1 . GCC (et éventuellement d'autres) supposera que les objets n'occupent pas plus de la moitié de l'espace d'adresses de toute façon: GCC.GNU.ORG/ML/GCC/2011-08/MSG00221.HTML 0 votes Solution possible: lancer les deux pointeurs sur uintptr_t , soustraire et diviser par Tailleof (t) vous-même. Ce n'est pas précisément portable, mais il est garanti de ne jamais être un comportement indéfini, et la plupart des systèmes spécifient une conversion entier <-> de pointeur d'une manière qui fait ce travail. Solution de contournement vraiment portable (mais moins efficace): Utilisez un alternatif pointeur de base. Si la matrice est supérieure à 2 << 30 éléments, vous pouvez alors calculer légalement étape = p1 + (2 << 30) , utiliser des opérateurs relationnels pour voir si p2> étape , et si oui, calculez le décalage comme (2U << 30) + uintptr_t (distance (étape, p2)) Notez que l'appel récursif peut nécessiter une autre étape. . 5 commentaires Conversion de uintprt_t n'est pas portable. J'ai travaillé sur des systèmes (systèmes de vecteur de crayon) où cela ne fonctionnerait pas. Sur ces systèmes, des pointeurs d'octets sont implémentés sous forme de pointeurs de mots de 64 bits avec un décalage de 3 bits stocké dans les 3 bits à haut ordre; La conversion de pointeur-to-ineger fait juste copie les bits. Je soupçonne que vous êtes plus susceptible de rencontrer un système dans lequel la conversion de uintptr_t échouera d'une fois la soustraction de pointeur simplifiée. Et je ne sais pas ce que vous entendez par " garantie de ne jamais être un comportement défini par la mise en œuvre ". La standard garantit que vous pouvez convertir un vide * sur uintptr_t (ce qui pourrait même pas exister) et de retour à vide * et le résultat sera comparer égale au pointeur d'origine. Si vous effectuez des arithmétiques sur la valeur uintptr_t , la norme garantit rien. Le pointeur résultant est défini par la mise en oeuvre et peut être une représentation de piège, alors il suffit d'évaluer le pointeur a un comportement indéfini. @Keiththompson: Mais je ne jette pas à un pointeur, sans parler de la derréférance, il n'y a pas de comportement indéfini. Ah, vous avez raison, l'idée est de calculer un indice entier. Mais l'index peut avoir de sens, et en utilisant il doit indiquer dans la matrice pourrait avoir un comportement indéfini. @KeithThompson: Oui, mais vous pouvez vérifier de manière générale si cela a fonctionné. si (index

Articles qui pourrait vous intéresser : Que puis-je utiliser pour la conversion d'entrée au lieu de scanf? Comment puis-je calculer a * b / c lorsque a et b sont tous deux plus petits que c, mais que a * b déborde? Comment vérifier si un pointeur void (void *) est l'un des deux types de données? L'écran LCD affiche des caractères aléatoires (MPLAB)