Garantiert C oder C++ Array < Array + SIZE?

Lesezeit: 7 Minuten

Benutzeravatar von user3188445
Benutzer3188445

Angenommen, Sie haben ein Array:

int array[SIZE];

oder

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

Garantiert C oder C++ das? array < array + SIZEund wenn ja wo?

Ich verstehe, dass viele Betriebssysteme unabhängig von der Sprachspezifikation diese Eigenschaft garantieren, indem sie den oberen Teil des virtuellen Adressraums für den Kernel reservieren. Meine Frage ist, ob dies auch gewährleistet ist durch die Spracheund nicht nur von der überwiegenden Mehrheit der Implementierungen.

Nehmen wir als Beispiel an, dass ein Betriebssystem-Kernel in wenig Speicher lebt und manchmal als Reaktion darauf die höchste Seite des virtuellen Speichers an Benutzerprozesse ausgibt mmap Anfragen nach anonymem Speicher. Wenn malloc oder ::operator new[] ruft direkt an mmap für die Zuordnung eines riesigen Arrays, und das Ende des Arrays grenzt an die Spitze des virtuellen Adressraums, so dass array + SIZE auf Null umläuft, läuft dies auf eine nicht konforme Implementierung der Sprache hinaus?

Klärung

Beachten Sie, dass die Frage ist nicht Fragen über array+(SIZE-1), die die Adresse des letzten Elements des Arrays ist. Dieser ist garantiert größer als array. Die Frage bezieht sich auf einen Zeiger eins nach dem Ende eines Arraysoder auch p+1 Wenn p ist ein Zeiger auf ein Nicht-Array-Objekt (was der Abschnitt des Standards, auf den die ausgewählte Antwort zeigt, auf die gleiche Weise behandelt).

Stackoverflow hat mich gebeten zu klären, warum diese Frage nicht dieselbe ist wie diese. Die andere Frage fragt, wie die vollständige Ordnung von Zeigern implementiert werden soll. Diese andere Frage läuft im Wesentlichen darauf hinaus, wie eine Bibliothek implementieren könnte std::less so dass es sogar für Zeiger auf unterschiedlich zugewiesene Objekte funktioniert, die laut Standard nur auf Gleichheit verglichen werden können, nicht größer und kleiner als.

Im Gegensatz dazu ging es bei meiner Frage darum, ob eins nach dem Ende eines Arrays immer größer als das Array ist. Ob die Antwort auf meine Frage Ja oder Nein lautet, ändert eigentlich nichts daran, wie Sie implementieren würden std::less, also scheint die andere Frage nicht relevant zu sein. Wenn es illegal ist, mit einem nach dem Ende eines Arrays zu vergleichen, dann std::less könnte in diesem Fall einfach ein undefiniertes Verhalten zeigen. (Außerdem wird die Standardbibliothek normalerweise von denselben Personen wie der Compiler implementiert und kann daher die Eigenschaften des jeweiligen Compilers frei nutzen.)

  • Wer hat gesagt, dass ein Zeiger eine tatsächliche Speicheradresse sein muss?

    – Verrückter Physiker

    2. März 2021 um 6:29 Uhr

  • @SM Hier geht es darum, Zeiger auf verschiedene Objekte zu ordnen. Bei dieser Frage geht es nur um Zeiger innerhalb desselben Arrays.

    – Barmar

    2. März 2021 um 6:40 Uhr

  • @ user3188445 Von den nicht maßgeblichen, aber im Allgemeinen zuverlässigen cpReferenzin C++ “Wenn ein Zeiger auf ein Element eines Arrays oder auf ein Unterobjekt des Elements des Arrays zeigt und ein anderer Zeiger um eins nach dem letzten Element des Arrays zeigt, ist der letztere Zeiger im Vergleich größer“.

    – dxiv

    2. März 2021 um 6:41 Uhr

  • Zum Glück ist es garantiert, denn sonst würde eine Menge Code da draußen kaputt gehen. Es ist sehr häufig zu sehen for (int *p = array; p < array + SIZE; p++) do_stuff(*p);

    – Nate Eldredge

    2. März 2021 um 6:44 Uhr

  • @АлексейНеудачин Der Standard erwähnt keine virtuellen Adressen, Seiten oder Deskriptortabellen. Wenn es das sagt &obj < &obj + 1 wahr sein muss, dann ist jeder Compiler, der das (aus irgendeinem Grund) nicht tut, fehlerhaft. Und in der Praxis < Der Vergleich sollte nicht von den verglichenen Adressen lesen, daher spielt es keine Rolle, ob der Zeiger ungültig ist.

    – HolyBlackCat

    2. März 2021 um 17:55 Uhr


Benutzeravatar von tstanisl
tstanisl

Ja. Aus Abschnitt 6.5.8 Abs. 5.

Wenn der Ausdruck P auf ein Element eines Array-Objekts und der Ausdruck Q auf das letzte Element desselben Array-Objekts zeigt, ist der Zeigerausdruck Q+1 größer als P.

Ausdruck array ist P. Der Ausdruck array + SIZE - 1 zeigt auf das letzte Element von arraywas Q ist. Also:

array + SIZE = array + SIZE - 1 + 1 = Q + 1 > P = array

  • Bedeutet dies, dass Sie keine Implementierung erstellen können, die ein Array an den Anfang des Adressraums setzt? Weil (array= ((int*)0xFFFFFFFC))+ 1 0x00000000 sein könnte? (32-Bit-Adressraum, 4-Byte-Int-Beispiel)

    – Wyck

    2. März 2021 um 15:32 Uhr

  • @Wyck, Sie können möglicherweise nichts an die oberste Position des Adressraums setzen, wenn ich cppreference.com richtig lese: “Ein Zeiger auf ein Objekt, das kein Element eines Arrays ist, wird behandelt, als würde er auf ein Element eines Arrays mit einem Element zeigen.”

    – Ilkkachu

    2. März 2021 um 16:06 Uhr

  • @ilkkachu: Objekte, deren Adresse nicht verwendet wird, könnten oben im Adressraum oder an einer beliebigen physischen Adresse platziert werden, die der Darstellung eines Nullzeigers entsprechen würde. Da die meisten nicht-trivialen Programme mindestens zwei Objekte haben, deren Adresse nicht genommen wird, verringert die Anforderung, dass alle Objekte, deren Adresse genommen wird, woanders hingehen müssen, nicht die Menge an praktisch nutzbarem Speicherplatz.

    – Superkatze

    2. März 2021 um 16:12 Uhr


  • @Wyck – es verbietet eine solche Implementierung nicht, solange es dafür sorgt < ist damit vereinbar.

    – Toby Speight

    2. März 2021 um 20:15 Uhr

  • @Wyck: Sie scheinen die Laufzeitwerte der Variablen zusammenzuführen array, SIZE, Pund Q mit tatsächlichen virtuellen Speicheradressen. Sicher, dass Zeiger Bitmuster enthalten, die mit virtuellen Speicheradressen identisch sind, ist eine einfache Implementierung, aber es ist nicht zwingend erforderlich. Als konkretes Beispiel kann ein Zeiger auf ein (16-Bit-)Wort an einer ungeraden Adresse auf einem MC68000 nicht direkt dereferenziert werden Nicht-Byte-Dereferenzierung einer ungeraden Adresse auf dieser Architektur löst Ausnahmen aus.

    – Eric Türme

    2. März 2021 um 22:54 Uhr

Benutzeravatar von Barmar
Barmar

C erfordert dies. Abschnitt 6.5.8 Abs. 5 sagt:

Zeiger auf Array-Elemente mit größeren tiefgestellten Werten sind größer als Zeiger auf Elemente desselben Arrays mit niedrigeren tiefgestellten Werten

Ich bin sicher, dass es etwas Analoges in der C++-Spezifikation gibt.

Diese Anforderung verhindert effektiv das Zuweisen von Objekten, die den Adressraum auf üblicher Hardware umschließen, da es unpraktisch wäre, die gesamte Buchführung zu implementieren, die zum effizienten Implementieren des relationalen Operators erforderlich ist.

  • Beachten Sie, dass array + SIZE zeigt nicht auf irgendein Element von array. Es zeigt auf das Element direkt nach dem letzten.

    – tstanisl

    2. März 2021 um 6:41 Uhr


  • Ich denke, Arrays sind auf ihre Größe + 1 definiert, aber ich bin mir nicht sicher, wie ich das nachschlagen soll.

    – Neil

    2. März 2021 um 6:43 Uhr

  • @Neil Du darfst einen Zeiger kurz nach dem Ende bilden, aber nicht dereferenzieren.

    – Barmar

    2. März 2021 um 6:45 Uhr

  • Die „Buchhaltung, die notwendig ist, um den Vergleichsoperator effizient zu implementieren“ ist trivial: p < q, p = q und p > q sind äquivalent zu p−q < 0, p−q = 0 und p−q > 0, wobei p −q wird in der Breite der Adressraumbits berechnet. Solange jedes unterstützte Objekt kleiner als die Hälfte des Adressraums ist, muss p−q in den richtigen Bereich fallen.

    – Eric Postpischil

    2. März 2021 um 11:58 Uhr


  • @jwdonahue Ich bin mit nicht-traditionellen Implementierungen gut vertraut, ich habe C auf Lisp-Maschinen verwendet.

    – Barmar

    3. März 2021 um 19:16 Uhr

Die Garantie gilt nicht für den Fall int *array = new(int[SIZE]); Wenn SIZE ist Null.

Das Ergebnis von new int[0] muss ein gültiger Zeiger sein, der haben kann 0 hinzugefügt, aber array == array + SIZE in diesem Fall und ein strikt kleiner als Test ergibt false.

  • Du hast mich erwischt, ich hätte angeben sollen, dass ich davon ausgegangen bin SIZE > 0

    – Benutzer3188445

    3. März 2021 um 2:51 Uhr

  • @ user3188445 @MM – Wirklich, das Ergebnis hier ist, dass die Frage lauten sollte, ob dies garantiert ist oder nicht array <= array + SIZE.

    – Aiken-Trommel

    9. März 2021 um 3:11 Uhr

Benutzeravatar von throx
Throx

Dies ist in C++ ab 7.6.6.4 (p139 von current C++23-Entwurf):

Wenn ein Ausdruck J vom ganzzahligen Typ zu einem Ausdruck P vom Zeigertyp addiert oder davon subtrahiert wird, hat das Ergebnis den Typ P.

(4.1) – Wenn P zu einem Nullzeigerwert und J zu 0 ausgewertet wird, ist das Ergebnis ein Nullzeigerwert.

(4.2) — Andernfalls, wenn P auf ein Array-Element i eines Array-Objekts x mit n Elementen (9.3.4.5) zeigt, zeigen die Ausdrücke P + J und J + P (wobei J den Wert j hat) auf das (möglicherweise hypothetisches) Array-Element i + j von x, wenn 0 <= i + j <= n, und der Ausdruck P - J zeigt auf das (möglicherweise hypothetische) Array-Element i − j von x, wenn 0 <= i − j <= n .

(4.3) — Andernfalls ist das Verhalten undefiniert.

Beachten Sie, dass 4.2 explizit “<= n" hat, nicht "< n". Sie ist für jeden Wert größer als size() undefiniert, ist aber für size() definiert.

Die Reihenfolge der Array-Elemente ist in 7.6.9 (p141) definiert:

(4.1) Wenn zwei Zeiger auf unterschiedliche Elemente desselben Arrays oder auf Unterobjekte davon zeigen, wird der Zeiger auf das Element mit dem höheren Index benötigt, um größer zu vergleichen.

Das bedeutet, dass das hypothetische Element n für alle wohldefinierten Fälle von n > 0 größer ist als das Array selbst (Element 0).

Die relevante Regel in C++ ist [expr.rel]/4.1:

Wenn zwei Zeiger auf unterschiedliche Elemente desselben Arrays oder auf Unterobjekte davon zeigen, wird der Zeiger auf das Element mit dem höheren Index benötigt, um größer zu vergleichen.

Die obige Regel scheint nur Zeiger auf Array-Elemente abzudecken, und array + SIZE zeigt nicht auf ein Array-Element. Allerdings, wie erwähnt in die Fußnote, wird ein Eins-nach-dem-Ende-Zeiger hier so behandelt, als wäre er ein Array-Element. Die entsprechende Sprachregelung ist in [basic.compound]/3:

Für Zwecke der Zeigerarithmetik ([expr.add]) und Vergleich ([expr.rel], [expr.eq]), ein Zeiger nach dem Ende des letzten Elements eines Arrays x von n elements wird als äquivalent zu einem Zeiger auf ein hypothetisches Array-Element betrachtet n von x und ein Objekt vom Typ T das kein Array-Element ist, wird als zu einem Array mit einem Element des Typs gehörend betrachtet T.

C++ garantiert das also array + SIZE > array (Zumindest wann SIZE > 0), und das &x + 1 > &x für irgendein Objekt x.

Das Array hat garantiert fortlaufenden Speicherplatz im Inneren. nach c++03 oder so hat vectors garantiert auch einen für sich &vec[0] ... &vec[vec.size() - 1]. Dies bedeutet automatisch, dass das, wonach Sie fragen, wahr ist
Dies wird als zusammenhängender Speicher bezeichnet. finden Sie hier für Vektoren
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0944r0.html

Die Elemente eines Vektors werden zusammenhängend gespeichert, was bedeutet, dass wenn v ein Vektor ist, wobei T ein anderer Typ als bool ist, dann gehorcht es der Identität &v[n] == &v[0] + n für alle 0 <= n < v.size(). Vermutlich fünf weitere Jahre des Studiums der Wechselwirkungen von Kontiguität und Caching machten der WG21 klar, dass Kontiguität vorgeschrieben und die nicht-kontinuierliche Vektorimplementierung eindeutig verboten werden sollte.

Letzteres stammt aus Standarddokumenten. C++03 Ich habe richtig geraten.

1417170cookie-checkGarantiert C oder C++ Array < Array + SIZE?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy