QList、QLinkedList、QVector类

QList 是提供列表的一个模板类。它不是在连续内存空间存储，而是以数组列表（array-list）形式实现，并基于索引访问（index-based），同时，它插入和删除元素比较快（constant time）。

可用运算符<< 、append()、prepend()进行添加元素，insert()进行插入。QList维护了一个指针数组，数组元素指向每一个链表项，因此QList 提供了基于下标的快速访问。 

QList list; 
list << "caterpillar"  << "momor"  << "bush" ; 
     
QListIterator iterator(list); 
while (iterator.hasNext()) { 
     cout << iterator.next().toAscii().data() << endl;
}


QList list2;
list2 <<12  << 13 << 16 <<10;
qSort(list2.begin(), list2.end());

针对不同的元素，QList 有两种方式存储元素：

• 第一种是当“元素的占用空间”<=“指针占用的空间”，即 sizeof(T) <= sizeof(void*)，并且元素已经使用 Q_DECLARE_TYPEINFO 声明为 Q_MOVABLE_TYPE 或 Q_PRIMITIVE_TYPE 时，那么 QList 存储方式和 QVector、QVarLengthArray一样，都是以数组的形式存储，即 QList 表示为 T 的数组。这时候就和 C 兼容，参考“什么是 POD？”；
• 另一种是当“元素的占用空间”>“指针占用的空间”，那么 QList 会给每一个元素 new 到堆上，即 QList 表示为 QList 的数组；

所以第一种 QList 要比第二种 QList 访问起来更快。由于 QList 在内部已经为数组的两端预留了内存空间，所以第一种 QList 执行 prepend() 和 append() 操作会非常快。第二种 QList 执行这俩操作时，每加入一个元素就会在堆上分配一次，所以会慢点。

QList 容器在其生命周期内只会变大不会缩小，只有分配给另一个 QList 时析构函数和赋值运算符才会释放多余的空间。

QLinkedList 是QT的一个通用容器类，是一个是双向链表，以非连续内存块保存数据。QLinkedList< T>不能使用下标，只能使用迭代器访问它的数据项，它插入和删除元素比较快。

    LinkedList list;
    list << "caterpillar"  << "momor"  << "bush" ;

    QMutableLinkedListIterator rwIterator(list); // 允许遍历并修改list
    while (rwIterator.hasNext())
    {
        if (rwIterator.next() == "momor" )
        {   rwIterator.insert( "bee" );  
            break ; 
        }
    } 

    QLinkedListIterator rIterator(list); // 允许遍历,但不能修改list
    while (rIterator.hasNext()) 
    {
        cout << rIterator.next().toAscii().data() << endl;
    } 

QVector 是QT的一个通用容器类，它在相邻的内存位置中存储items的值，并且提供基于索引（index-based）的快速访问。如果你添加元素，但是vector的容量不够的话，系统就会重新分配一段内存，然后把原先的内容全部拷贝过去，然后删除原先的内容。

QVector< double > vect(2); 
vect[0] = 1.0; 
vect[1] = 2.0; 
for  ( int  i = 0; i < vect.count(); ++i) {
     cout << vect[i] << endl; 
} 

三种容器的时间复杂度如下

• 对于大多数用途,QList是首选。它的基于索引的API比QLinkedList基于迭代器的API更方便,并且通常比QVector将其项目存储在内存中的速度更快.它还扩展到可执行文件中较少的代码.
• 如果需要一个真实的链表,保证在列表中间插入常量时间,并将迭代器设置为项而不是索引,请使用QLinkedList.
• 如果希望项目占据相邻的内存位置,请使用QVector.

参考：

QVector、Qlist、QlinkedList 类 用法比较： - 莫水千流 - 博客园

Qt 中的顺序容器：QList、QVector - 知乎