使用Qt这么多年，一直有一个疑问：为什么需要“一批”输入/输出参数时，大量的Qt接口以QList作为参数形式，而不是QVector？

0. 缘起

vector（向量）和list（链表）作为常见的容器，使用方式非常类似，但是针对不同场景存在一些性能上的区别：

（参考资料：https://en.cppreference.com/w/cpp/container/vector、https://en.cppreference.com/w/cpp/container/list）

由此可以得出以下结论：

• 在更关心访问效率，而不关心插入/删除效率时，使用vector；在更关心插入/删除效率，而不关心访问效率时，使用list。
• 对于主要在尾部执行插入/移除操作的情况，如果总体数据量不大（不太需要重新分配内存），vector总体性能上也不会比list差太多；即使是大数据量，如果总体数据量可以估计，那么完全可以预先分配足够的内存，这样就避免了大多数需要重新分配内存的情况，从而节省性能开销。

这么看来，除非存在大量非尾的插入/删除操作，vector都应该是首选。

1.  Qt的首选不是vector？

在Qt5中，也有两个容器类QVector和QList，很容易联想到这两个容器类与STL中两个相近命名的容器类的对应关系。既是如此，按照上面的推演分析，应该有大量的Qt接口使用QVector作为参数和返回的形式。然而在Qt的各种API中，使用得更多的反而是QList，甚至在很多显然更应该倾向查询性能的接口中也是如此，却是为何？

几乎随处可见。那岂不是完蛋了，这样的性能谁敢用啊？

2. 解析

重新审视前面的整个推理链条，发现了一个漏洞：单纯因为QList与list命名相似，就认为QList应当具备list所有的优势与劣势。

Qt官方文档关于QList的介绍开篇名义：

QList<T> is one of Qt's generic container classes. It stores items in a list that provides fast index-based access and index-based insertions and removals.

这里说QList将对象存储在一个list中，并且提供了基于索引的访问、插入和删除。既然基于索引了，那它就不是一个简单的链表！

Internally, QList<T> is represented as an array of T if sizeof(T) <= sizeof(void*) and T has been declared to be either a Q_MOVABLE_TYPE or a Q_PRIMITIVE_TYPE using Q_DECLARE_TYPEINFO. Otherwise, QList<T> is represented as an array of T* and the items are allocated on the heap.

The array representation allows very fast insertions and index-based access. The prepend() and append() operations are also very fast because QList preallocates memory at both ends of its internal array. (See Algorithmic Complexity for details.

QList的内部实现，不管sizeof(T)  <= sizeof(void*)是否成立，都是一个array（数组）。如果size小于等于指针，那么它是一个T的数组，否则是一个指针数组。这也就解释了为什么它可以提供基于索引的操作，它内部可是个数组啊。这里还有个高级操作，QList在其内部数组的两端都做了预分配内存，所以插头插尾都能非常快。多说无益，来看源码。（Qt版本5.5.0）

2.1 访问操作的解析

// qlist.h
template <typename T>
inline const T &QList::at(int i) const
{ Q_ASSERT_X(i >= 0 && i < p.size(), "QList::at", "index out of range");
return reinterpret_cast(p.at(i))->t(); }
inline const T &QList::operator[](int i) const
{ Q_ASSERT_X(i >= 0 && i < p.size(), "QList::operator[]", "index out of range");
 return reinterpret_cast(p.at(i))->t(); }
template 
inline T &QList::operator[](int i)
{ Q_ASSERT_X(i >= 0 && i < p.size(), "QList::operator[]", "index out of range");
  detach(); return reinterpret_cast(p.at(i))->t(); }

可以看到，不管是[]运算符还是at函数，都是通过p.at()实现的。

// qlist.h
class QList : public QListSpecialMethods<T>
{
public:
    // ...
private:
    // ...
    union { QListData p; QListData::Data *d; };
    // ...
}

这是p的定义，p是QListData的一个实例。

// qlist.h
struct Q_CORE_EXPORT QListData {
    // ...
    struct Data {
        QtPrivate::RefCount ref;
        int alloc, begin, end;
        void *array[1];
    };
    // ...
    Data *d;
    // ...
    inline void **at(int i) const { return d->array + d->begin + i; }
    // ...
};

这是QListData::at的定义，以及它需要用到的成员变量d的定义。从这里可以看出，数据在内存中的实际位置，是计算出来的。

2.2 尾追加(append)操作的解析

// qlist.h
template <typename T>
class QList : public QListSpecialMethods
{
// ...
    // stl compatibility
    inline void push_back(const T &t) { append(t); }
// ...
}

这是QList::push_back的实现，显然它相当于append的别名函数。

// qlist.h
template <typename T>
Q_OUTOFLINE_TEMPLATE void QList<T>::append(const T &t)
{
    if (d->ref.isShared()) {
        Node *n = detach_helper_grow(INT_MAX, 1);
        QT_TRY {
            node_construct(n, t);
        } QT_CATCH(...) {
            --d->end;
            QT_RETHROW;
        }
    } else {
        if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
            Node *n = reinterpret_cast<Node *>(p.append());
            QT_TRY {
                node_construct(n, t);
            } QT_CATCH(...) {
                --d->end;
                QT_RETHROW;
            }
        } else {
            Node *n, copy;
            node_construct(&copy, t); // t might be a reference to an object in the array
            QT_TRY {
                n = reinterpret_cast<Node *>(p.append());;
            } QT_CATCH(...) {
                node_destruct(&copy);
                QT_RETHROW;
            }
            *n = copy;
        }
    }
}

这是QList::append的实现。不管走到哪个分支，都走了先分配地址（Node *n = reinterpret_cast<Node *>(p.append())），再创建node（node_construct(node*, t)）的流程。其中if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic)这个分支通过判断sizeof(T)与size(void*)的大小，来决定实际数据格式（T或者T*）。

// qlist.cpp
// ensures that enough space is available to append n elements
void **QListData::append(int n)
{
    Q_ASSERT(!d->ref.isShared());
    int e = d->end;
    if (e + n > d->alloc) {
        int b = d->begin;
        if (b - n >= 2 * d->alloc / 3) {
            // we have enough space. Just not at the end -> move it.
            e -= b;
            ::memcpy(d->array, d->array + b, e * sizeof(void *));
            d->begin = 0;
        } else {
            realloc(grow(d->alloc + n));
        }
    }
    d->end = e + n;
    return d->array + e;
}

// ensures that enough space is available to append one element
void **QListData::append()
{
    return append(1);
}

这是QListData::append的实现。该函数确保实际分配的内存空间足够（可能需要调整内存分布或者重新分配内存），并返回一个用于构造node的地址。可能出现以下几种情况：

• 当append将写入的地址不超过当前的尾部，直接计算出一个node地址；
• 当append将写入的地址，超过了当前的尾部（e + n > d->alloc），但是已分配的总内存空间足够（b - n >= 2 * d->alloc / 3），则先做内部调整（::memcpy(d->array, d->array + b, e * sizeof(void *))），再计算node地址；
• 当append将写入的地址，且需要使用的总内存也超过了当前已分配的内存，则需要重新分配内存（grow(d->alloc + n)），再计算node地址。

2.3 头追加(prepend)操作的解析

// qlist.h
template <typename T>
class QList : public QListSpecialMethods<T>
{
// ...
    // stl compatibility
    inline void push_front(const T &t) { prepend(t); }
// ...
};

这是QList::push_front的实现，它是prepend的别名函数。

// qlist.h
template <typename T>
inline void QList::prepend(const T &t)
{
    if (d->ref.isShared()) {
        Node *n = detach_helper_grow(0, 1);
        QT_TRY {
            node_construct(n, t);
        } QT_CATCH(...) {
            ++d->begin;
            QT_RETHROW;
        }
    } else {
        if (QTypeInfo::isLarge || QTypeInfo::isStatic) {
            Node *n = reinterpret_cast(p.prepend());
            QT_TRY {
                node_construct(n, t);
            } QT_CATCH(...) {
                ++d->begin;
                QT_RETHROW;
            }
        } else {
            Node *n, copy;
            node_construct(&copy, t); // t might be a reference to an object in the array
            QT_TRY {
                n = reinterpret_cast(p.prepend());;
            } QT_CATCH(...) {
                node_destruct(&copy);
                QT_RETHROW;
            }
            *n = copy;
        }
    }
}

这是QList::prepend的实现，最后几个分支都走到同一个函数p.prepend()。

// qlist.cpp
void **QListData::prepend()
{
    Q_ASSERT(!d->ref.isShared());
    if (d->begin == 0) {
        if (d->end >= d->alloc / 3)
            realloc(grow(d->alloc + 1));

        if (d->end < d->alloc / 3)
            d->begin = d->alloc - 2 * d->end;
        else
            d->begin = d->alloc - d->end;

        ::memmove(d->array + d->begin, d->array, d->end * sizeof(void *));
        d->end += d->begin;
    }
    return d->array + --d->begin;
}

这是QLiatData::prepend的实现。该函数确保实际内存大小足够（可能需要调整内存分布或者重新分配内存），并返回一个用于构造node的地址。可能出现以下几种情况：

• 当prepend将写入的地址不超过当前的头部，直接计算出一个node地址；
• 当prepend将写入的地址，超过了当前的头部（d->begin == 0），且需要使用的总内存也超过了当前已分配的内存（d->end >= d->alloc / 3），则需要重新分配内存（grow(d->alloc + 1)），再计算node地址。
• 当prepend将写入的地址，超过了当前的头部（d->begin == 0），但是已分配的总内存空间足够，则先做内部调整（::memmove(d->array + d->begin, d->array, d->end * sizeof(void *))），再计算node地址。

2.4 随机插入(insert)操作的解析

// qlist.h
template <typename T>
inline void QList<T>::insert(int i, const T &t)
{
    if (d->ref.isShared()) {
        Node *n = detach_helper_grow(i, 1);
        QT_TRY {
            node_construct(n, t);
        } QT_CATCH(...) {
            p.remove(i);
            QT_RETHROW;
        }
    } else {
        if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
            Node *n = reinterpret_cast<Node *>(p.insert(i));
            QT_TRY {
                node_construct(n, t);
            } QT_CATCH(...) {
                p.remove(i);
                QT_RETHROW;
            }
        } else {
            Node *n, copy;
            node_construct(&copy, t); // t might be a reference to an object in the array
            QT_TRY {
                n = reinterpret_cast<Node *>(p.insert(i));;
            } QT_CATCH(...) {
                node_destruct(&copy);
                QT_RETHROW;
            }
            *n = copy;
        }
    }
}

这是QList::insert的实现，最后几个分支都走到同一个函数p.insert(int)。

// qlist.cpp
void **QListData::insert(int i)
{
    Q_ASSERT(!d->ref.isShared());
    if (i <= 0)
        return prepend();
    int size = d->end - d->begin;
    if (i >= size)
        return append();

    bool leftward = false;

    if (d->begin == 0) {
        if (d->end == d->alloc) {
            // If the array is full, we expand it and move some items rightward
            realloc(grow(d->alloc + 1));
        } else {
            // If there is free space at the end of the array, we move some items rightward
        }
    } else {
        if (d->end == d->alloc) {
            // If there is free space at the beginning of the array, we move some items leftward
            leftward = true;
        } else {
            // If there is free space at both ends, we move as few items as possible
            leftward = (i < size - i);
        }
    }

    if (leftward) {
        --d->begin;
        ::memmove(d->array + d->begin, d->array + d->begin + 1, i * sizeof(void *));
    } else {
        ::memmove(d->array + d->begin + i + 1, d->array + d->begin + i,
                  (size - i) * sizeof(void *));
        ++d->end;
    }
    return d->array + d->begin + i;
}

这是QLiatData::insert的实现。该函数确保实际内存大小足够（可能需要调整内存分布或者重新分配内存），并返回一个用于构造node的地址。可能出现以下几种情况：

• 当insert将写入的位置超过当前有效尾部时，直接调用append()；
• 当insert将写入的位置超过当前有效头部时，直接调用prepend()；
• 当需要使用的总内存超过了当前已分配的内存（d->begin == 0 && d->end == d->alloc），则需要重新分配内存（grow(d->alloc + 1)），再计算node地址。
• 调用::memmove实现内存移动，优先选择向尾部方向移动；如果已到达缓存末端，则向前移动。

2.5 删除(erase)操作的解析

// qlist.h
template <typename T>
inline typename QList<T>::iterator QList<T>::erase(iterator it)
{
    Q_ASSERT_X(isValidIterator(it), "QList::erase", "The specified iterator argument 'it' is invalid");
    if (d->ref.isShared()) {
        int offset = int(it.i - reinterpret_cast<Node *>(p.begin()));
        it = begin(); // implies detach()
        it += offset;
    }
    node_destruct(it.i);
    return reinterpret_cast<Node *>(p.erase(reinterpret_cast<void**>(it.i)));
}

这是QList::erase的实现，最后走到函数p.erase(int)。

// qlist.cpp
void **QListData::erase(void **xi)
{
    Q_ASSERT(!d->ref.isShared());
    int i = xi - (d->array + d->begin);
    remove(i);
    return d->array + d->begin + i;
}

这是QLiatData::erase的实现，最后走到了remove(int)。

// qlist.h
template <typename T>
Q_OUTOFLINE_TEMPLATE typename QList<T>::iterator QList<T>::erase(typename QList<T>::iterator afirst,
                                                                 typename QList<T>::iterator alast)
{
    Q_ASSERT_X(isValidIterator(afirst), "QList::erase", "The specified iterator argument 'afirst' is invalid");
    Q_ASSERT_X(isValidIterator(alast), "QList::erase", "The specified iterator argument 'alast' is invalid");

    if (d->ref.isShared()) {
        // ### A block is erased and a detach is needed. We should shrink and only copy relevant items.
        int offsetfirst = int(afirst.i - reinterpret_cast<Node *>(p.begin()));
        int offsetlast = int(alast.i - reinterpret_cast<Node *>(p.begin()));
        afirst = begin(); // implies detach()
        alast = afirst;
        afirst += offsetfirst;
        alast += offsetlast;
    }

    for (Node *n = afirst.i; n < alast.i; ++n)
        node_destruct(n);
    int idx = afirst - begin();
    p.remove(idx, alast - afirst);
    return begin() + idx;
}

这是QList::erase的另一种实现，最后走到函数p.remove(int, int)。

// qlist.cpp
void QListData::remove(int i)
{
    Q_ASSERT(!d->ref.isShared());
    i += d->begin;
    if (i - d->begin < d->end - i) {
        if (int offset = i - d->begin)
            ::memmove(d->array + d->begin + 1, d->array + d->begin, offset * sizeof(void *));
        d->begin++;
    } else {
        if (int offset = d->end - i - 1)
            ::memmove(d->array + i, d->array + i + 1, offset * sizeof(void *));
        d->end--;
    }
}

void QListData::remove(int i, int n)
{
    Q_ASSERT(!d->ref.isShared());
    i += d->begin;
    int middle = i + n/2;
    if (middle - d->begin < d->end - middle) {
        ::memmove(d->array + d->begin + n, d->array + d->begin,
                   (i - d->begin) * sizeof(void*));
        d->begin += n;
    } else {
        ::memmove(d->array + i, d->array + i + n,
                   (d->end - i - n) * sizeof(void*));
        d->end -= n;
    }
}

这是QLiatData::remove的实现，向前执行memmove安全地覆盖不需要的数据，并重新标记头部或尾部。

// qlist.h
template <typename T>
class QList : public QListSpecialMethods<T>
{
// ...
    inline void removeFirst() { Q_ASSERT(!isEmpty()); erase(begin()); }
    inline void removeLast() { Q_ASSERT(!isEmpty()); erase(--end()); }
// ...
};

此外，还有几个方便接口，也是调用erase实现的。

3. 结论

• QList是一个使用动态数组实现的类似list的容器类，但是它不是list的Qt实现。
• QList没有实现list（链表）的next和last功能。
• QList的随机访问很快，可以认为与数组的随机访问相当（只多了计算数据真实内存地址的开销）。
• 在大多数情况下，QList的头尾位置的追加删除都非常快，只有在预分配内存不足的情况下，需要重新分配内存和拷贝数据。
• 在非头尾位置的插入删除会发生内存拷贝，但是对于大数据结构（sizeof(T) > sizeof(int)），在数组内保存的是一个void*，不需要对数据结构本身做析构和构造，内存拷贝量不超过4 * 整体长度，总体上也比简单数组要快很多。

可以认为QList是一个升级版的QVector。在大多数情况下，性能并不比QVector差，放心大胆地用吧！

4. 不用纠结了

后来我在QList官方介绍页面发现了一个更详细的链接（ Pros and Cons of Using QList ），摘录其中一个表说明所有问题：

这个表里把Qt和STL的容器类做了个类比，存在对应关系的列在同一行。QList不跟STL任何一个对应，与list对应的是QLinkedList。

二零二四年七月二十八日 顾毅写于厦门