Qt Container

1. Qt Container

1. Qt Container

1.1. Overview

Qt 的 container 与 Rust Box 类似, 它们本身只是一个 wrapper, 真正的数据是在堆上分配的.

这种 wrapper 有两个好处:

shadow copy, 复制一个 container 的开销很小
copy on write, 只在需要的时候才 copy 堆上的数据

每种 container 底层都有一个 XxxData 代表堆上数据, 同时包含引用计数负责堆上数据的释放, 另外, 对于所有可能修改堆上数据的操作, 都会通过 detach 触发 copy on write

1.1.1. shadow copy

// case 1:
QVector<int> data {1, 2, 3};
auto data2 = data;

// case 2:
QVector<int> getData() {
    return QVector<int> {1, 2, 3};
}
auto data = getData();

// case 3:
void check(QVector<int> data) {}
check(QVector<int> {1, 2, 3})

上面三种情况下, data 都是 shadow copy, 其底层的 QTypedArrayData 会指向相同的堆上数据

QVector<int> data {1, 2, 3};
printf("%p\n", &data[0]);

const auto data2 = data;
printf("%p\n", &data2[0]);

// 输出为:
// 0x1191e68
// 0x1191e68

1.1.2. copy on write

int main(int argc, char *argv[]) {
    QVector<int> data {1, 2, 3};
    printf("%p\n", &data[0]);

    auto data2 = data;
    printf("%p\n", &data2[0]);

    return 0;
}

// 输出为:
// 0x1219e68
// 0x1219e98

虽然 data2 并没有显式的修改数据, 但从 qt 看来, 还是有可能发生潜在的 write: 因为 data2 通过 operator[] 返回了堆上数据的引用, 为了防止代码在别处修改这个引用的数据导致的 write, qt 会针对非 const 的 operator[] 进行 copy

1.2. shadow copy

template <typename T>
inline QVector<T>::QVector(const QVector<T> &v)
{
    // 若 ref() 为 true, 表示 v 是 shareable 的, 则通过
    // ref() inc 引用计数后, 直接让 this.d = v.d 即可,
    // 其中 d 即堆上的 QTypedArrayData
    if (v.d->ref.ref()) {
        d = v.d;
    } else {
        if (v.d->capacityReserved) {
            d = Data::allocate(v.d->alloc);
            Q_CHECK_PTR(d);
            d->capacityReserved = true;
        } else {
            // d 是在堆上分配的
            d = Data::allocate(v.d->size);
            Q_CHECK_PTR(d);
        }
        if (d->alloc) {
            copyConstruct(v.d->begin(), v.d->end(), d->begin());
            d->size = v.d->size;
        }
    }
}

shadow copy 是通过 RefCount 实现的, 和 c++ 的 shared_ptr 类似.

1.2.1. setSharable

默认情况下 container 都是 shareable 的, 拷贝构造函数会是 shadow copy. 通过 setSharable(false), 可以阻止这种行为.

1.3. copy on write

根据 RefCount 决定是否需要通过 detach 进行 copy
针对所有可能修改对象的方法进行 copy on write, 包括显式的 remove, insert 等操作, operator [] 也有可能导致 detach. 理论上, 所有非 const 方法都应该 detach

1.3.1. removeLast

template <typename T>
void QVector<T>::removeLast()
{
    if (d->ref.isShared())
        detach();
    --d->size;
    if (QTypeInfo<T>::isComplex)
        (d->data() + d->size)->~T();
}

detach 会负责:

将原始的 d deref, 即减小原来对象的引用计数
通过 realloc 分配新的内存, 复制旧对象的所有数据(而非仅仅是修改的数据)

1.3.2. operatror []

operator [] 会导致 detach:

inline T &QVector<T>::operator[](int i) {
    return data()[i];
}

inline T *data() { detach(); return d->begin(); }

const operator [] 并不需要 detach:

template <typename T>
inline const T &QVector<T>::operator[](int i) const {
    return d->begin()[i];
}

1.4. detach 导致的问题

1.4.1. 隐含的 detach

int main(int argc, char *argv[]) {
    QVector<int> data {1, 2, 3};
    printf("%p\n", &data[0]);

    auto dataCopy = data;
    for (int &i : dataCopy) {
        printf("%p\n", &i);
    }
    return 0;
}

// 0x14f3e68
// -------
// 0x14f3e98
// 0x14f3e9c
// 0x14f3ea0
// 因为 dataCopy 进行遍历时, 隐含的使用了 dataCopy.begin() 方法,
// 而非 const 的 iterator 会隐含着 detach

为避免隐含的 detach, 应尽量使用 const 对象

1.4.2. 修改的不一致

QVector<int> data{1, 2, 3};
int &first = data[0];

auto data2 = data;
first = 2;

foreach(int i, data2) {
    printf("%d\n", i);
}
// 2
// 2
// 3
// 
// 虽然 data2 可以透明的看作是 data 的 deep copy, 但其 data2[0] 还是被修改了

之所以发生问题, 是因为 qt 无法针对 first = 2 这种操作自动 detach

1.5. foreach

1.5.1. foreach 宏会隐式的在 data 的 copy 上迭代:

QVector<int> data{1, 2};
data.reserve(100);

for(int &i : data) {
    printf("%p %d\n", &i, i);
}
printf("---\n");
// foreach 会隐式在 data 的 copy 上迭代
// 所以 foreach 里可以自由的修改 data, 而且修改会导致 detach
foreach (int i, data) {
    data.insert(0, i);
}

for(int &i : data) {
    printf("%p %d\n", &i, i);
}

printf("---\n");

// range-based loop 并不会对 data 做 copy, 本质上它是基于 iterator 的, 它对 data 修改是不可预测的
for(int &i : data) {
    data.insert(0, i);
}

for(int &i : data) {
    printf("%p %d\n", &i, i);
}
// 0xd90438 1
// 0xd9043c 2
// ---
// 0xd79e68 2
// 0xd79e6c 1
// 0xd79e70 1
// 0xd79e74 2
// ---
// 0xd79e68 2
// 0xd79e6c 2
// 0xd79e70 2
// 0xd79e74 2
// 0xd79e78 2
// 0xd79e7c 1
// 0xd79e80 1
// 0xd79e84 2

1.5.2. foreach 在 data 的 const copy 上迭代

由于 foreach 操作的实际是原数据的 copy, 所以修改 iterator 是没有意义的, 因此, 这里的 copy 实际上是 const copy

foreach (int &i, data) {
    i += 1;
}
// /home/ANT.AMAZON.COM/waysun/program/qt/5.14.0/gcc_64/include/QtCore/qglobal.h:1110:34: error: binding ‘const int’ to reference of type ‘int&’ discards qualifiers
//      for (variable = *_container_.i; _container_.control; _container_.control = 0)

这里的 i 是 const int, 无法被修改

1.6. c++ range-based for loop

range-based for 是通过 iterator 直接操作数据:

不需要 copy
可以修改 iterator
不可以修改 container
begin() 会隐含一个 detach

QVector<int> data{1, 2, 3};
for(int &i : data) {
    printf("%p %d\n", &i, i);
}
printf("---\n");
auto data2 = data;
for(const int &i : qAsConst(data2)) {
    printf("%p %d\n", &i, i);
}
printf("---\n");
for(int &i : data2) {
    printf("%p %d\n", &i, i);
}
printf("---\n");
for(int &i : data2) {
    i += 1;
}
for(int &i : data2) {
    printf("%p %d\n", &i, i);
}
// 0x65ee68 1
// 0x65ee6c 2
// 0x65ee70 3
// ---
// 0x65ee68 1
// 0x65ee6c 2
// 0x65ee70 3
// ---
// 0x65ee98 1
// 0x65ee9c 2
// 0x65eea0 3
// ---
// 0x65ee98 2
// 0x65ee9c 3
// 0x65eea0 4

1.7. foreach 与 for(;) 的比较

foreach 会复制, 可以修改原 container, 由于使用了 const copy, 所以 iterator 不能修改, 但 iterator 也不会导致 detach
ranged-based for 不复制, 不可以修改原 container, 由于使用了 iterator, 所以 iterator 可以修改, 但 iterator 也会导致 detach
foreach (QPair<int,int> p, list) 无法编译通过, 因为宏无法自理多余的 `,`
foreach 隐含的复制行为, 可以会引起不注意的 bug
for(;) 虽然会导致 detach, 但通过 qAsConst 可以避免
foreach 已经 deprecated

1.8. Recap

通过 setSharable 可以控制是否使用 implicit sharing
由于 container 使用 RefCount 实现了 shadow copy 和 copy on write, 通常不再需要在堆上分配 Container, 直接在栈上分配即可. qt 保证了底层数据是在堆上分配的
使用 const 对象或 qAsConst 避免隐含的 detach
foreach 与 for(;) 的区别