QList 的工作原理和运行效率浅析

我们知道Qt为了在一些没有STL的环境中运作，开发了一套相对完整的容器。大部分Qt的容器我们都能够招到对应STL容器，例如QVector对应std::vector, QMap对应std::map，不过这其中也有一些特例，例如QList在STL中就没有应该的容器，std::list对应的Qt容器实际上是QLinkedList。所以在使用QList的时候请务必弄清楚这一点，否则可能会导致程序的运行效率的低下，让我们先看一份代码：

#include <benchmark/benchmark.h>
#include <qlist>
#include <qvector>

const std::string test_buffer{ "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" };
const int ITER_COUNTS = 10000000;

static void BM_QListPushString(benchmark::State& state) {
    QList<std::string> test_qlist;
    for (auto _ : state) {
        test_qlist.push_back(test_buffer);
    }
}
BENCHMARK(BM_QListPushString)->Iterations(ITER_COUNTS);

static void BM_QVectorPushString(benchmark::State& state) {
    QVector<std::string> test_qvector;
    for (auto _ : state) {
        test_qvector.push_back(test_buffer);
    }
}
BENCHMARK(BM_QVectorPushString)->Iterations(ITER_COUNTS);

static void BM_QListPushChar(benchmark::State& state) {
    QList<char> test_qlist;
    for (auto _ : state) {
        test_qlist.push_back('x');
    }
}
BENCHMARK(BM_QListPushChar)->Iterations(ITER_COUNTS);

static void BM_QVectorPushChar(benchmark::State& state) {
    QVector<char> test_qvector;
    for (auto _ : state) {
        test_qvector.push_back('x');
    }
}
BENCHMARK(BM_QVectorPushChar)->Iterations(ITER_COUNTS);

BENCHMARK_MAIN();

以上代码使用google benchmark统计QList和QVector的运行效率，代码采用的最简单的push_back函数测试两种容器对于小数据和相对较大数据的处理性能。结果如下：

Run on (8 X 3600 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB (x4)
  L1 Instruction 32 KiB (x4)
  L2 Unified 256 KiB (x4)
  L3 Unified 8192 KiB (x1)
-----------------------------------------------------------------------------------
Benchmark                                         Time             CPU   Iterations
-----------------------------------------------------------------------------------
BM_QListPushString/iterations:10000000          152 ns          150 ns     10000000
BM_QVectorPushString/iterations:10000000        102 ns          102 ns     10000000
BM_QListPushChar/iterations:10000000           12.2 ns         12.5 ns     10000000
BM_QVectorPushChar/iterations:10000000         4.92 ns         4.69 ns     10000000

可以发现QVector在两种情况下的性能都占优，尤其是PushChar的情况优势更加明显。原因就要从QList的原理说起了。前面说过QList并不是一个链表链接的结构，它的实际结构如下：

       QListData                                 +--------------------+
                                                 |                    |
+------------------------+                       |      obj buffer 1  |
|                        |                       |                    |
|      ptr to buffer 1   +----------------------->                    |
|                        |                       +--------------------+
+------------------------+
|                        |                       +--------------------+
|      ptr to buffer 2   |                       |                    |
|                        +----------------------->      obj buffer 2  |
+------------------------+                       |                    |
|                        |                       |                    |
|           .            |                       +--------------------+
|           .            |
|           .            |
|                        |
+------------------------+
|                        |                       +--------------------+
|                        |                       |                    |
|      ptr to buffer N   +----------------------->                    |
|                        |                       |      obj buffer N  |
+------------------------+                       |                    |
                                                 +--------------------+

它的内部维护了一个指针（void*）的数组，该数组指向了真正的对象，它就像是一个vector和list的结合体一样。在对象占用内存大的时候（大于sizeof(void*)），它每次会从堆中分配内存。然后将内存的起始地址放入数组中。相对于QVector慢的原因是它每次都要经过堆分配内存，而QVector可以预分配内存从而提高push_back的运行效率。而对于小内存对象，他直接将其存储到数组中，这样不需要经过堆分配内存，所以相对于大内存QList本身也有很大的性能提升，但是由于它每次需要用到sizeof(void*)的内存，也会导致更多的内存分配，所以运行效率还是不如QVector。

当然，QList也有自己的优势，例如当对占用大内存对象进行重新排续的时候，QVector只能进行大量内存移动，而QList则只需要移动对象指针即可。相对于std::list，QList在单纯的push_back和枚举的时候也有不错的表现。