Existe-t-il une limite de longueur maximale de tableau en C ++?

Existe-t-il une longueur maximale pour un tableau en C ++?

Est-ce une limite C ++ ou dépend-elle de ma machine? Est-ce que c'est modifiable? Cela dépend-il du type de la matrice?

Puis-je briser cette limite d'une manière ou d'une autre ou dois-je rechercher un meilleur moyen de stocker des informations? Et quel devrait être le moyen le plus simple?

Ce que je dois faire est de stocker un long long int sur un tableau, je travaille dans un environnement Linux. Ma question est: que dois-je faire si je dois stocker un tableau de N entiers longs longs avec N> 10 chiffres?

J'en ai besoin parce que j'écris un algorithme cryptographique (comme par exemple le p-Pollard) pour l'école, et que je frappe ce mur d'entiers et de longueur de représentation des tableaux.

Il y a deux limites, toutes deux non imposées par C ++ mais plutôt par le matériel.

La première limite (ne doit jamais être atteinte) est fixée par les restrictions du type de taille utilisé pour décrire un index dans le tableau (et sa taille). Il est donné par la valeur maximale que le système std::size_tpeut prendre. Ce type de données est suffisamment grand pour contenir la taille en octets de n'importe quel objet

L'autre limite est une limite de mémoire physique. Plus vos objets dans le tableau sont volumineux, plus cette limite est atteinte tôt car la mémoire est pleine. Par exemple, a vector<int>d'une taille donnée n prend généralement plusieurs fois plus de mémoire qu'un tableau de type vector<char>(moins une petite valeur constante), car il intest généralement plus grand que char. Par conséquent, un vector<char>peut contenir plus d'éléments qu'un vector<int>avant que la mémoire ne soit pleine. Il en va de même pour les tableaux de style C bruts comme int[]et char[].

De plus, cette limite supérieure peut être influencée par le type de allocatorutilisé pour construire le vectorcar un allocatorest libre de gérer la mémoire comme il le souhaite. Un allocateur très étrange mais néanmoins imaginable pourrait regrouper la mémoire de telle manière que des instances identiques d'un objet partagent des ressources. De cette façon, vous pouvez insérer de nombreux objets identiques dans un conteneur qui, autrement, utiliserait toute la mémoire disponible.

En dehors de cela, C ++ n'applique aucune limite.

Personne n'a mentionné la limite de la taille du cadre de la pile .

Il y a deux emplacements de mémoire pouvant être alloués:

• Sur le tas (mémoire allouée dynamiquement).
  La limite de taille ici est une combinaison du matériel disponible et de la capacité du système d'exploitation à simuler de l'espace en utilisant d'autres périphériques pour stocker temporairement les données inutilisées ( c'est-à-dire déplacer les pages sur le disque dur).
• Sur la pile (variables déclarées localement).
  La limite de taille ici est définie par le compilateur (avec des limites matérielles possibles). Si vous lisez la documentation du compilateur, vous pouvez souvent modifier cette taille.

Ainsi si vous allouez dynamiquement un tableau (la limite est grande et décrite en détail par d'autres articles.

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

Sinon, si le tableau est alloué sur la pile, vous êtes limité par la taille du cadre de la pile. NB Les vecteurs et autres conteneurs ont une petite présence dans la pile, mais généralement la majeure partie des données se trouve sur le tas.

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

En regardant cela d'un point de vue pratique plutôt que théorique, sur un système Windows 32 bits, la quantité totale maximale de mémoire disponible pour un seul processus est de 2 Go. Vous pouvez briser la limite en passant à un système d'exploitation 64 bits avec beaucoup plus de mémoire physique, mais le fait de le faire ou de rechercher des alternatives dépend beaucoup de vos utilisateurs prévus et de leurs budgets. Vous pouvez également l'étendre quelque peu en utilisant PAE .

Le type de tableau est très important, car l'alignement de la structure par défaut sur de nombreux compilateurs est de 8 octets, ce qui est très inutile si l'utilisation de la mémoire est un problème. Si vous utilisez Visual C ++ pour cibler Windows, consultez la directive #pragma pack pour résoudre ce problème.

Une autre chose à faire est de regarder ce que les techniques de compression de la mémoire pourraient vous aider, comme les matrices éparses, la compression à la volée, etc ... Encore une fois, cela dépend fortement de l'application. Si vous modifiez votre message pour donner plus d'informations sur ce qui se trouve réellement dans vos tableaux, vous obtiendrez peut-être des réponses plus utiles.

Edit: Étant donné un peu plus d'informations sur vos besoins exacts, vos besoins de stockage semblent être compris entre 7,6 Go et 76 Go non compressés, ce qui nécessiterait une boîte de 64 bits assez coûteuse pour stocker en tant que tableau en mémoire en C ++. Cela soulève la question de savoir pourquoi voulez-vous stocker les données en mémoire, là où l'on suppose la vitesse d'accès, et pour permettre un accès aléatoire. La meilleure façon de stocker ces données en dehors d'un tableau dépend en grande partie de la façon dont vous souhaitez y accéder. Si vous devez accéder aux membres du groupe de manière aléatoire, pour la plupart des applications, il existe généralement des moyens de regrouper des groupes de données qui ont tendance à être consultés en même temps. Par exemple, dans les grandes bases de données SIG et spatiales, les données sont souvent regroupées par zone géographique. En termes de programmation C ++, vous pouvez remplacer l'opérateur de tableau [] pour récupérer des parties de vos données à partir du stockage externe si nécessaire.

Je suis d'accord avec ce qui précède, que si vous initialisez votre tableau avec

 int myArray[SIZE] 

alors SIZE est limité par la taille d'un entier. Mais vous pouvez toujours malloc une partie de la mémoire et avoir un pointeur vers elle, aussi gros que vous le souhaitez tant que malloc ne renvoie pas NULL.

Pour résumer les réponses, les étendre et pour répondre directement à votre question:

Non, C ++ n'impose aucune limite pour les dimensions d'un tableau.

Mais comme la matrice doit être stockée quelque part en mémoire, les limites liées à la mémoire imposées par d'autres parties du système informatique s'appliquent. Notez que ces limites ne sont pas directement liées aux dimensions (= nombre d'éléments) du tableau, mais plutôt à sa taille (= quantité de mémoire prise). Dimensions ( D ) et la taille (en mémoire S ) d'un réseau ne sont pas les mêmes, car ils sont liés par la mémoire prise par un seul élément ( E ): S = D * E .

MaintenantE dépend de:

• le type des éléments du tableau (les éléments peuvent être plus petits ou plus grands)
• alignement de la mémoire (pour augmenter les performances, les éléments sont placés à des adresses qui sont des multiplications d'une certaine valeur, ce qui introduit un
  `` espace perdu '' (remplissage) entre les éléments
• taille des parties statiques des objets (dans la programmation orientée objet, les composants statiques des objets du même type ne sont stockés qu'une seule fois, indépendamment du nombre de ces objets du même type)

Notez également que vous obtenez généralement différentes limitations liées à la mémoire en allouant les données du tableau sur la pile (en tant que variable automatique int t[N]:), ou sur le tas (allocation dynamique avec malloc()/ newou en utilisant des mécanismes STL), ou dans la partie statique de la mémoire de processus (comme une variable statique:) static int t[N]. Même lors de l'allocation sur le tas, vous avez toujours besoin d'une petite quantité de mémoire sur la pile pour stocker des références aux blocs de mémoire alloués au tas (mais c'est généralement négligeable).

La taille du size_ttype n'a aucune influence sur le programmeur (je suppose que le programmeur utilise le size_ttype pour l'indexation, comme il est conçu pour cela), car le fournisseur du compilateur doit typedeflui donner un type entier suffisamment grand pour adresser la quantité maximale de mémoire possible pour la plate-forme donnée architecture.

Les sources des limitations de la taille de la mémoire proviennent de

• quantité de mémoire disponible pour le processus (qui est limitée à 2 ^ 32 octets pour les applications 32 bits, même sur les noyaux OS 64 bits),
• la division de la mémoire de processus (par exemple la quantité de mémoire de processus conçue pour la pile ou le tas),
• la fragmentation de la mémoire physique (de nombreux petits fragments de mémoire libre dispersés ne sont pas applicables au stockage d'une structure monolithique),
• quantité de mémoire physique,
• et la quantité de mémoire virtuelle.

Ils ne peuvent pas être `` modifiés '' au niveau de l'application, mais vous êtes libre d'utiliser un autre compilateur (pour modifier les limites de taille de la pile), ou portez votre application en 64 bits, ou portez-la sur un autre système d'exploitation, ou modifiez le / configuration de la mémoire virtuelle de la machine (virtuelle? physique?).

Il n'est pas rare (et même conseillé) de traiter tous les facteurs ci-dessus comme des perturbations externes et donc comme des sources possibles d'erreurs d'exécution, et de soigneusement vérifier et réagir aux erreurs liées à l'allocation de mémoire dans le code de votre programme.

Donc enfin: bien que C ++ n'impose aucune limite, vous devez quand même vérifier les conditions défavorables liées à la mémoire lors de l'exécution de votre code ... :-)

Comme l'ont noté de nombreuses excellentes réponses, il existe de nombreuses limites qui dépendent de votre version du compilateur C ++, du système d'exploitation et des caractéristiques de l'ordinateur. Cependant, je suggère le script suivant sur Python qui vérifie la limite sur votre machine.

Il utilise la recherche binaire et à chaque itération vérifie si la taille moyenne est possible en créant un code qui tente de créer un tableau de la taille. Le script essaie de le compiler (désolé, cette partie ne fonctionne que sous Linux) et d'ajuster la recherche binaire en fonction du succès. Vérifiez-le:

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)

Vous pouvez l'enregistrer sur votre machine et la lancer, et elle imprimera la taille maximale que vous pouvez créer. Pour ma machine, c'est 2305843009213693951.

Une chose que je ne pense pas a été mentionnée dans les réponses précédentes.

Je sens toujours une "mauvaise odeur" dans le sens du refactoring lorsque les gens utilisent de telles choses dans leur conception.

C'est un vaste éventail et peut-être pas la meilleure façon de représenter vos données à la fois d'un point de vue d'efficacité et d'un point de vue de performance.

à votre santé,

Rob

Si vous devez gérer des données aussi volumineuses, vous devrez les diviser en blocs gérables. Tout ne rentrera pas dans la mémoire d'un petit ordinateur. Vous pouvez probablement charger une partie des données du disque (ce qui convient raisonnablement), effectuer vos calculs et les modifier, les stocker sur le disque, puis répéter jusqu'à ce que vous ayez terminé.

Aussi ennuyeusement non spécifiques que soient toutes les réponses actuelles, elles ont généralement raison, mais avec de nombreuses mises en garde, pas toujours mentionnées. L'essentiel est que vous avez deux limites supérieures, et une seule d'entre elles est réellement définie, donc YMMV :

1. Délais de compilation

Fondamentalement, ce que votre compilateur autorisera. Pour Visual C ++ 2017 sur une boîte x64 Windows 10, il s'agit de ma limite maximale au moment de la compilation avant d'engager la limite de 2 Go,

unsigned __int64 max_ints[255999996]{0};

Si je faisais ça à la place,

unsigned __int64 max_ints[255999997]{0};

J'aurais:

Error C1126 automatic allocation exceeds 2G

Je ne sais pas comment 2G corrèle à 255999996/ 7. J'ai recherché sur Google les deux nombres, et la seule chose que j'ai pu trouver qui était peut-être liée était cette * nix Q&A sur un problème de précision avecdc . Dans tous les cas, le type de tableau int que vous essayez de remplir ne semble pas avoir d'importance, le nombre d'éléments pouvant être alloués.

2. Limites d'exécution

Votre pile et votre tas ont leurs propres limites. Ces limites sont à la fois des valeurs qui changent en fonction des ressources système disponibles, ainsi que du «poids» de votre application elle-même. Par exemple, avec mes ressources système actuelles, je peux faire fonctionner ceci:

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

Mais si je le peaufine un peu ...

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

Bam! Débordement de pile!

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).

Et juste pour détailler toute la lourdeur de votre point d'application, c'était bon à faire:

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

Mais cela a provoqué un débordement de pile:

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

Je suis surpris que la fonction membre max_size () de std :: vector n'ait pas été mentionnée ici.

"Renvoie le nombre maximum d'éléments que le conteneur est capable de contenir en raison des limitations d'implémentation du système ou de la bibliothèque, c'est-à-dire std :: distance (begin (), end ()) pour le plus grand conteneur."

Nous savons que cela std::vectorest implémenté comme un tableau dynamique sous le capot, donc max_size()devrait donner une approximation très proche de la longueur maximale d'un tableau dynamique sur votre machine.

Le programme suivant crée un tableau de la longueur maximale approximative du tableau pour différents types de données.

#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;
}

Sur mon macOS (version 5.0.1 de clang), j'obtiens ce qui suit:

|  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

Sur ideone gcc 8.3, j'obtiens:

|  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

Il est à noter qu'il s'agit d'une limite théorique et que sur la plupart des ordinateurs, vous manquerez de mémoire bien avant d'atteindre cette limite. Par exemple, nous voyons que pour type charon gcc, le nombre maximum d'éléments est égal au maximum de std::size_t. En essayant ceci , nous obtenons l'erreur:

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()];

Enfin, comme le souligne @MartinYork, pour les tableaux statiques, la taille maximale est limitée par la taille de votre pile.

Comme cela a déjà été souligné, la taille du tableau est limitée par votre matériel et votre système d'exploitation (man ulimit). Cependant, votre logiciel ne peut être limité que par votre créativité. Par exemple, pouvez-vous stocker votre «matrice» sur le disque? Avez-vous vraiment besoin de longs longs entiers? Avez-vous vraiment besoin d'un tableau dense? Avez-vous même besoin d'un tableau?

Une solution simple serait d'utiliser Linux 64 bits. Même si vous ne disposez pas physiquement de suffisamment de RAM pour votre matrice, le système d'exploitation vous permettra d'allouer de la mémoire comme si vous le faisiez puisque la mémoire virtuelle disponible pour votre processus est probablement beaucoup plus grande que la mémoire physique. Si vous avez vraiment besoin d'accéder à tout ce qui se trouve dans la matrice, cela revient à le stocker sur disque. En fonction de vos modèles d'accès, il peut y avoir des moyens plus efficaces de le faire (par exemple: utiliser mmap (), ou simplement stocker les données séquentiellement dans un fichier (auquel cas Linux 32 bits suffirait)).

Je contournerais cela en créant un tableau dynamique 2d:

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

plus à ce sujet ici https://stackoverflow.com/a/936702/3517001