Gibt es in C ++ eine maximale Array-Längenbeschränkung?

Gibt es eine maximale Länge für ein Array in C ++?

Ist es ein C ++ - Limit oder hängt es von meinem Computer ab? Ist es optimierbar? Kommt es auf den Typ an, aus dem das Array besteht?

Kann ich diese Grenze irgendwie überschreiten oder muss ich nach einer besseren Möglichkeit suchen, Informationen zu speichern? Und was sollte der einfachste Weg sein?

Was ich tun muss, ist long long int auf einem Array zu speichern. Ich arbeite in einer Linux-Umgebung. Meine Frage ist: Was muss ich tun, wenn ich ein Array von N langen langen ganzen Zahlen mit N> 10 Ziffern speichern muss?

Ich brauche das, weil ich einen kryptografischen Algorithmus (wie zum Beispiel den p-Pollard) für die Schule schreibe und diese Wand aus ganzen Zahlen und der Länge der Arrays-Darstellung treffe.

Es gibt zwei Grenzen, die beide nicht von C ++, sondern von der Hardware erzwungen werden.

Die erste Grenze (sollte niemals erreicht werden) wird durch die Einschränkungen des Größentyps festgelegt, der zur Beschreibung eines Index im Array verwendet wird (und dessen Größe). Sie ergibt sich aus dem Maximalwert, den das System std::size_tannehmen kann. Dieser Datentyp ist groß genug, um die Größe eines Objekts in Byte zu enthalten

Die andere Grenze ist eine physikalische Speichergrenze. Je größer Ihre Objekte im Array sind, desto eher wird diese Grenze erreicht, da der Speicher voll ist. Beispielsweise benötigt a vector<int>einer bestimmten Größe n typischerweise ein Vielfaches des Speichers eines Arrays vom Typ vector<char>(abzüglich eines kleinen konstanten Werts), da intes normalerweise größer als ist char. Daher vector<char>kann a mehr Elemente enthalten als a, vector<int>bevor der Speicher voll ist. Gleiches gilt für rohe Arrays im C-Stil wie int[]und char[].

Darüber hinaus kann diese Obergrenze durch die Art der allocatorKonstruktion beeinflusst werden, vectorda ein allocatorSpeicher nach Belieben verwaltet werden kann. Ein sehr seltsamer, aber dennoch denkbarer Allokator könnte den Speicher so bündeln, dass identische Instanzen eines Objekts Ressourcen gemeinsam nutzen. Auf diese Weise können Sie viele identische Objekte in einen Container einfügen, der sonst den gesamten verfügbaren Speicher belegt.

Abgesehen davon setzt C ++ keine Grenzen.

Niemand erwähnte die Begrenzung der Größe des Stapelrahmens .

Es gibt zwei Stellen, an denen Speicher zugewiesen werden kann:

• Auf dem Heap (dynamisch zugewiesener Speicher).
  Die Größenbeschränkung ist hier eine Kombination aus verfügbarer Hardware und der Fähigkeit des Betriebssystems, Speicherplatz zu simulieren, indem andere Geräte verwendet werden, um nicht verwendete Daten vorübergehend zu speichern ( dh Seiten auf die Festplatte zu verschieben).
• Auf dem Stapel (lokal deklarierte Variablen).
  Die Größenbeschränkung ist hier vom Compiler definiert (mit möglichen Hardwarebeschränkungen). Wenn Sie die Compiler-Dokumentation lesen, können Sie diese Größe häufig anpassen.

Wenn Sie also ein Array dynamisch zuweisen (das Limit ist groß und wird von anderen Posts ausführlich beschrieben.

int* a1 = new int[SIZE];  // SIZE limited only by OS/Hardware

Wenn das Array auf dem Stapel zugewiesen ist, sind Sie alternativ durch die Größe des Stapelrahmens begrenzt. NB- Vektoren und andere Container haben eine geringe Präsenz im Stapel, aber normalerweise befindet sich der Großteil der Daten auf dem Heap.

int a2[SIZE]; // SIZE limited by COMPILER to the size of the stack frame

Aus praktischer und nicht aus theoretischer Sicht beträgt auf einem 32-Bit-Windows-System maximal 2 GB Arbeitsspeicher für einen einzelnen Prozess. Sie können das Limit überschreiten, indem Sie ein 64-Bit-Betriebssystem mit viel mehr physischem Speicher verwenden. Ob Sie dies tun oder nach Alternativen suchen, hängt jedoch stark von Ihren beabsichtigten Benutzern und deren Budgets ab. Sie können es auch mit PAE etwas erweitern .

Der Typ des Arrays ist sehr wichtig, da die Standardstrukturausrichtung auf vielen Compilern 8 Byte beträgt, was sehr verschwenderisch ist, wenn die Speichernutzung ein Problem darstellt. Wenn Sie Visual C ++ als Ziel für Windows verwenden, lesen Sie die Direktive #pragma pack , um dies zu überwinden.

Eine andere Sache, die Sie tun müssen, ist zu prüfen, was Ihnen bei Speicherkomprimierungstechniken helfen kann, wie z. B. spärliche Matrizen, spontane Komprimierung usw. Auch dies ist stark anwendungsabhängig. Wenn Sie Ihren Beitrag bearbeiten, um weitere Informationen darüber zu erhalten, was sich tatsächlich in Ihren Arrays befindet, erhalten Sie möglicherweise nützlichere Antworten.

Bearbeiten: Angesichts etwas mehr Informationen zu Ihren genauen Anforderungen scheint Ihr Speicherbedarf unkomprimiert zwischen 7,6 GB und 76 GB zu liegen, was eine ziemlich teure 64-Bit-Box erfordern würde, um als Array im Speicher in C ++ gespeichert zu werden. Es stellt sich die Frage, warum Sie die Daten im Speicher speichern möchten, wo man die Geschwindigkeit des Zugriffs voraussetzt und einen wahlfreien Zugriff zulässt. Der beste Weg, diese Daten außerhalb eines Arrays zu speichern, hängt davon ab, wie Sie darauf zugreifen möchten. Wenn Sie zufällig auf Array-Mitglieder zugreifen müssen, gibt es für die meisten Anwendungen Möglichkeiten, Datenklumpen zu gruppieren, auf die gleichzeitig zugegriffen wird. In großen GIS- und Geodatenbanken werden Daten beispielsweise häufig nach geografischen Gebieten gekachelt. In C ++ - Programmierbegriffen können Sie den Array-Operator [] überschreiben, um bei Bedarf Teile Ihrer Daten aus dem externen Speicher abzurufen.

Ich würde dem oben Gesagten zustimmen, wenn Sie Ihr Array mit initialisieren

 int myArray[SIZE] 

dann ist SIZE durch die Größe einer ganzen Zahl begrenzt. Sie können jedoch jederzeit einen Teil des Speichers mallocieren und einen Zeiger darauf haben, so groß wie Sie möchten, solange malloc nicht NULL zurückgibt.

Um die Antworten zusammenzufassen, zu erweitern und Ihre Frage direkt zu beantworten:

Nein, C ++ legt keine Grenzen für die Dimensionen eines Arrays fest.

Da das Array jedoch irgendwo im Speicher gespeichert werden muss, gelten speicherbezogene Beschränkungen, die von anderen Teilen des Computersystems auferlegt werden. Beachten Sie, dass sich diese Grenzwerte nicht direkt auf die Abmessungen (= Anzahl der Elemente) des Arrays beziehen , sondern auf dessen Größe (= Speicherplatz). Abmessungen ( D ) und in-Speichergröße ( S ) aus einer Anordnung ist nicht das gleiche, wie sie durch den Speicher durch ein einziges Element (genommen in Zusammenhang stehen E ): S = D * E .

JetztE hängt ab von:

• die Art der Array-Elemente (Elemente können kleiner oder größer sein)
• Speicherausrichtung (um die Leistung zu erhöhen, werden Elemente an Adressen platziert, die ein Vielfaches eines bestimmten Werts sind, was zu
  "verschwendetem Platz" (Auffüllen) zwischen Elementen führt
• Größe statischer Teile von Objekten (bei der objektorientierten Programmierung werden statische Komponenten von Objekten desselben Typs nur einmal gespeichert, unabhängig von der Anzahl solcher Objekte desselben Typs)

Beachten Sie außerdem, dass Sie im Allgemeinen unterschiedliche speicherbezogene Einschränkungen erhalten, wenn Sie die Array-Daten auf dem Stapel (als automatische Variable int t[N]:) oder auf dem Heap (dynamische Zuordnung mit malloc()/ newoder mithilfe von STL-Mechanismen) oder im statischen Teil des Prozessspeichers (as) zuweisen eine statische Variable :) static int t[N]. Selbst wenn Sie auf dem Heap zuweisen, benötigen Sie immer noch eine kleine Menge Speicher auf dem Stapel, um Verweise auf die vom Heap zugewiesenen Speicherblöcke zu speichern (dies ist jedoch normalerweise vernachlässigbar).

Die Größe des size_tTyps hat keinen Einfluss auf den Programmierer (ich gehe davon aus, dass der Programmierer den size_tTyp für die Indizierung verwendet, da er dafür ausgelegt ist), da der Compiler-Anbieter typedefeinen ganzzahligen Typ verwenden muss, der groß genug ist, um die für die jeweilige Plattform maximal mögliche Speichermenge zu adressieren die Architektur.

Die Ursachen für die Speichergrößenbeschränkungen stammen aus

• Für den Prozess verfügbarer Speicherplatz (der für 32-Bit-Anwendungen auf 2 ^ 32 Byte begrenzt ist, selbst auf 64-Bit-Betriebssystemkernen),
• die Aufteilung des Prozessspeichers (z. B. Größe des Prozessspeichers für Stapel oder Heap),
• die Fragmentierung des physischen Speichers (viele verstreute kleine freie Speicherfragmente sind nicht zum Speichern einer monolithischen Struktur anwendbar),
• Menge des physischen Speichers,
• und die Menge des virtuellen Speichers.

Sie können auf Anwendungsebene nicht "optimiert" werden. Sie können jedoch einen anderen Compiler verwenden (um die Stapelgrößenbeschränkungen zu ändern) oder Ihre Anwendung auf 64-Bit portieren oder auf ein anderes Betriebssystem portieren oder das physische / ändern Konfiguration des virtuellen Speichers der (virtuellen? physischen?) Maschine.

Es ist nicht ungewöhnlich (und sogar ratsam), alle oben genannten Faktoren als externe Störungen und damit als mögliche Ursachen für Laufzeitfehler zu behandeln und Speicherzuordnungsfehler in Ihrem Programmcode sorgfältig zu überprüfen und darauf zu reagieren.

Also schließlich: Während C ++ keine Grenzen setzt, müssen Sie beim Ausführen Ihres Codes immer noch nach ungünstigen speicherbezogenen Bedingungen suchen ... :-)

Wie viele hervorragende Antworten zeigten, gibt es viele Einschränkungen, die von Ihrer Version des C ++ - Compilers, dem Betriebssystem und den Computereigenschaften abhängen. Ich schlage jedoch das folgende Skript in Python vor, das das Limit auf Ihrem Computer überprüft.

Es verwendet die binäre Suche und prüft bei jeder Iteration, ob die mittlere Größe möglich ist, indem ein Code erstellt wird, der versucht, ein Array der Größe zu erstellen. Das Skript versucht, es zu kompilieren (leider funktioniert dieser Teil nur unter Linux) und die binäre Suche je nach Erfolg anzupassen. Hör zu:

import os

cpp_source = 'int a[{}]; int main() {{ return 0; }}'

def check_if_array_size_compiles(size):
        #  Write to file 1.cpp
        f = open(name='1.cpp', mode='w')
        f.write(cpp_source.format(m))
        f.close()
        #  Attempt to compile
        os.system('g++ 1.cpp 2> errors')
        #  Read the errors files
        errors = open('errors', 'r').read()
        #  Return if there is no errors
        return len(errors) == 0

#  Make a binary search. Try to create array with size m and
#  adjust the r and l border depending on wheather we succeeded
#  or not
l = 0
r = 10 ** 50
while r - l > 1:
        m = (r + l) // 2
        if check_if_array_size_compiles(m):
                l = m
        else:
                r = m

answer = l + check_if_array_size_compiles(r)
print '{} is the maximum avaliable length'.format(answer)

Sie können es auf Ihrem Computer speichern und starten, und es wird die maximale Größe gedruckt, die Sie erstellen können. Für meine Maschine ist es 2305843009213693951.

Eine Sache, die ich nicht glaube, wurde in den vorherigen Antworten erwähnt.

Ich spüre immer einen "schlechten Geruch" im Sinne eines Refactorings, wenn Leute solche Dinge in ihrem Design verwenden.

Dies ist ein riesiges Array und möglicherweise nicht die beste Möglichkeit, Ihre Daten sowohl unter Effizienz- als auch unter Leistungsgesichtspunkten darzustellen.

Prost,

rauben

Wenn Sie mit so großen Daten arbeiten müssen, müssen Sie sie in überschaubare Teile aufteilen. Auf keinem kleinen Computer passt alles in den Speicher. Sie können wahrscheinlich einen Teil der Daten von der Festplatte laden (was auch immer angemessen passt), Ihre Berechnungen und Änderungen daran vornehmen, sie auf der Festplatte speichern und dann wiederholen, bis sie abgeschlossen sind.

So ärgerlich unspezifisch alle aktuellen Antworten auch sind, sie sind meistens richtig, aber mit vielen Einschränkungen, die nicht immer erwähnt werden. Das Wesentliche ist, dass Sie zwei Obergrenzen haben und nur eine davon tatsächlich definiert ist, also YMMV :

1. Kompilierzeitlimits

Grundsätzlich, was Ihr Compiler erlaubt. Für Visual C ++ 2017 auf einer x64 Windows 10-Box ist dies meine maximale Grenze zur Kompilierungszeit, bevor die 2-GB-Grenze erreicht wird.

unsigned __int64 max_ints[255999996]{0};

Wenn ich das stattdessen tun würde,

unsigned __int64 max_ints[255999997]{0};

Ich würde bekommen:

Error C1126 automatic allocation exceeds 2G

Ich bin nicht sicher, wie 2G mit 255999996/ korreliert 7. Ich habe beide Zahlen gegoogelt, und das einzige, was ich finden konnte, das möglicherweise damit zusammenhängt, war dieses * nix Q & A über ein Präzisionsproblem mitdc . In beiden Fällen scheint es keine Rolle zu spielen, welchen Typ von int-Array Sie füllen möchten, sondern nur, wie viele Elemente zugewiesen werden können.

2. Laufzeitlimits

Ihr Stapel und Ihr Heap haben ihre eigenen Einschränkungen. Diese Grenzwerte sind sowohl Werte, die sich basierend auf den verfügbaren Systemressourcen ändern, als auch die "Schwere" Ihrer App. Mit meinen aktuellen Systemressourcen kann ich beispielsweise Folgendes ausführen:

int main()
{
    int max_ints[257400]{ 0 };
    return 0;
}

Aber wenn ich es nur ein bisschen optimiere ...

int main()
{
    int max_ints[257500]{ 0 };
    return 0;
}

Bam! Paketüberfluss!

Exception thrown at 0x00007FF7DC6B1B38 in memchk.exe: 0xC00000FD: Stack overflow (parameters: 0x0000000000000001, 0x000000AA8DE03000). Unhandled exception at 0x00007FF7DC6B1B38 in memchk.exe: 0xC00000FD: Stack overflow (parameters: 0x0000000000000001, 0x000000AA8DE03000).

Und nur um die ganze Schwere Ihres App-Punkts zu beschreiben, war dies gut zu gehen:

int main()
{
    int maxish_ints[257000]{ 0 };
    int more_ints[400]{ 0 };
    return 0;
}  

Dies verursachte jedoch einen Stapelüberlauf:

int main()
{
    int maxish_ints[257000]{ 0 };
    int more_ints[500]{ 0 };
    return 0;
}  

Ich bin überrascht, dass die max_size () -Mitgliedsfunktion von std :: vector hier nicht erwähnt wurde.

"Gibt die maximale Anzahl von Elementen zurück, die der Container aufgrund von Einschränkungen bei der System- oder Bibliotheksimplementierung aufnehmen kann, dh std :: distance (begin (), end ()) für den größten Container."

Wir wissen, dass dies std::vectorals dynamisches Array unter der Haube implementiert ist. Daher max_size()sollte die maximale Länge eines dynamischen Arrays auf Ihrem Computer sehr genau angegeben werden.

Das folgende Programm erstellt eine Tabelle mit der ungefähren maximalen Array-Länge für verschiedene Datentypen.

#include <iostream>
#include <vector>
#include <string>
#include <limits>

template <typename T>
std::string mx(T e) {
    std::vector<T> v;
    return std::to_string(v.max_size());
}

std::size_t maxColWidth(std::vector<std::string> v) {
    std::size_t maxWidth = 0;

    for (const auto &s: v)
        if (s.length() > maxWidth)
            maxWidth = s.length();

    // Add 2 for space on each side
    return maxWidth + 2;
}

constexpr long double maxStdSize_t = std::numeric_limits<std::size_t>::max();

// cs stands for compared to std::size_t
template <typename T>
std::string cs(T e) {
    std::vector<T> v;
    long double maxSize = v.max_size();
    long double quotient = maxStdSize_t / maxSize;
    return std::to_string(quotient);
}

int main() {
    bool v0 = 0;
    char v1 = 0;

    int8_t v2 = 0;
    int16_t v3 = 0;
    int32_t v4 = 0;
    int64_t v5 = 0;

    uint8_t v6 = 0;
    uint16_t v7 = 0;
    uint32_t v8 = 0;
    uint64_t v9 = 0;

    std::size_t v10 = 0;
    double v11 = 0;
    long double v12 = 0;

    std::vector<std::string> types = {"data types", "bool", "char", "int8_t", "int16_t",
                                      "int32_t", "int64_t", "uint8_t", "uint16_t",
                                      "uint32_t", "uint64_t", "size_t", "double",
                                      "long double"};

    std::vector<std::string> sizes = {"approx max array length", mx(v0), mx(v1), mx(v2),
                                      mx(v3), mx(v4), mx(v5), mx(v6), mx(v7), mx(v8),
                                      mx(v9), mx(v10), mx(v11), mx(v12)};

    std::vector<std::string> quotients = {"max std::size_t / max array size", cs(v0),
                                          cs(v1), cs(v2), cs(v3), cs(v4), cs(v5), cs(v6),
                                          cs(v7), cs(v8), cs(v9), cs(v10), cs(v11), cs(v12)};

    std::size_t max1 = maxColWidth(types);
    std::size_t max2 = maxColWidth(sizes);
    std::size_t max3 = maxColWidth(quotients);

    for (std::size_t i = 0; i < types.size(); ++i) {
        while (types[i].length() < (max1 - 1)) {
            types[i] = " " + types[i];
        }

        types[i] += " ";

        for  (int j = 0; sizes[i].length() < max2; ++j)
            sizes[i] = (j % 2 == 0) ? " " + sizes[i] : sizes[i] + " ";

        for  (int j = 0; quotients[i].length() < max3; ++j)
            quotients[i] = (j % 2 == 0) ? " " + quotients[i] : quotients[i] + " ";

        std::cout << "|" << types[i] << "|" << sizes[i] << "|" << quotients[i] << "|\n";
    }

    std::cout << std::endl;

    std::cout << "N.B. max std::size_t is: " <<
        std::numeric_limits<std::size_t>::max() << std::endl;

    return 0;
}

Unter meinem MacOS (Clang Version 5.0.1) erhalte ich Folgendes:

|  data types | approx max array length | max std::size_t / max array size |
|        bool |   9223372036854775807   |             2.000000             |
|        char |   9223372036854775807   |             2.000000             |
|      int8_t |   9223372036854775807   |             2.000000             |
|     int16_t |   9223372036854775807   |             2.000000             |
|     int32_t |   4611686018427387903   |             4.000000             |
|     int64_t |   2305843009213693951   |             8.000000             |
|     uint8_t |   9223372036854775807   |             2.000000             |
|    uint16_t |   9223372036854775807   |             2.000000             |
|    uint32_t |   4611686018427387903   |             4.000000             |
|    uint64_t |   2305843009213693951   |             8.000000             |
|      size_t |   2305843009213693951   |             8.000000             |
|      double |   2305843009213693951   |             8.000000             |
| long double |   1152921504606846975   |             16.000000            |

N.B. max std::size_t is: 18446744073709551615

Auf ideone gcc 8.3 bekomme ich:

|  data types | approx max array length | max std::size_t / max array size |
|        bool |   9223372036854775744   |             2.000000             |
|        char |   18446744073709551615  |             1.000000             |
|      int8_t |   18446744073709551615  |             1.000000             |
|     int16_t |   9223372036854775807   |             2.000000             |
|     int32_t |   4611686018427387903   |             4.000000             |
|     int64_t |   2305843009213693951   |             8.000000             |
|     uint8_t |   18446744073709551615  |             1.000000             |
|    uint16_t |   9223372036854775807   |             2.000000             |
|    uint32_t |   4611686018427387903   |             4.000000             |
|    uint64_t |   2305843009213693951   |             8.000000             |
|      size_t |   2305843009213693951   |             8.000000             |
|      double |   2305843009213693951   |             8.000000             |
| long double |   1152921504606846975   |             16.000000            |

N.B. max std::size_t is: 18446744073709551615

Es ist zu beachten, dass dies eine theoretische Grenze ist und dass auf den meisten Computern der Speicher knapp wird, bevor Sie diese Grenze erreichen. Zum Beispiel sehen wir, dass für type charon gccdie maximale Anzahl von Elementen gleich dem Maximum von ist std::size_t. Wenn wir dies versuchen , erhalten wir den Fehler:

prog.cpp: In function ‘int main()’:
prog.cpp:5:61: error: size of array is too large
  char* a1 = new char[std::numeric_limits<std::size_t>::max()];

Wie @MartinYork hervorhebt, ist die maximale Größe für statische Arrays durch die Größe Ihres Stapels begrenzt.

Wie bereits erwähnt, ist die Arraygröße durch Ihre Hardware und Ihr Betriebssystem (man ulimit) begrenzt. Ihre Software kann jedoch nur durch Ihre Kreativität eingeschränkt sein. Können Sie beispielsweise Ihr "Array" auf der Festplatte speichern? Benötigen Sie wirklich lange, lange Ints? Benötigen Sie wirklich ein dichtes Array? Benötigen Sie überhaupt ein Array?

Eine einfache Lösung wäre die Verwendung von 64-Bit-Linux. Selbst wenn Sie physisch nicht über genügend RAM für Ihr Array verfügen, können Sie mit dem Betriebssystem Speicher zuweisen, als ob Sie dies tun würden, da der für Ihren Prozess verfügbare virtuelle Speicher wahrscheinlich viel größer als der physische Speicher ist. Wenn Sie wirklich auf alles im Array zugreifen müssen, müssen Sie es auf der Festplatte speichern. Abhängig von Ihren Zugriffsmustern gibt es möglicherweise effizientere Möglichkeiten, dies zu tun (z. B. die Verwendung von mmap () oder das einfache sequentielle Speichern der Daten in einer Datei (in diesem Fall würde 32-Bit-Linux ausreichen)).

Ich würde dies umgehen, indem ich ein dynamisches 2D-Array erstelle:

long long** a = new long long*[x];
for (unsigned i = 0; i < x; i++) a[i] = new long long[y];

Mehr dazu hier https://stackoverflow.com/a/936702/3517001