Y a-t-il une limite de longueur maximale du tableau en C++ ?

Question

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

S'agit-il d'une limite en C++ ou cela dépend-il de ma machine? Est-ce modifiable? Est-ce en fonction du type de données utilisé pour le tableau?

Puis-je contourner cette limite d'une manière ou d'une autre ou dois-je chercher un meilleur moyen de stocker les informations? Et quel serait le moyen le plus simple?

Mon objectif est de stocker de longues valeurs de type long long int dans un tableau, je travaille dans un environnement Linux. Ma question est : que dois-je faire si j'ai besoin de stocker un tableau de N longs entiers longs avec N> 10 chiffres?

J'ai besoin de cela car je suis en train d'écrire un algorithme cryptographique (comme par exemple le p-Pollard) pour l'école, et je me heurte à ce mur des entiers et de la représentation de la longueur des tableaux.

Answer 1

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

Il y a deux endroits où la mémoire peut être allouée:

• 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 dispositifs pour stocker temporairement les données inutilisées (c.-à-d. déplacer des pages vers le disque dur).
• Sur la pile (variables déclarées localement).
  La limite de taille ici est définie par le compilateur (avec d'éventuelles limites matérielles). Si vous lisez la documentation du compilateur, vous pouvez souvent ajuster cette taille.

Ainsi, si vous allouez un tableau de manière dynamique (la limite est large et décrite en détail dans d'autres publications).

int* a1 = new int[SIZE];  // SIZE limitée uniquement par le SE/Système Hardware

Alternativement, si le tableau est alloué sur la pile, vous êtes limité par la taille du cadre de pile. N.B. les vecteurs et autres conteneurs ont une petite présence sur la pile mais généralement la majeure partie des données sera sur le tas.

int a2[SIZE]; // SIZE limitée par le COMPILATEUR à la taille du cadre de pile

Answer 2

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

La première limite (qui ne devrait jamais être atteinte) est fixée par les restrictions de la taille du type utilisé pour décrire un index dans le tableau (et sa taille). Elle est donnée par la valeur maximale que le type std::size_t du système peut prendre. Ce type de données est assez 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 grands, plus cette limite est atteinte rapidement car la mémoire est pleine. Par exemple, un vector d'une taille donnée n prend généralement plusieurs fois plus de mémoire qu'un tableau de type vector (moins une petite valeur constante), puisque int est généralement plus grand que char. Par conséquent, un vector peut contenir plus d'éléments qu'un vector avant que la mémoire ne soit pleine. Il en va de même pour les tableaux de style C brut comme int[] et char[].

De plus, cette limite supérieure peut être influencée par le type d'allocator utilisé pour construire le vector car un allocator est libre de gérer la mémoire de la manière qu'il veut. Un allocator très étrange mais néanmoins concevable pourrait regrouper la mémoire de telle manière que des instances identiques d'un objet partagent des ressources. De cette manière, vous pourriez insérer beaucoup d'objets identiques dans un conteneur qui sinon utiliserait toute la mémoire disponible.

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

Answer 3

En le regardant 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 dépasser la limite en passant à un système d'exploitation 64 bits avec beaucoup plus de mémoire physique, mais que vous choisissiez de le faire ou de chercher 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 du tableau est très important, car la structure d'alignement par défaut sur de nombreux compilateurs est de 8 octets, ce qui est très gaspilleur si l'utilisation de mémoire est un problème. Si vous utilisez Visual C++ pour cibler Windows, consultez la directive #pragma pack comme moyen de surmonter cela.

Une autre chose à faire est de regarder quelles techniques de compression en mémoire pourraient vous aider, telles que les matrices creuses, la compression à la volée, etc... Encore une fois, cela dépend beaucoup de l'application. Si vous éditez votre message pour donner plus d'informations sur ce qui se trouve réellement dans vos tableaux, vous pourriez obtenir des réponses plus utiles.

Édition : Compte tenu de quelques informations supplémentaires sur vos exigences exactes, vos besoins de stockage semblent se situer entre 7,6 Go et 76 Go non compressés, ce qui nécessiterait une boîte 64 bits assez coûteuse pour stocker un tableau en mémoire en C++. Cela soulève la question de pourquoi vous voulez stocker les données en mémoire, où l'on présume pour la rapidité 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 surtout de la manière dont vous souhaitez y accéder. Si vous avez besoin d'accéder de manière aléatoire aux membres du tableau, pour la plupart des applications, il y a tendance à être des moyens de regrouper des tas de données qui ont tendance à être accessibles en même temps. Par exemple, dans de grandes bases de données GIS et spatiales, les données sont souvent divisées en tuiles par zone géographique. En termes de programmation C++, vous pouvez remplacer l'opérateur [] du tableau pour extraire des portions de vos données à partir d'un stockage externe au besoin.

Answer 4

Je serais d'accord avec ce qui précède, selon lequel si vous initialisez votre tableau avec

 int myArray[SIZE]

alors SIZE est limité par la taille d'un entier. Mais vous pouvez toujours allouer dynamiquement un morceau de mémoire et avoir un pointeur vers celui-ci, aussi grand que vous le souhaitez tant que malloc ne retourne pas NULL.

Answer 5

Une chose que je ne pense pas avoir é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 tableau énorme et peut-être pas la meilleure façon de représenter vos données à la fois du point de vue de l'efficacité et du point de vue des performances.

Santé,

Rob