QList的最大大小是多少？

Question

有人遇到QList的最大大小限制吗？

我有一个指向我的对象的指针的QList，发现当它达到第268,435,455个项目时会静默地抛出错误，这恰好是28位。我本来期望它至少具有31位的最大大小（减去一位，因为size()返回带符号整数），或者在我的64位计算机上具有63位的最大大小，但事实并非如此。通过在计数循环中执行QList<void*> mylist; mylist.append(0);的最小示例来确认了这一点。

换句话说，QList的实际最大大小是多少？如果它实际上不是2^32-1，那么为什么？是否有解决方法？

我正在运行Qt 4.8.5的MSVC2010 Windows 64位版本。

- Phlucious

---

评论不适合进行长时间的讨论；此对话已被移至聊天室。 - George Stocker

Answer 1

虽然其他答案试图解释这个问题，但它们没有回答问题或者错过了重点。感谢每个人帮助我追踪这个问题。

正如Ali Mofrad所提到的，当QList在QList::append(MyObject*)调用中无法分配额外空间时，抛出的错误是std::bad_alloc错误。以下是Qt源代码中发生这种情况的位置：

qlist.cpp: line 62:
static int grow(int size)         //size = 268435456
{
    //this is the problem line
    volatile int x = qAllocMore(size * sizeof(void *), QListData::DataHeaderSize) / sizeof(void *);
    return x;                     //x = -2147483648
}

qlist.cpp: line 231:
void **QListData::append(int n)   //n = 1
{
    Q_ASSERT(d->ref == 1);
    int e = d->end;
    if (e + n > d->alloc) {
        int b = d->begin;
        if (b - n >= 2 * d->alloc / 3) {
            //...
       } else {
            realloc(grow(d->alloc + n));    //<-- grow() is called here
        }
    }
    d->end = e + n;
    return d->array + e;
}

在grow()中，新请求的大小（268,435,456）乘以sizeof(void*)（8）来计算新内存块的大小，以容纳增长的QList。问题是，如果它是无符号int32，则268435456*8等于+2,147,483,648，如果是有符号int32，则为-2,147,483,648，这就是从我的操作系统返回grow()的内容。因此，在QListData::realloc(int)中调用std::realloc()时，我们试图扩展到负大小。

解决方法是使用ddriver建议的QList::reserve()预分配空间，防止我的QList不得不增长。

简而言之，QList的最大大小为2^28-1项，除非您预先分配空间，否则最大大小确实为2^31-1，如预期所示。

更新（2020年1月）：在Qt 5.5中，这似乎已经改变了，QList和QVector的最大大小现在为2 ^ 28-1，无论您是否事先保留。很遗憾。

- Phlucious

---

如果您错过了我的上一个评论，请考虑切换到QVector或std::vector，并将点保留在容器中，而不是动态分配它们并存储指向它们的指针，这样可以大大节省CPU时间和内存。此外，如果您确实需要继续添加点，则可以考虑使用自己的容器，并采用更为保守的增长策略。 - dtech

请注意，问题不在于乘法（sizeof返回一个size_t，在64位系统上将是一个64位整数），而是qAllocMore处理普通的整数。此外，在Qt 5中，该代码已经发生了重大变化。 - peppe

@peppe 很好的观察。我手头没有Qt5源代码。他们是否更改了QList和相关函数以使用quint64或size_t，就像应该做的那样？ - Phlucious

更新：我现在正在使用Qt 5.11.1，看起来它已经将大小限制硬编码为2^28-1项。当保留更大的尺寸时，QList::reserve（）会抛出badalloc错误。相关的代码已经被注释掉了，说明它是在Qt 5.7中添加的。我不知道这是否已经在更新版本中得到修复。 - Phlucious

Answer 2

有人遇到过QList的最大尺寸限制吗？我有一个指向我的对象的QList指针，发现当它达到第268,435,455个元素时会悄然抛出错误，这正是28位数。我本来期望它至少有31位的最大尺寸（减1位因为size()返回一个有符号整数），或者在64位电脑上有63位的最大尺寸，但事实似乎并非如此。

int中存储的理论最大正数为2^31 - 1，指针的大小为4字节（对于32位机器），因此可能的最大数量为2^29 - 1。将数据附加到容器中会增加堆内存的碎片化，因此可能只能分配一半可能的内存。尝试使用reserve()或resize()代替。

此外，Win32对内存分配有一些限制。因此，未经特殊设置的应用程序无法分配超过该限制（1G或2G）的内存。

您确定需要这么大的容器吗？优化应用程序是否更好？

- Sergey Belyashov

---

我点了个赞。OP也应该注意，在Qt容器中，代码不会在64位系统上获得63位，甚至是2^(63-3) -1 = 2^60-1。对于这些情况应该使用Std容器。Qt容器在这方面相当有限。这里有相关信息。还应该注意，内核和其他进程也需要内存。 - László Papp

大约1GB或2GB，这是真的。 - Ali Mofrad

Answer 3

QList将其元素存储在void *数组中。

因此，在32位机器上，具有2²⁸个项的列表，其中每个项都是void *，将占用2³⁰字节，在64位机器上将占用2³¹字节。我怀疑您是否可以请求如此大的连续内存块。

而为什么要分配如此巨大的列表呢？您确定您真的需要它吗？

---

被一个void*数组支持的想法是因为可以将列表上的几个操作移动到非模板化代码中，从而减少生成的代码量。

如果类型足够小（即sizeof(T) <= sizeof(void*)），并且如果可以通过memmove在内存中移动类型，则QList将项目直接存储在void*数组中。否则，每个项目将通过new在堆上分配，并且数组将存储对这些项目的指针。一组类型特征用于确定如何处理每种类型，请参见Q_DECLARE_TYPEINFO。

虽然从理论上讲，这种方法可能听起来很有吸引力，但在实践中：

• 对于所有比void *小的原始类型（char；64位上的int和float等），您会浪费分配的数组空间的50％至75％
• 对于所有大于void *的可移动类型（32位上的double，QVariant等），您需要为列表中的每个项目支付堆分配（加上数组本身）
• QList代码通常比QVector代码优化得少
• 编译器现在在合并模板实例方面做得相当不错，因此这种设计的最初原因被忽略了。

今天坚持使用QVector是一个更好的主意。不幸的是，Qt API无处不在地暴露了QList，并且不能更改它们（我们需要C ++ 11将QList定义为QVector的模板别名...）

- peppe

Answer 4

我在Ubuntu 32位系统下使用qt4.8.6进行测试，内存为4GB。对于我来说，最大尺寸为268,435,450。

我在Windows7 32位系统下使用qt4.8.4进行测试，内存为4GB。对于我来说，最大尺寸为134,217,722。

出现了这个错误：'std::bad_alloc'

#include <QCoreApplication>
#include <QDebug>

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    QList<bool> li;
    for(int i=0; ;i++)
    {
        li.append(true);
        if(i>268435449)
            qDebug()<<i;
    }
    return a.exec();
}

输出结果为：

268435450

调用std::bad_alloc实例后终止
what(): std::bad_alloc

- Ali Mofrad

---

64位Ubuntu 4 GB RAM Qt 5.3.2上经过268,435,453次后仍出现相同的异常。 - Simon Warta

虽然这很有用，但并没有回答问题：解决方法是什么，为什么会发生这种情况。请使用注释提供额外的信息。 - László Papp