3.2 Qt容器类
Qt提供了一组通用的基于模板的容器类。相比C++的标准模板库中的容器类，Qt的这些容器更轻量、更安全并且更容易使用。此外，Qt的容器类在速度、内存消耗和内联（inline）代码等方面进行了优化（较少的内联代码将会减少可执行程序的大小）。
存储在Qt容器中的数据必须是可赋值的数据类型，也就是说，这种数据类型必须提供一个默认的构造函数（不需要参数的构造函数）、一个复制构造函数和一个赋值操作运算符。
这样的数据类型包含了通常使用的大多数数据类型，包括基本数值类型（比如int和double等）和Qt的一些数据类型（比如QString、QDate和QTime等）。不过，Qt的QObject及其他的子类（比如QWidget、Qdialog）等是不能够存储在容器中的，例如：
QList<QToolBar> list;
上述代码是无法通过编译的，因为这些类（QObject及其他的子类）是没有复制构造函数和赋值操作运算符的。
一个可代替的方案是存储QObject及其子类的指针，例如：
QList<QToolBar＊> list;
Qt的容器类是可以嵌套的，例如：
QHash<QString, QList<double> >
其中：QHash的键类型是QString，它的值类型是QList<double>。注意，在最后两个符号“>”之间要保留一个空格。否则，C++编译器会把两个“>”符号解释为一个“>>”符号，导致无法通过编译器编译。
Qt的容器类为遍历其中的内容提供了两种方法：
(1) Java风格的迭代器（Java-style iterators）。
(2) STL风格的迭代器（STL-style iterators），能够同Qt和STL的通用算法一起使用，并且在效率上也略胜一筹。
下面，重点看一下经常使用到的Qt容器类。
3.2.1 QList类、QLinkedList类和QVector类
经常使用到的Qt容器类有QList、QLinkedList和QVector等。在开发一个较高性能需求的应用程序时，程序员会比较关注这些容器类的运行效率，表3.1列出了QList、QLinkedList和QVector容器的时间复杂度。
表3.1 QList、QLinkedList和QVector容器时间复杂度比较
其中："Amort.O(1)"表示，如果仅仅完成一次操作，可能会有O(n)行为；但是如果完成多次操作(例如n次)，平均结果将会是O(1)。
1.QList类
QList<T>是目前为止最常用的容器类，它存储给定数据类型T的一列数值。继承自QList类的子类有QItemSelection、QQueue、QSignalSpy以及QStringList和QTestEventList。
QList提供了可以在列表进行追加的QList::append()和Qlist::prepend()函数，也提供了在列表中间完成插入操作的函数QList::insert()。相对于任何其他的Qt容器类，为了使可执行代码尽可能少，QList被高度优化。
QList<T>维护了一个指针数组，该数组存储的指针指向QList<T>存储的列表项的内容。因此，QList<T>提供了基于下标的快速访问。
对于不同的数据类型，QList<T>采取不同的存储策略，存储策略有以下几种：
(1) 如果T是一个指针类型或指针大小的基本类型（即该基本类型占有的字节数和指针类型占有的字节数相同），QList<T>会把数值直接存储在它的数组中。
(2) 如果QList<T>存储对象的指针，该指针指向实际存储的对象。
下面举一个例子：
#include <QDebug>
int main(int argc,char ＊argv[])
{
QList<QString> list;
{
QString str("This is a test string");
list<<str;
}
qDebug()<<list[0]<< "How are you! ";
return 0;
}
其中：
● QList<QString> list：声明了一个QList<QString>栈对象。
● list<<str：通过操作运算符“<<”将一个QString字符串存储在该列表中。
● 程序中的花括弧“{”和“}”括起来的作用域表明，此时，QList<T>保存了对象的一个复制。
2.QLinkedList类
QLinkedList<T>是一个链式列表，它以非连续的内存块保存数据。
QLinkedList<T>不能够使用下标，只能够使用迭代器访问它的数据项。与QList相比，当对一个很大的列表进行插入操作时，QLinkedList具有更高的效率。
3.QVector类
QVector<T>在相邻的内存中存储给定数据类型T的一组数值。在一个QVector的前部或者中间位置进行插入操作的速度是很慢的，这是因为这样的操作会导致内存中的大量数据被移动，这是由QVector存储数据的方式决定的。
QVector<T>既可以使用下标访问数据项，也可以使用迭代器访问数据项。继承自QVector类的子类有QPolygon、QPolygonF和QStack。
4.Java风格迭代器遍历容器
Java风格的迭代器是Qt 4新加入的一个功能。同STL风格的迭代器相比，它使用起来更简单方便，不过这也是以轻微的性能损耗为代价的。对于每一个容器类，Qt都提供了两种类型的Java风格迭代器数据类型，即只读访问和读写访问，其分类如表3.2表示。
表3.2 Java风格迭代器的两种分类
Java风格迭代器的迭代点（Java-style iterators point）位于列表项的中间，而不是直接指向某个列表项。因此，它的迭代点或者在第一个列表项的前面，或者在两个列表项之间，或者在最后一个列表项之后。
下面以QList为例，介绍Java风格的两种迭代器的用法。而QLinkedList和QVector具有和QList相同的遍历接口，在此不再详细讲解。
(1) 举例介绍如何实现QList的只读遍历方法。这是一个简单的控制台程序。对于Qt的一些类，比如QString、QList等，不需要QcoreApplication（对于GUI用户界面程序则使用Qapplication）的支持也能够工作，因此本例没有创建QCoreApplication对象。但是，在使用Qt编写应用程序时，如果是控制台应用程序，建议初始化一个QCoreApplication对象；如果是GUI图形用户界面程序，则初始化QApplication对象。其具体代码如下：
#include <QDebug>
int main(int argc,char ＊argv[])
{
QList<int> list;
list<<1<<2<<3<<4<<5;
QListIterator<int> i(list);
for(;i.hasNext();)
qDebug()<<i.next();
return 0;
}
其中：
● 头文件<QDebug>已经包含了QList的头文件。
● QList<int> list：创建一个QList<int>栈对象list。
● list<<1<<2<<3<<4<<5：用操作运算符“<<”输入5个整数值。
● QListIterator<int> i(list)：以该list为参数初始化一个QListIterator对象i。此时，迭代点处在第一个列表项“1”的前面（注意，并不是指向该列表项）。
● for(;i.hasNext();)：调用QListIterator<T>::hasNext()函数检查当前迭代点之后是否有列表项。如果有，则调用QListIterator<T>::next()函数进行遍历。next()函数将会跳过下一个列表项（即迭代点将位于第一个列表项和第二个列表项之间），并返回它跳过的列表项的内容。
● 最后程序的运行结果为：
1 2 3 4 5
上述例子是QListIterator<T>对列表进行向后遍历的函数，而对列表进行向前遍历的函数有：
QListIterator<T>::toBack()：将迭代点移动到最后一个列表项的后面。
QListIterator<T>::hasPrevious()：检查当前迭代点之前是否具有列表项。
QListIterator<T>::previous()：函数返回前一个列表项的内容并将迭代点移动到前一个列表项之前。
除此之外，QListIterator<T>提供的其他函数还有：
toFront()：移动迭代点到列表的前端（第一个列表项的前面）。
peekNext()：返回下一个列表项，但不移动迭代点。
peekPrevious()：返回前一个列表项，但不移动迭代点。
findNext()：从当前迭代点开始向后查找指定的列表项，如果找到，则返回true，此时迭代点位于匹配列表项的后面；如果没有找到，则返回false，迭代点位于列表的后端（最后一个列表项的后面）。
findPrevious()：与findNext()类似，不同的是它的方向是向前的，查找操作完成后的迭代点在匹配项的前面或整个列表的前端。
(2) QListIterator<T>是只读迭代器，它不能够完成列表项的插入和删除操作。读写迭代器QMutableListIterator<T>除了提供基本的遍历操作（与QListIterator的操作相同），还提供了insert()插入操作函数、remove()删除操作函数和修改数据函数等。
下面，举例介绍如何实现QList的读写遍历方法。具体代码如下：
#include <QDebug>
int main(int argc,char ＊argv[])
{
QList<int> list;
QMutableListIterator<int> i(list);
for(int j=0;j<10;++j)
i.insert(j);
for(i.toFront();i.hasNext();)
qDebug()<<i.next();
for(i.toBack();i.hasPrevious();)
{
if(i.previous()%2==0)
i.remove();
else
i.setValue(i.peekNext()＊10);
}
for(i.toFront();i.hasNext();)
qDebug()<<i.next();
return 0;
}
其中：
● QList<int> list：创建一个空的列表list。
● QMutableListIterator<int> i(list)：创建上述列表的读写迭代器。
● i.insert(j)：通过QMutableListIterator<T>::insert()插入操作为该列表插入10个整数值。
● for(i.toFront();i.hasNext();)、qDebug()<<i.next()：将迭代器的迭代点移动到列表的前端，完成对列表的遍历和输出。
● for(i.toBack();i.hasPrevious();){…}：移动迭代器的迭代点到列表的后端，对列表进行遍历。如果前一个列表项的值为偶数，则将该列表项删除；否则，将该列表项的值修改为原来的10倍。
● i.setValue(i.peekNext()＊10)：函数QMutableListIterator<T>::setValue()修改遍历函数next()、previous()、findNext()和findPrevious()跳过的列表项的值，但不会移动迭代点的位置。对于findNext()和findPrevious()有些特殊：当findNext()（或findPrevious()）查找到的时候，setValue()将会修改匹配的列表项；如果没有找到的话，对setValue()的调用将不会做任何修改。
● for(i.toFront();i.hasNext();){…}：重新遍历并输出列表。
● 程序运行结果如下：
0 1 2 3 4 5 6 7 8 9
10 30 50 70 90
5.STL风格迭代器遍历容器
对于每一个容器类，Qt都提供了两种类型的STL风格迭代器数据类型：一种提供只读访问，一种提供读写访问。由于只读类型的迭代器要比读写迭代器速度更快，所以应尽可能地使用只读类型的迭代器。两种风格迭代器分类如表3.3表示。
表3.3 STL风格迭代器的两种分类
STL风格的迭代器的API是建立在指针操作基础上的。例如，++操作运算符移动迭代器到下一个项（item），而*操作运算符返回迭代器指向的项。
不同于Java风格的迭代器，STL风格的迭代器的迭代点直接指向列表项。
下面以QList为例，介绍STL风格的两种迭代器的用法。而QLinkedList和QVector具有和QList相同的遍历接口，在此不再详细讲解。
● QList<T>::begin()函数，返回指向第一个列表项的迭代器。
● QList<T>::end()函数，返回一个容器最后列表项之后的虚拟列表项，标记无效位置的迭代器，它用于判断是否到达容器的底部。
下面，举例介绍如何使用STL风格的迭代器，具体代码如下：
#include <QDebug>
int main(int argc,char ＊argv[])
{
QList<int> list;
for(int j=0;j<10;j++)
list.insert(list.end(),j);
QList<int>::iterator i;
for(i=list.begin();i!=list.end();++i)
{
qDebug()<<(＊i);
＊i=(＊i)＊10;
}
QList<int>::const_iterator ci;
for(ci=list.constBegin();ci!=list.constEnd();++ci)
qDebug()<<＊ci;
return 0;
}
其中：
● QList<int> list：初始化一个空的QList<int>列表。
● list.insert(list.end(),j)：使用QList<T>::insert()函数插入10个整数值。此函数有两个参数：第一个参数是QList<T>::iterator类型，表示在该列表项之前插入一个新的列表项（使用QList<T>::end()函数返回的迭代器，表示在列表的最后插入一个列表项）；第二个参数指定了需要插入的值。
● QList<int>::iterator i：初始化一个QList<int>::iterator读写迭代器。
● for(i=list.begin();i!=list.end();++i){…}：在控制台输出列表的同时将列表的所有值增大10倍。
● QList<int>::const_iterator ci：初始化一个QList<int>:: const_iterator读写迭代器。
● for(ci=list.constBegin();ci!=list.constEnd();++ci) {…}：在控制台输出列表的所有值。
最后编译，运行此应用程序，输出结果如下：
0 1 2 3 4 5 6 7 8 9
0 10 20 30 40 50 60 70 80 90
3.2.2 QMap类和QHash类
QMap类和QHash类具有非常类似的功能，它们的差别仅在于：
● QHash具有比QMap更快的查找速度。
● QHash以任意的顺序存储数据项，而QMap总是按照键Key顺序存储数据。
● QHash的键类型Key必须提供operator==()和一个全局的qHash(Key)函数，而QMap的键类型Key必须提供operator<()函数。
二者的时间复杂度比较如表3.4所示。
表3.4 QMap和QHash时间复杂度的比较
其中："Amort.O(1) "表示，如果仅仅完成一次操作，可能会有O(n)行为；但如果完成多次操作(例如n次)，平均结果将会是O(1)。
1.QMap类
QMap<Key,T>提供了一个从类型为Key的键到类型为T的值的映射。
通常，QMap存储的数据形式是一个键对应一个值，并且按照键Key的次序存储数据。为了能够支持一键多值的情况，QMap提供了QMap<Key,T>::insertMulti()和QMap<Key,T>::values()函数。存储一键多值的数据时，也可以使用QMultiMap<Key,T>容器，它继承自QMap。
2.QHash类
QHash<Key,T>具有和QMap几乎完全相同的API。QHash维护着一张哈希表（hash table），哈希表的大小和QHash的数据项的数目相适应。
QHash以任意的顺序组织它的数据。当存储数据的顺序无关紧要时，建议使用QHash作为存放数据的容器。QHash也可以存储一键多值形式的数据，它的子类QMultiHash<Key,T>实现了一键多值的语义。
3.Java风格迭代器遍历容器
对于每一个容器类，Qt都提供了两种类型的Java风格迭代器数据类型：一种提供只读访问，一种提供读写访问，其分类如表3.5所示。
表3.5 Java风格迭代器的两种分类
下面的例子完成了在QMap中的插入、遍历和修改。
#include <QDebug>
int main(int argc,char ＊argv[])
{
QMap<QString,QString> map;
map.insert("beijing","111");
map.insert("shanghai","021");
map.insert("jinan","0531");
QMapIterator<QString,QString> i(map);
for(;i.hasNext();)
qDebug()<<" "<<i.peekNext().key()<<" "<<i.next().value();
QMutableMapIterator<QString,QString> mi(map);
if(mi.findNext("111"))
mi.setValue("010");
QMapIterator<QString,QString> modi(map);
qDebug()<<" ";
for(;modi.hasNext();)
qDebug()<<" "<<modi.peekNext().key()<<" "<<modi.next().value();
return 0;
}
其中：
● QMap<QString,QString> map：创建一个QMap栈对象。
● map.insert(…)：向栈对象插入<城市，区号>对。
● QMapIterator<QString,QString> i(map)：创建一个只读迭代器。
● for(;i.hasNext();)、qDebug()<<" "<<i.peekNext().key()<<" "<<i.next().value()：完成对QMap的遍历输出。在输出QMap的键和值时，调用的函数是不同的。因为，在输出键的时候，不需要让迭代点移动到下一个位置，因此调用了QMapIterator<T,T>::peekNext()；而在输出值的时候调用了QmapIterator <T,T>::next()。
● if(mi.findNext("111"))、mi.setValue("010")：查找某个<键,值>对，然后修改值。Java风格的迭代器没有提供查找键的函数。因此，在例子中通过查找值的函数QMutableMapIterator<T,T>::findNext()来实现查找和修改。
● for(;modi.hasNext();) {…}：再次遍历并输出修改后的结果。
● 程序运行结果如下：
"beijing" "111"
"shanghai" "021"
"jinan" "0531"
"beijing" "010"
"shanghai" "021"
"jinan" "0531"
从上面的运行结果可以看出，QMap<T,T>是按照键的顺序键存储数据的。
4.STL风格迭代器遍历容器
对于每一个容器类，Qt都提供了两种类型的STL风格迭代器数据类型：一种提供只读访问，一种提供读写访问，其分类如表3.6所示。
表3.6 STL风格迭代器的两种分类
下面的程序功能与使用Java风格迭代器的例子基本相同。不同的是，这里通过查找键来实现值的修改。
#include <QDebug>
int main(int argc,char ＊argv[])
{
QMap<QString,QString> map;
map.insert("beijing","111");
map.insert("shanghai","021");
map.insert("jinan","0531");
QMap<QString,QString>::const_iterator i;
for(i=map.constBegin();i!=map.constEnd();++i)
qDebug()<<" "<<i.key()<<" "<<i.value();
QMap<QString,QString>::iterator mi;
mi=map.find("beijing");
if(mi!=map.end())
mi.value()="010";
QMap<QString,QString>::const_iterator modi;
qDebug()<<" ";
for(modi=map.constBegin();modi!=map.constEnd();++modi)
qDebug()<<" "<<modi.key()<<" "<<modi.value();
return 0;
}
其中：
● mi.value()="010"：将新的值直接赋给QMap<QString,QString>::iterator::value()返回的结果，因为该函数返回的是<键,值>对其中值的引用。
● 编译运行程序，其输出的结果与上面的程序完全相同。