¿Hay un límite máximo de longitud de matriz en C ++?

¿Hay una longitud máxima para una matriz en C ++?

¿Es un límite de C ++ o depende de mi máquina? ¿Es modificable? ¿Depende del tipo de la matriz?

¿Puedo romper ese límite de alguna manera o tengo que buscar una mejor manera de almacenar información? ¿Y cuál debería ser la forma más sencilla?

Lo que tengo que hacer es almacenar long long int en una matriz, estoy trabajando en un entorno Linux. Mi pregunta es: ¿qué debo hacer si necesito almacenar una matriz de N enteros largos largos con N> 10 dígitos?

Necesito esto porque estoy escribiendo algún algoritmo criptográfico (como, por ejemplo, el p-Pollard) para la escuela, y choco con este muro de enteros y longitud de representación de matrices.

Hay dos límites, ambos no impuestos por C ++ sino por el hardware.

El primer límite (nunca se debe alcanzar) está establecido por las restricciones del tipo de tamaño utilizado para describir un índice en la matriz (y el tamaño del mismo). Está dado por el valor máximo que el sistemastd::size_t puede tomar . Este tipo de datos es lo suficientemente grande como para contener el tamaño en bytes de cualquier objeto

El otro límite es un límite de memoria física. Cuanto más grandes sean sus objetos en la matriz, antes se alcanzará este límite porque la memoria está llena. Por ejemplo, a vector<int>de un tamaño dado n generalmente toma varias veces más memoria que una matriz de tipo vector<char>(menos un valor constante pequeño), ya intque generalmente es mayor que char. Por lo tanto, a vector<char>puede contener más elementos que vector<int>antes de que la memoria esté llena. Lo mismo cuenta para matrices de estilo C sin formato como int[]y char[].

Además, este límite superior puede estar influenciado por el tipo de allocatorutilizado para construir el vectorporque unallocator es libre de administrar la memoria de la forma que desee. Un asignador muy extraño pero concebible podría agrupar la memoria de tal manera que instancias idénticas de un objeto compartan recursos. De esta manera, podría insertar una gran cantidad de objetos idénticos en un contenedor que de otro modo usaría toda la memoria disponible.

Aparte de eso, C ++ no impone ningún límite.

Nadie mencionó el límite en el tamaño del marco de la pila .

Hay dos lugares donde se puede asignar memoria:

• En el montón (memoria asignada dinámicamente).
  El límite de tamaño aquí es una combinación de hardware disponible y la capacidad del sistema operativo para simular el espacio mediante el uso de otros dispositivos para almacenar temporalmente datos no utilizados ( es decir, mover páginas al disco duro).
• En la pila (variables declaradas localmente).
  El límite de tamaño aquí está definido por el compilador (con posibles límites de hardware). Si lee la documentación del compilador, a menudo puede modificar este tamaño.

Por lo tanto, si asigna una matriz dinámicamente (el límite es grande y otras publicaciones lo describen en detalle).

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

Alternativamente, si la matriz está asignada en la pila, entonces está limitado por el tamaño del marco de la pila. Los vectores NB y otros contenedores tienen una pequeña presencia en la pila, pero generalmente la mayor parte de los datos estará en el montón.

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

Mirándolo desde un punto de vista práctico más que teórico, en un sistema Windows de 32 bits, la cantidad total máxima de memoria disponible para un solo proceso es de 2 GB. Puede romper el límite yendo a un sistema operativo de 64 bits con mucha más memoria física, pero si hacer esto o buscar alternativas depende en gran medida de los usuarios previstos y sus presupuestos. También puede extenderlo un poco usando PAE .

El tipo de matriz es muy importante, ya que la alineación predeterminada de la estructura en muchos compiladores es de 8 bytes, lo cual es un desperdicio si el uso de memoria es un problema. Si está utilizando Visual C ++ para apuntar a Windows, consulte la directiva #pragma pack como una forma de superar esto.

Otra cosa que debe hacer es ver qué pueden ayudarle las técnicas de compresión de memoria, como matrices dispersas, compresión sobre la marcha, etc. De nuevo, esto depende en gran medida de la aplicación. Si edita su publicación para dar más información sobre lo que realmente está en sus matrices, puede obtener respuestas más útiles.

Editar: Dada un poco más de información sobre sus requisitos exactos, sus necesidades de almacenamiento parecen estar entre 7.6 GB y 76 GB sin comprimir, lo que requeriría una caja de 64 bits bastante costosa para almacenar como una matriz en memoria en C ++. Plantea la pregunta de por qué desea almacenar los datos en la memoria, donde se presume la velocidad de acceso, y permitir el acceso aleatorio. La mejor manera de almacenar estos datos fuera de una matriz se basa básicamente en cómo desea acceder a ellos. Si necesita acceder a los miembros de la matriz al azar, para la mayoría de las aplicaciones, existen formas de agrupar grupos de datos a los que se accede al mismo tiempo. Por ejemplo, en grandes SIG y bases de datos espaciales, los datos a menudo se agrupan por área geográfica. En los términos de programación de C ++, puede anular el operador de matriz [] para obtener partes de sus datos del almacenamiento externo según sea necesario.

Estoy de acuerdo con lo anterior, que si está inicializando su matriz con

 int myArray[SIZE] 

entonces SIZE está limitado por el tamaño de un número entero. Pero siempre puedes malloc un trozo de memoria y tener un puntero a él, tan grande como quieras siempre que malloc no devuelva NULL.

Para resumir las respuestas, extiéndalas y responda su pregunta directamente:

No, C ++ no impone ningún límite para las dimensiones de una matriz.

Pero como la matriz debe almacenarse en algún lugar de la memoria, también se aplican los límites relacionados con la memoria impuestos por otras partes del sistema informático. Tenga en cuenta que estos límites no se relacionan directamente con las dimensiones (= número de elementos) de la matriz, sino con su tamaño (= cantidad de memoria tomada). Dimensiones ( D ) y el tamaño en memoria ( S ) de una matriz no es el mismo, ya que están relacionadas por la memoria tomada por un solo elemento ( E ): S = D * E .

AhoraE depende de:

• El tipo de elementos de la matriz (los elementos pueden ser más pequeños o más grandes)
• alineación de memoria (para aumentar el rendimiento, los elementos se colocan en direcciones que son múltiplos de algún valor, lo que introduce
  'espacio desperdiciado' (relleno) entre elementos
• tamaño de las partes estáticas de los objetos (en la programación orientada a objetos, los componentes estáticos de los objetos del mismo tipo solo se almacenan una vez, independientemente del número de dichos objetos del mismo tipo)

También tenga en cuenta que generalmente obtiene diferentes limitaciones relacionadas con la memoria al asignar los datos de la matriz en la pila (como una variable automática int t[N]:), o en el montón (ubicación dinámica con malloc()/ newo utilizando mecanismos STL), o en la parte estática de la memoria del proceso (como Una variable estática:) static int t[N]. Incluso al asignar en el montón, aún necesita una pequeña cantidad de memoria en la pila para almacenar referencias a los bloques de memoria asignados al montón (pero esto es insignificante, por lo general).

El tamaño del size_ttipo no tiene influencia en el programador (supongo que el programador usa el size_ttipo para indexar, ya que está diseñado para ello), ya que el proveedor del compilador lo tiene typedefen un tipo entero lo suficientemente grande como para abordar la cantidad máxima de memoria posible para la plataforma dada arquitectura.

Las fuentes de las limitaciones del tamaño de la memoria provienen de

• cantidad de memoria disponible para el proceso (que está limitado a 2 ^ 32 bytes para aplicaciones de 32 bits, incluso en núcleos del sistema operativo de 64 bits),
• la división de la memoria de proceso (por ejemplo, la cantidad de memoria de proceso diseñada para la pila o el montón),
• la fragmentación de la memoria física (muchos fragmentos pequeños de memoria libre dispersos no son aplicables para almacenar una estructura monolítica),
• cantidad de memoria física
• y la cantidad de memoria virtual.

No se pueden 'ajustar' a nivel de aplicación, pero puede usar un compilador diferente (para cambiar los límites de tamaño de pila), o portar su aplicación a 64 bits, o portarla a otro sistema operativo, o cambiar el físico / configuración de memoria virtual de la máquina (¿virtual? ¿física?).

No es raro (e incluso aconsejable) tratar todos los factores anteriores como perturbaciones externas y, por lo tanto, como posibles fuentes de errores de tiempo de ejecución, y verificar cuidadosamente y reaccionar a los errores relacionados con la asignación de memoria en el código de su programa.

Entonces, finalmente: aunque C ++ no impone ningún límite, aún debe verificar las condiciones adversas relacionadas con la memoria al ejecutar su código ... :-)

Como se observaron muchas respuestas excelentes, hay muchos límites que dependen de su versión del compilador de C ++, el sistema operativo y las características de la computadora. Sin embargo, sugiero el siguiente script en Python que verifica el límite en su máquina.

Utiliza la búsqueda binaria y en cada iteración comprueba si el tamaño medio es posible creando un código que intente crear una matriz del tamaño. El script intenta compilarlo (lo siento, esta parte solo funciona en Linux) y ajustar la búsqueda binaria según el éxito. Echale un vistazo:

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)

Puede guardarlo en su máquina e iniciarlo, e imprimirá el tamaño máximo que puede crear. Para mi máquina es 2305843009213693951.

Una cosa que no creo que se haya mencionado en las respuestas anteriores.

Siempre estoy sintiendo un "mal olor" en el sentido de refactorización cuando la gente usa tales cosas en su diseño.

Esa es una gran variedad y posiblemente no sea la mejor manera de representar sus datos tanto desde el punto de vista de la eficiencia como desde el punto de vista del rendimiento.

salud,

Robar

Si tiene que lidiar con datos tan grandes, deberá dividirlos en fragmentos manejables. No cabe en la memoria de ninguna computadora pequeña. Probablemente pueda cargar una parte de los datos del disco (lo que sea razonablemente adecuado), realizar sus cálculos y cambios, almacenarlos en el disco y luego repetir hasta completar.

Tan molestamente inespecífico como lo son todas las respuestas actuales, en su mayoría son correctas pero con muchas advertencias, no siempre mencionadas. La esencia es que tienes dos límites superiores, y solo uno de ellos es algo realmente definido, por lo que YMMV :

1. Límites de tiempo de compilación

Básicamente, lo que permitirá su compilador. Para Visual C ++ 2017 en un cuadro de Windows 10 x64, este es mi límite máximo en tiempo de compilación antes de incurrir en el límite de 2 GB,

unsigned __int64 max_ints[255999996]{0};

Si hice esto en su lugar,

unsigned __int64 max_ints[255999997]{0};

Obtendría:

Error C1126 automatic allocation exceeds 2G

No estoy seguro de cómo 2G correllates a 255999996/ 7. Busqué en Google ambos números, y lo único que pude encontrar que posiblemente estaba relacionado fue este * nix Q&A sobre un problema de precisióndc . De cualquier manera, no parece importar qué tipo de matriz int está tratando de llenar, sino cuántos elementos se pueden asignar.

2. Límites de tiempo de ejecución

Su pila y montón tienen sus propias limitaciones. Estos límites son valores que cambian según los recursos del sistema disponibles, así como cuán "pesada" es su aplicación. Por ejemplo, con mis recursos actuales del sistema, puedo hacer que esto se ejecute:

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

Pero si lo retoco un poco ...

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

Bam! ¡Desbordamiento de pila!

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

Y solo para detallar todo el peso de su punto de aplicación, esto fue bueno:

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

Pero esto causó un desbordamiento de pila:

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

Me sorprende que la función miembro max_size () de std :: vector no se haya mencionado aquí.

"Devuelve el número máximo de elementos que el contenedor puede contener debido a limitaciones de implementación del sistema o de la biblioteca, es decir, std :: distance (begin (), end ()) para el contenedor más grande".

Sabemos que std::vectorse implementa como una matriz dinámica debajo del capó, por lo que max_size()debe proporcionar una aproximación muy cercana de la longitud máxima de una matriz dinámica en su máquina.

El siguiente programa crea una tabla de longitud de matriz máxima aproximada para varios tipos de datos.

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

En mi macOS (clang versión 5.0.1), obtengo lo siguiente:

|  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

En ideone gcc 8.3 obtengo:

|  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

Cabe señalar que este es un límite teórico y que en la mayoría de las computadoras, se quedará sin memoria mucho antes de alcanzar este límite. Por ejemplo, vemos que para type charon gcc, el número máximo de elementos es igual al máximo de std::size_t. Al intentar esto , obtenemos el error:

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

Por último, como señala @MartinYork, para las matrices estáticas el tamaño máximo está limitado por el tamaño de su pila.

Como ya se ha señalado, el tamaño de la matriz está limitado por su hardware y su sistema operativo (man ulimit). Sin embargo, su software solo puede estar limitado por su creatividad. Por ejemplo, ¿puede almacenar su "matriz" en el disco? ¿Realmente necesitas entradas largas y largas? ¿Realmente necesitas una matriz densa? ¿Necesitas una matriz?

Una solución simple sería usar Linux de 64 bits. Incluso si físicamente no tiene suficiente memoria RAM para su matriz, el sistema operativo le permitirá asignar memoria como lo hace, ya que la memoria virtual disponible para su proceso es probablemente mucho más grande que la memoria física. Si realmente necesita acceder a todo en la matriz, esto equivale a almacenarlo en el disco. Dependiendo de sus patrones de acceso, puede haber formas más eficientes de hacerlo (es decir: usando mmap (), o simplemente almacenando los datos secuencialmente en un archivo (en cuyo caso, Linux de 32 bits sería suficiente)).

Yo evitaría esto haciendo una matriz dinámica 2D:

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

más sobre esto aquí https://stackoverflow.com/a/936702/3517001