在c++中数组有最大长度吗?

这是c++的限制还是取决于我的机器?它是否可以调整?它取决于数组的类型吗?

我能以某种方式打破这个限制吗?还是我必须寻找更好的存储信息的方式?最简单的方法是什么?

我要做的是在一个数组中存储long long int,我在Linux环境中工作。我的问题是:如果我需要存储一个包含N个长整数和N个>个10位数字的数组,我该怎么做?

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


当前回答

从实际而非理论的角度来看,在32位Windows系统上,单个进程可用的最大内存总量是2 GB。您可以通过使用具有更多物理内存的64位操作系统来打破这个限制,但是是这样做还是寻找替代方案在很大程度上取决于您的预期用户和他们的预算。您还可以使用PAE对其进行某种程度的扩展。

数组的类型非常重要,因为许多编译器上的默认结构对齐是8字节,如果内存使用有问题,这是非常浪费的。如果你使用Visual c++瞄准Windows,可以使用#pragma pack指令来克服这个问题。

另一件要做的事情是看看哪些内存压缩技术可以帮助你,比如稀疏矩阵,动态压缩等等……这也是高度依赖于应用程序的。如果你编辑你的文章来提供更多关于数组中实际内容的信息,你可能会得到更有用的答案。

Edit: Given a bit more information on your exact requirements, your storage needs appear to be between 7.6 GB and 76 GB uncompressed, which would require a rather expensive 64 bit box to store as an array in memory in C++. It raises the question why do you want to store the data in memory, where one presumes for speed of access, and to allow random access. The best way to store this data outside of an array is pretty much based on how you want to access it. If you need to access array members randomly, for most applications there tend to be ways of grouping clumps of data that tend to get accessed at the same time. For example, in large GIS and spatial databases, data often gets tiled by geographic area. In C++ programming terms you can override the [] array operator to fetch portions of your data from external storage as required.

其他回答

我很惊讶std::vector的max_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的最大值。尝试这个,我们得到错误:

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指出的,对于静态数组,最大大小受限于堆栈的大小。

有一件事我认为在之前的回答中没有提到。

当人们在设计中使用这些东西时,我总是感觉到重构的“臭味”。

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

欢呼,

Rob

从实际而非理论的角度来看,在32位Windows系统上,单个进程可用的最大内存总量是2 GB。您可以通过使用具有更多物理内存的64位操作系统来打破这个限制,但是是这样做还是寻找替代方案在很大程度上取决于您的预期用户和他们的预算。您还可以使用PAE对其进行某种程度的扩展。

数组的类型非常重要,因为许多编译器上的默认结构对齐是8字节,如果内存使用有问题,这是非常浪费的。如果你使用Visual c++瞄准Windows,可以使用#pragma pack指令来克服这个问题。

另一件要做的事情是看看哪些内存压缩技术可以帮助你,比如稀疏矩阵,动态压缩等等……这也是高度依赖于应用程序的。如果你编辑你的文章来提供更多关于数组中实际内容的信息,你可能会得到更有用的答案。

Edit: Given a bit more information on your exact requirements, your storage needs appear to be between 7.6 GB and 76 GB uncompressed, which would require a rather expensive 64 bit box to store as an array in memory in C++. It raises the question why do you want to store the data in memory, where one presumes for speed of access, and to allow random access. The best way to store this data outside of an array is pretty much based on how you want to access it. If you need to access array members randomly, for most applications there tend to be ways of grouping clumps of data that tend to get accessed at the same time. For example, in large GIS and spatial databases, data often gets tiled by geographic area. In C++ programming terms you can override the [] array operator to fetch portions of your data from external storage as required.

前面已经指出,数组大小受硬件和操作系统的限制(man ulimit)。不过,你的软件可能只受限于你的创造力。例如,您可以将“数组”存储在磁盘上吗?你真的需要长整型吗?你真的需要密集数组吗?你需要数组吗?

One simple solution would be to use 64 bit Linux. Even if you do not physically have enough ram for your array, the OS will allow you to allocate memory as if you do since the virtual memory available to your process is likely much larger than the physical memory. If you really need to access everything in the array, this amounts to storing it on disk. Depending on your access patterns, there may be more efficient ways of doing this (ie: using mmap(), or simply storing the data sequentially in a file (in which case 32 bit Linux would suffice)).

尽管目前所有的答案都不明确,但令人恼火的是,它们大多是正确的,但也有许多不常被提及的警告。要点是,你有两个上限,其中只有一个是真正定义的,所以YMMV:

1. 编译时的限制

基本上,你的编译器将允许什么。对于x64 Windows 10盒子上的Visual c++ 2017,这是我在产生2GB限制之前的编译时的最大限制,

unsigned __int64 max_ints[255999996]{0};

如果我这样做,

unsigned __int64 max_ints[255999997]{0};

我得到:

错误C1126自动分配超过2G

我不确定2G如何与255999996/7相关联。我谷歌了这两个数字,我能找到的唯一可能相关的是这个关于dc精度问题的*nix问答。不管怎样,你要填充哪种类型的int数组似乎并不重要,重要的是可以分配多少元素。

2. 运行时的限制

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

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

但如果我稍微调整一下……

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

砰!堆栈溢出!

在memchk.exe中的0x00007FF7DC6B1B38抛出异常:0xC00000FD: 堆栈溢出(参数:0x0000000000000001, 0x000000AA8DE03000)。 在memchk.exe中的0x00007FF7DC6B1B38未处理的异常: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;
}