C++中是否存在数组长度的最大限制?

208

C++中的数组是否有最大长度限制?

这是一个C++的限制还是取决于我的计算机?它是可调整的吗?它是否取决于数组所包含的类型?

我能否以某种方式突破这个限制,或者必须寻找更好的存储信息的方法?那么最简单的方法应该是什么?

我需要做的是将long long int存储在数组中,我正在Linux环境下工作。我的问题是:如果我需要存储N个长达10位以上的long long整数的数组,我该怎么做?

我需要这样做是因为我正在为学校编写一些加密算法(例如p-Pollard),并遇到了整数和数组表示长度的难题。

12个回答

194

没有人提到堆栈帧的大小限制。

内存可以分配在两个地方:

  • 在堆(动态分配内存)。
    这里的大小限制是可用硬件和操作系统利用其他设备暂时存储未使用数据(例如将页面移动到硬盘)的能力的组合。
  • 在栈上(本地声明变量)。
    这里的大小限制是由编译器定义的(可能有硬件限制)。如果您阅读编译器文档,通常可以调整此大小。

因此,如果您动态分配数组(该限制很大,并由其他文章详细描述。

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

如果数组分配在堆栈上,那么你受到堆栈帧大小的限制。需要注意的是,向量和其他容器虽然在堆栈中存在,但通常大部分数据都在堆上。

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

6
大型数组的首选分配方式不是在堆栈或全局定义中,而是通过动态分配(通过 newmalloc)实现。 - Thomas Matthews
3
@Thomas Matthews:在我的世界里不是这样的。动态分配的对象需要管理。如果需要动态分配,我会使用一个代表动态分配内存的堆栈对象,比如std::vector。 - Martin York
4
有一个特殊情况被忽略了: 全局数组,虽然不太美观且最好避免使用,但它们不属于 的限制范围,而且你不需要使用 malloc / free 就能处理它们。 - ted
1
@ted,为什么应该“尽量避免”使用全局数组?更准确地说,我认为你指的是静态分配的数组。它们的作用域不一定是全局的。我认为它们比动态数组更好,因为你可以在它们上面使用绝对寻址(至少在Linux上),而这是你无法在动态分配的数组上做到的。 - Z boson
2
非常重要的一点。最近我发现了一个“生产质量”的开源项目,它提供了可配置的最大缓冲区大小。所有的缓冲区都是在堆栈上分配的,因此配置足够大的值会导致程序在启动时立即崩溃。 - aroth
显示剩余7条评论

174

有两个限制,都不是由C++强制实施的,而是由硬件决定的。

第一个限制(不应该被达到)是由用于描述数组中索引的大小类型(及其大小)的限制设置的。它由系统的std::size_t可以取到的最大值给出。这种数据类型足够大,可以包含任何对象的字节数。

另一个限制是物理内存限制。数组中对象越大,内存就越快满。例如,给定尺寸nvector<int>通常占用多倍于类型为vector<char>(减去一个小常数值)的数组的内存,因为int通常比char更大。因此,在内存满之前,vector<char>可能包含比vector<int>更多的项。对于像int[]char[]这样的原始C-style数组,情况也是一样。

此外,上限还可能受到用于构造vectorallocator类型的影响,因为allocator可以自由地管理任何内存。一个非常奇怪但可行的allocator可以以这样的方式池化内存,使相同实例的对象共享资源。这样,您可以将大量相同的对象插入到容器中,否则会使用所有可用内存。

除此之外,C++不强制执行任何限制。


20
通常来说,你很容易就会达到堆栈大小限制,特别是在使用线程时更是如此,这又取决于具体的实现方式(但可以进行更改)。 - Alaric
11
std::size_t通常(总是?)是指针的大小,而不是整数数学单元本地硬件支持的最大整数大小。在我使用过的每个x86操作系统中,32位操作系统的size_t为32位,64位操作系统的size_t为64位。 - Mr Fooz
2
我理解的是,数组的最大限制取决于处理器的最大值。这是由索引运算符引起的。例如,一台机器的字长可能为16位,但寻址寄存器为32位。内存块的大小受newmalloc传递的参数限制。比数组更大的内存块可以通过指针访问。 - Thomas Matthews
@Gabriel 在64位系统中,一个位置的地址存储在8个字节中。因此理论上,进程中字节数组的最大索引应该是(2^64)-1,对吗?如果我的硬件内存超过了这个限制,那么进程也无法越过这个限制。这个假设正确吗?而且,这个限制是由系统本身而不是语言所暗示的,对吗? - Sourav Kannantha B
@SouravKannanthaB 是的,限制是由系统而不是语言暗示的(在语言限制自己使用本地支持的整数数据类型的程度上)。 如果您假想的计算机具有更多硬件,则无法访问它。 但操作系统也不能。 您的计算机 不会 有更多硬件:那是100亿吉字节。 世界上最大的超级计算机只有其中的一小部分 - Konrad Rudolph
显示剩余6条评论

13

从实际的角度来看,在一个32位的Windows系统上,单个进程可以使用的最大内存总量为2GB。你可以通过使用64位操作系统和更多的物理内存来突破这一限制,但是是否这样做或寻找替代方案很大程度上取决于您的预期用户及其预算。还可以使用PAE进行一定程度的扩展。

数组的类型非常重要,因为许多编译器的默认结构对齐方式是8字节,如果内存使用是一个问题,这将非常浪费。如果你正在使用Visual C++针对Windows,可以查看#pragma pack指令来解决这个问题。

另一件事情是考虑一下哪些内存压缩技术可能会对你有帮助,例如稀疏矩阵、即时压缩等等...再次强调,这非常依赖于应用程序。如果您编辑您的帖子并提供一些有关数组中实际包含内容的信息,您可能会得到更有用的答案。

编辑:根据您的确切需求提供了更多信息,您的存储需求似乎在7.6GB到76GB之间(未压缩),这将需要一个相当昂贵的64位框来以C++中的数组形式存储。这引发了一个问题,为什么要将数据存储在内存中,通常是为了加快访问速度,并允许随机访问。最好的方式是将这些数据存储在数组之外,这基本上取决于您想如何访问它。如果需要随机访问数组成员,在大多数应用程序中,往往有一些方法可以将被同时访问的数据聚集在一起。例如,在大型GIS和空间数据库中,数据通常按地理区域进行分块处理。在C++编程方面,您可以覆盖[]数组运算符,根据需要从外部存储获取您的数据的部分。


1
有一些系统调用可以允许在程序空间之外分配内存;但这取决于操作系统,不具备可移植性。我们在嵌入式系统中使用了它们。 - Thomas Matthews

7

尽管当前的答案大多数都含糊不清,但它们大多数是正确的,但有许多注意事项并不总是被提到。 要点是,您有两个上限,其中只有一个是实际定义的内容,因此 YMMV

1. 编译时限制

基本上是您的编译器所允许的范围。对于在x64 Windows 10上使用Visual C++ 2017,在超过此编译时上限之前,我的最大限制为2GB,

unsigned __int64 max_ints[255999996]{0};

如果我改为这样做,
unsigned __int64 max_ints[255999997]{0};

我得到的错误信息是:

Error C1126 自动分配超过 2G

我不确定 2G 和 255999996/7 有什么关联。我搜索了这两个数字,唯一可能相关的是这个关于 dc 精度问题 的 *nix Q&A。无论你试图填充哪种类型的 int 数组,似乎都无关紧要,只要能够分配多少个元素。

2. 运行时限制

你的堆栈和堆各自有其限制。这些限制都是基于可用系统资源以及应用本身的“重量”而变化的值。例如,使用我的当前系统资源,我可以运行这个程序:

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

但是,如果我稍微调整一下...
int main()
{
    int max_ints[257500]{ 0 };
    return 0;
}

嘭!堆栈溢出了!

异常抛出于0x00007FF7DC6B1B38,文件名为memchk.exe: 0xC00000FD: 堆栈溢出 (参数: 0x0000000000000001, 0x000000AA8DE03000)。 未处理的异常发生于0x00007FF7DC6B1B38,文件名为memchk.exe: 0xC00000FD: 堆栈溢出 (参数: 0x0000000000000001, 0x000000AA8DE03000)。

为了详细阐述你的应用程序重要性,这一切都是好的:

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

但是这导致了一个堆栈溢出:
int main()
{
    int maxish_ints[257000]{ 0 };
    int more_ints[500]{ 0 };
    return 0;
}  

4
总结回答你的问题:

不,C++没有强制限制数组的维度

但由于数组必须存储在内存中,因此其他计算机系统部分所施加的与内存相关的限制也会适用。请注意,这些限制与数组的维度(=元素数)无直接关系,而是与其大小(=所占内存量)相关。数组的D维和内存大小S不同,它们通过单个元素所占内存(E)相关: S=D*E

现在,E取决于:

  • 数组元素的类型(元素可以更小或更大)
  • 内存对齐(为了提高性能,元素放置在某些值的倍数地址上,这会引入“浪费空间”(填充))
  • 对象静态部件的大小(在面向对象编程中,相同类型的对象的静态组件仅存储一次,与此类相同的对象数量无关)

还要注意,通过在堆栈上分配数组数据(作为自动变量:int t[N]),在堆上(使用malloc()/new或使用STL机制进行动态分配),或在进程内存的静态部分(作为静态变量:static int t[N])中,通常会获得不同的与内存相关的限制。即使在堆上分配,您仍然需要一些微小的堆栈内存来存储对分配的内存块的引用(但这通常是可以忽略的)。

size_t类型的大小对程序员没有影响(我假设程序员将size_t类型用于索引,因为它专为此设计),因为编译器提供者必须将其typedef为整数类型足够大,以便为给定平台架构寻址最大内存量。

内存大小限制的来源有:

  • 进程可用内存量(即使在64位操作系统内核上,32位应用程序也受到2^32字节的限制)
  • 进程内存的划分(例如,为堆或堆栈设计的进程内存量)
  • 物理内存的碎片化(许多散布的小型自由内存片段不适合存储一个单体结构)
  • 物理内存量
  • 虚拟内存的数量

这些限制无法在应用程序层面进行“微调”,但是您可以自由选择使用不同的编译器(以更改堆栈大小限制),或将应用程序移植到64位系统,或将其移植到另一个操作系统,或更改(虚拟?物理?)机器的物理/虚拟内存配置。

通常情况下(甚至建议如此),将所有上述因素视为外部干扰和可能的运行时错误来源,并仔细检查并对程序代码中与内存分配相关的错误做出反应。

最后:虽然C++没有强加任何限制,但在运行代码时仍需要检查不良的内存相关条件... :-)


4
我同意上面的观点,如果你正在初始化数组,则可以使用
 int myArray[SIZE] 

如果使用整数,那么SIZE的大小会受到限制。但是,您可以始终分配一块内存,并拥有一个指向它的指针,只要malloc不返回NULL,您就可以拥有任意大小的内存块。


1
我不确定这是否有误,或者是我误解了你的意思,或者其他原因。例如,MSVC17编译器可以防止这种情况:int oops[INT_MAX]{0}; 它会生成错误信息:C2148 - 数组的总大小不能超过0x7fffffff字节 - kayleeFrye_onDeck
拥有16GB DDR4内存,在Windows 10上使用VS2017进行调试之前,当前已使用约66%的内存,我对可以使用多大的int数组进行初始化并赋值为0没有明确的限制。有时我可以使用大约257k个元素,有时会出现堆栈溢出。如果我除了主要的数组之外添加了任何内容,那么这个数字就会下降(显然)。我不得不进行实验来确定这个数字,因此我不认为除了在真空中知道您的理论极限之外,这个指标是可靠的。 - kayleeFrye_onDeck

3
作为许多优秀答案所指出的那样,许多限制取决于您的C++编译器版本、操作系统和计算机特性。 但是,我建议使用以下Python脚本检查机器上的限制。
它使用二分搜索,在每次迭代中通过创建尝试创建该大小数组的代码来检查中间大小是否可能。 脚本尝试进行编译(抱歉,此部分仅适用于Linux),并根据成功调整二分搜索。 请查看以下内容:
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)

您可以将其保存到计算机并启动它,它将打印您可以创建的最大大小。对于我的机器,它是2305843009213693951。


3
我很惊讶std::vectormax_size()成员函数没有在这里提到。

"由于系统或库实现限制,即 std::distance(begin(), end()) 为最大容器元素数,此函数返回容器能够容纳的最大元素数。"

我们知道std::vector在底层是作为一个动态数组实现的,因此max_size()应该给出关于机器上动态数组的最大长度的非常接近的近似值。
下面的程序构建了一个包含各种数据类型的近似最大数组长度表。
#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;
}

在我的macOS上(clang版本5.0.1),我得到了以下结果:
|  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

ideone gcc 8.3 上,我得到:

|  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

需要注意的是,这是一个理论上的极限,在大多数计算机上,您在达到此极限之前就会耗尽内存。例如,我们发现在gcc上对于char类型,最大元素数量等于std::size_t的最大值。尝试this时,我们会收到错误提示:
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()];

最后,正如@MartinYork所指出的那样,对于静态数组,其最大大小受堆栈大小的限制。

2

如果你需要处理如此大量的数据,你需要将其分成可管理的块。它不会全部适合任何小型计算机的内存中。你可以从磁盘加载一部分数据(任何合理适合的),对其进行计算和更改,将其存储到磁盘中,然后重复此过程,直到完成。


另外参见归并排序的示例算法,用于处理数据过大而无法放入内存。 - Thomas Matthews

2

在之前的回答中可能没有提到的一点是,我总是感觉在重构时会出现“异味”。

从效率和性能的角度来看,那是一个巨大的数组,可能不是表示数据的最佳方式。

祝好,

罗布


你有什么建议我应该使用什么? - luiss
如果您能告诉我们您正在存储的数据,那么也许我们可以帮忙。(-: - Rob Wells
抱歉,Luis,我的第一次回答非常轻率。 它将受到您的数据性质的驱动。您的数据关系将驱动您用于表示数据的模型。然后,集合应该就显而易见了。如果不是这样,我会担心数据模型。 - Rob Wells
不要对我这么轻率:用类似这样的玩具做一个缓存数据库怎么样?http://www.tweaktown.com/news/22066/intel_s_latest_server_board_supports_up_to_1tb_of_ram/index.html - user1382306

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接