RobbEr's Blog

Welcome

Qt-QVarLengthArray

发表于 更新于 分类于 ， 阅读次数： Valine：
本文字数： 3.8k 阅读时长 ≈ 3 分钟

引入

C++语言不支持栈Stack (此处出现的堆栈为操作系统的堆栈) 上的可变长度数组：

1
2
3
4
5
int fun1(unsigned n)
{
    int arr[n + 1];   // 错误！
    ...
}

还有一种办法则是在堆Heap上构建：

1
2
3
4
5
6
int fun2(unsigned n)
{
    int *arr = new int[n + 1];    // 可行
    ...
    delete arr;
}

但如果频繁调用fun2则会出现由于堆分配带来的效率问题。

C++11虽然引入了std::array用作传统构建在栈上的C数组的替代。但std::array依旧是定长数组。

QVarLengthArray试图解决这一C++难题。他在栈上分配一定数量元素，当试图调整其内部元素数量为更大时，它会自动使用在堆上分配。

详解

简而言之，QVarLengthArray是一个栈数组与堆数组的结合：

  • 初始给定大小，创建栈数组；
  • 当添加元素大于栈数组大小时，创建堆数组，并把栈数组内容复制到堆数组上；
  • 加快创建速度，适用于高频率使用数组的代码中；

示例

1
2
3
4
5
6
int myfunc(int n)
{
    QVarLengthArray<int, 1024> array(n + 1);
    ...
    return array[n];
}

在上面的例子中，QVarLengthArray将在堆栈上预分配1024个元素，并使用它们，除非n + 1大于1024。如果省略第二个模板参数，则使用QVarLengthArray的默认值256。

源码解析

QVarLengthArray的接口更为底层，缺少一些QList的功能，这里先看一下私有成员：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class QVarLengthArray
{
    ...
private:
    void realloc(int size, int alloc);
    int a;      // capacity
    int s;      // size
    T *ptr;     // data
    union {
        char array[Prealloc * sizeof(T)];
        qint64 q_for_alignment_1;
        double q_for_alignment_2;
    };
}

首先成员变量：

  • a为容量；
  • s为数组大小；
  • ptr为创建在堆上的数组指针；
  • 联合体中array为创建在栈上的数组，另外两个则是为了内存对齐锁创建的对象；

这里着重看一下realloc函数(此处为Qt5.7.1源码)，此函数为在栈及堆上可变长度数组的实现关键：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
template <class T, int Prealloc>
Q_OUTOFLINE_TEMPLATE void QVarLengthArray<T, Prealloc>::realloc(int asize, int aalloc)
{
    Q_ASSERT(aalloc >= asize);
    T *oldPtr = ptr;
    int osize = s;
    const int copySize = qMin(asize, osize);
    Q_ASSUME(copySize >= 0);
    if (aalloc != a)
    {
        if (aalloc > Prealloc)
        {
            T* newPtr = reinterpret_cast<T *>(malloc(aalloc * sizeof(T)));
            Q_CHECK_PTR(newPtr); // 可以抛出异常
            // 按设计：在QT_NO_EXCEPTIONS的情况下，malloc不能失败，否则在此处崩溃
            ptr = newPtr;
            a = aalloc;
        }
        else
        {
            ptr = reinterpret_cast<T *>(array);
            a = Prealloc;
        }
        s = 0;
        /* 新版Qt使用!QTypeInfoQuery<T>::isRelocatable，其定义：
        struct QTypeInfoQuery : public QTypeInfo<T>
        {
            enum { isRelocatable = !QTypeInfo<T>::isStatic };
        };
        即与isStatic相反 */
        if (QTypeInfo<T>::isStatic)
        {
            // 即try
            QT_TRY 
            {
                // 复制所有旧元素
                while (s < copySize) 
                {
                    // 在新版Qt中使用T(std::move(*(oldPtr+s)))调用移动构造函数
                    new (ptr+s) T((*(oldPtr+s)));
                    (oldPtr+s)->~T();
                    s++;
                }
            }
            // 即catch
            QT_CATCH(...)
            {
                int sClean = s;
                while (sClean < osize)
                    (oldPtr+(sClean++))->~T();
                if (oldPtr != reinterpret_cast<T *>(array) && oldPtr != ptr)
                    free(oldPtr);
                QT_RETHROW;
            }
        }
        else
        {
            memcpy(static_cast<void *>(ptr), static_cast<const void *>(oldPtr), copySize * sizeof(T));
        }
    }
    s = copySize;
    if (QTypeInfo<T>::isComplex) 
    {
        // destroy remaining old objects
        while (osize > asize)
            (oldPtr+(--osize))->~T();
    }
    if (oldPtr != reinterpret_cast<T *>(array) && oldPtr != ptr)
        free(oldPtr);
    if (QTypeInfo<T>::isComplex)
    {
        // 调用默认构造函数，可能抛出异常
        while (s < asize)
            new (ptr+(s++)) T;
    }
    else
    {
        s = asize;
    }
}

首先，函数声明：

  1. 第一行：template <class T, int Prealloc>为模板参数，T为数组元素类型，Prealloc为初始分配在栈上的数组的大小。
  2. 第二行：Q_OUTOFLINE_TEMPLATE为针对编译器的内联优化建议，asize为数组大小，aalloc为容量。

其次，函数部分：

  • Q_ASSERT(aalloc >= asize)判断参数是否传入出错；
  • const int copySize = qMin(asize, osize)获取需要复制的元素长度；
    -Q_ASSUME(copySize >= 0)为断言和建议编译器优化宏；
  • if (aalloc != a)则是判断是否与之前的容量相等，不相等则重新创建数组；进入if作用域：
    • if (aalloc > Prealloc)判断新容量是否大于之前分配在栈上的容量，是则重新在堆上创建aalloc*sizeof(T)大小的数组，否则直接将Prealloc设置为aalloc；
    • 之后设置数组大小为0，拷贝旧元素到新数组中，完成一个拷贝后将数组大小加一；
    • if (QTypeInfo<T>::isStatic)此处的QTypeInfo<T>::isStatic是一个编译时常量，如果需要使用复制构造函数重新迁移T类型的对象，则该常量的值为true，如果可以改用memcpy，则该值为false。之后则是进行复制，如果需要使用构造函数则调用构造函数进行新元素的拷贝(新版Qt为移动)构造并调用旧元素的析构函数进行析构，当出现错误时清理所有依旧完成拷贝的旧元素和释放旧指针并继续向外层抛出异常；如果支持memcpy则直接进行内存的拷贝。
  • s = copySize设置数组大小为拷贝的元素数量；
  • if (QTypeInfo<T>::isComplex)此处的QTypeInfo<T>::isComplex也是一个编译时常量，如果需要运行T类型的构造函数和析构函数，它的计算结果为true，如果不需要，则为false。即此处if语句作用域继续析构剩余的旧元素；
  • if (oldPtr != reinterpret_cast<T *>(array) && oldPtr != ptr)判断指针是否为同一个，不是则释放旧指针；
  • 最后一个if (QTypeInfo<T>::isComplex)则是与之前同理，如果需要运行构造函数则调用新元素的构造函数进行构造或直接设置数组大小为asize。