容器类，Qt

大家好，今天给各位分享容器类的一些知识，其中也会对Qt进行解释，文章篇幅可能偏长，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在就马上开始吧！

注：本文是我对Qt官方文档的翻译，错误之处还请指正。

Qt库提供了一套通用的基于模板的容器类，可以用这些类存储指定类型的项。比如，你需要一个大小可变的QString的数组，则使用QVector<QString>。

这些容器类比STL（C++标准模板库）容器设计得更轻量、更安全并且更易于使用。如果对STL不熟悉，或者倾向于用“Qt的方式”，那么你可以使用这些类，而不去用STL的类。

这些容器类是隐式共享的、可重入的，并且对速度、内存消耗等进行了优化。除此之外，当它们作为只读的容器时是线程安全的，所有线程都可以使用它们。

你可以用两种方式遍历容器内存储的项：Java风格的迭代器和STL风格的迭代器。Java风格的迭代器更易于使用，并且提供了更高级的功能；STL风格的迭代器更高效，并且可以和Qt与STL的泛型算法一起使用。

Qt还提供了foreach关键字使我们方便地遍历容器中的项。

Qt提供了几个有序容器：QList、QLinkedList、QVector、QStack和QQueue。大多数时候，QList是最好的选择，虽然是用数组实现的，但在它的首尾添加元素都非常快。如果你需要一个链表（linked-list）就用QLinkedList；想要你的项在内存中连续存储，就使用QVector。QStack和QQueue（栈和队列）分别提供了后进先出（LIFO）和先进先出（FIFO）的机制。

Qt还有一些关联容器：QMap、QMultiMap、QHash、QMultiHash、QSet。“Multi”容器支持一个键对应多个值。“Hash”容器在有序集合上使用hash函数进行快速的查找，而没有用二叉搜索。

作为特殊的情况，QCache和QContiguousCache类在有限的缓存中提供对对象高效的哈希查找。

容器是可嵌套的。比如当键是QString类型、值是QList<int>类型时，用QMap<QString,QList<int>>是最好的选择，唯一的缺点是你必须在结尾的两个尖括号(>)之间插入一个空格，否则C++编译器可能会误将两个>当作右移运算符来解释，出现语法错误。

存储在容器中的值可以是任何可赋值的数据类型，为了达到这一点，一个类型必须有默认构造函数、拷贝构造函数还有一个赋值运算符。这个已经涵盖了大多数你可能想要存在容器中的类型，包括基本类型，比如int和double、指针类型，还有Qt中的类型，比如QString、QDate和QTime，但是它不包括QObject或者QObject的子类(QWidget,QDialog,QTimer等等)。如果你尝试使用QList<QWidget>，编译器可能会提示QWidget的拷贝构造函数和赋值操作符不可用。所以如果你想在容器中存储这些类型，把它们当做指针就行了，比如QList<QWidget*>。

这里有一个例子，达到可赋值的数据类型条件的一个普通数据类型：

【领更多QT学习资料，点击下方链接免费领取↓↓，先码住不迷路~】

点击领取→Qt+音视频开发基础知识和资料包

classEmployee\n{\npublic:\nEmployee(){}\nEmployee(constEmployee&other);\n\nEmployee&operator=(constEmployee&other);\n\nprivate:\nQStringmyName;\nQDatemyDateOfBirth;\n};

如果我们没有提供拷贝构函数或赋值运算符，C++会提供“一个值一个值地赋值”的默认实现。而且，如果你没有提供任何构造函数，C++将提供一个默认的构造函数，使用默认构造函数初始化它的成员。虽然没有任何显式的构造函数或赋值运算符，下面的数据类型可以被存在容器中：

structMovie\n{\nintid;\nQStringtitle;\nQDatereleaseDate;\n};

有些容器对它们能够存储的数据类型有特殊的要求，例如QMap<Key,T>键Key的必须提供<()运算符。在一些情况中，特定的函数有特殊的要求，达不到要求的话编译器将会报错。

Qt的容器提供运算符<<()和运算符>>()，这样一来它们很容易使用QDataStream来读写，这意味着容器中的数据类型也必须支持运算符<<()和>>()。我们可以对上面的Movie类做一些事：

QDataStream&operator<<(QDataStream&out,constMovie&movie)\n{\nout<<(quint32)movie.id<<movie.title\n<<movie.releaseDate;\nreturnout;\n}\n\nQDataStream&operator>>(QDataStream&in,Movie&movie)\n{\nquint32id;\nQDatedate;\n\nin>>id>>movie.title>>date;\nmovie.id=(int)id;\nmovie.releaseDate=date;\nreturnin;\n}迭代器类

迭代器提供了获得容器中项的一套方法，Qt容器类有两种类型的迭代器：Java风格的以及STL风格的。当调用非const的成员函数将容器中的数据从隐式共享的拷贝中修改或分离时，两种迭代器都会失效。

Java风格的迭代器在Qt4中加入，比STL风格的迭代器更易于使用，但是以轻微的效率作为代价，它们的API以Java的迭代器类为模型。

对于每个容器类，都有两种Java风格的迭代器类型：一种是只读，另一种是可读写。

在这里，我们只关注QList和QMap。QLinkedList、QVector和QSet与QList的迭代器有同样的接口；QHash与QMap迭代器也有同样的接口。

与STL风格的迭代器不同，Java风格的迭代器指向项之间的位置，而不是直接指向项。由于这个原因，它们指向第一项之前，或者最后一项之后，或者两项之间。下面的图展示了包含4项的list的有效的迭代器位置，用红色箭头表示：

下面是一个典型的例子，迭代器按顺序循环遍历QList<QString>的所有元素，并把它们打印到控制台上：

QList<QString>list;\nlist<<"A"<<"B"<<"C"<<"D";\n\nQListIterator<QString>i(list);\nwhile(i.hasNext())\nqDebug()<<i.next();

流程是这样的：将要遍历的Qlist被传到QListIterator的构造函数，这时迭代器定位在list的第一项之前（"A"之前），接下来我们调用hasNext()来检测迭代器后面是否有一项，如果有，我们调用next()来跳过那一项，next()函数返回它跳过的那一项。对一个QList<QString>来说，那一项的类型是QString。

QListIterator<QString>i(list);\ni.toBack();\nwhile(i.hasPrevious())\nqDebug()<<i.previous();

代码和正序遍历是对称的，我们调用toBack()将迭代器移到最后一项后面的位置。

下图描述了在一个迭代器上调用next()和previous()函数的效果：

下面的表概括了QListIterator的API：

QListIterator没有提供从list中插入或移除项的函数，想要实现插入和移除，你必须使用QMutableListIterator。下面举例说明使用QMutableListIterator从QList<int>中移除所有奇数。

QMutableListIterator<int>i(list);\nwhile(i.hasNext()){\nif(i.next()%2!=0)\ni.remove();\n}

每次循环都会调用next()，它跳过list中的下一项，然后remove()函数移除我们刚刚从list中跳过的那一项，调用remove()不会使迭代器失效，所以它是安全的，我们可以继续使用它。在倒序遍历中同样有效：

QMutableListIterator<int>i(list);\ni.toBack();\nwhile(i.hasPrevious()){\nif(i.previous()%2!=0)\ni.remove();\n}

如果想修改某项的值，我们可以使用setValue()，下面的代码中，我们用128来替换所以大于128的值：

\nQMutableListIterator<int>i(list);\nwhile(i.hasNext()){\nif(i.next()>128)\ni.setValue(128);\n}

和remove()一样，setValue()操作我们刚刚跳过的那一项。如果是正序遍历，这一项在当前迭代器之前；如果是倒序遍历，这一项在当前迭代器之后。

next()函数返回list中这一项的非const引用，简单点，我们甚至连setValue()都不需要：

QMutableListIterator<int>i(list);\nwhile(i.hasNext())\ni.next()*=2;

正如上面所说，QLinkedList、QVector还有QSet的迭代器类和QList的迭代器有着相同的API。现在，我们来看看QMapIterator，有点不同，因为他在键值对上遍历。

类似于QListIterator，QMapIterator提供了toFront()、toBack()、hasNext()、next()、peekNext()、hasPrevious()、previous()以及peekPrevious()。键和值的部分通过调用next()、peekNext()、previous()或peekPrevious()返回的对象的key()和value()来获得。

下面的例子中，移除所有首都名字以“City”结尾的一对(capital,country)：

QMap<QString,QString>map;\nmap.insert("Paris","France");\nmap.insert("GuatemalaCity","Guatemala");\nmap.insert("MexicoCity","Mexico");\nmap.insert("Moscow","Russia");\n...\n\nQMutableMapIterator<QString,QString>i(map);\nwhile(i.hasNext()){\nif(i.next().key().endsWith("City"))\ni.remove();\n}

QMapIterator还提供了直接在迭代器上操作的key()和value()函数，返回迭代器跳过的上一项的键和值。比如，下面的代码把QMap中的内容复制到QHash中：

QMap<int,QWidget*>map;\nQHash<int,QWidget*>hash;\n\nQMapIterator<int,QWidget*>i(map);\nwhile(i.hasNext()){\ni.next();\nhash.insert(i.key(),i.value());\n}

如果想要使用同一个值遍历所有项，我们使用findNext()或findPrevious()。下面例子中，我们移除所有带有某个特定值的项：

QMutableMapIterator<int,QWidget*>i(map);\nwhile(i.findNext(widget))\ni.remove();STL风格的迭代器

自从Qt2.0发布就可以使用STL风格的迭代器了，它们适用于Qt和STL的泛型算法，并且对速度作了优化。

对于每个容器类，有两种STL风格的迭代器类型：只读的和可读写的。尽可能使用只读的迭代器，因为它们比可读写的迭代器要快。

STL迭代器的API是以数组中的指针为模型的，比如++运算符将迭代器前移到下一项，*运算符返回迭代器所指的那一项。事实上，对于QVector和QStack，它们的项在内存中存储在相邻的位置，迭代器类型正是T*，const迭代器类型正是constT*。

在讨论中，我们重点放在QList和QMap，QLinkedList、QVector和QSet的迭代器类型与QList的迭代器有相同的接口；同样地，QHash的迭代器类型与QMap的迭代器有相同的接口。

下面是一个典型例子，按顺序循环遍历QList<QString>中的所有元素，并将它们转为小写：

QList<QString>list;\nlist<<"A"<<"B"<<"C"<<"D";\n\nQList<QString>::iteratori;\nfor(i=list.begin();i!=list.end();++i)\n*i=(*i).toLower();

不同于Java风格的迭代器，STL风格的迭代器直接指向每一项。begin()函数返回指向容器中第一项的迭代器。end()函数返回指向容器中最后一项后面一个位置的迭代器，end()标记着一个无效的位置，不可以被解引用，主要用在循环的break条件。如果list是空的，begin()等于end()，所以我们永远不会执行循环。

【领更多QT学习资料，点击下方链接免费领取↓↓，先码住不迷路~】

点击领取→Qt+音视频开发基础知识和资料包

下图展示了一个包含4个元素的vector的所有有效迭代器位置，用红色箭头标出：

倒序遍历需要我们在获得项之前减少迭代器，这需要一个while循环：

QList<QString>list;\nlist<<"A"<<"B"<<"C"<<"D";\n\nQList<QString>::iteratori=list.end();\nwhile(i!=list.begin()){\n--i;\n*i=(*i).toLower();\n}

在上面的代码中，我们使用一元运算符*来获得存储在某个迭代器位置的项，然后我们调用QString::toLower()，大多数C++编译器还允许我们使用i->toLower()，但有些不允许。

如果是只读的，你可以使用const_iterator、constBegin()和constEnd()，比如：

QList<QString>::const_iteratori;\nfor(i=list.constBegin();i!=list.constEnd();++i)\nqDebug()<<*i;

下面的表概括了STL风格迭代器的API：

++和--运算符可以使用前缀(++i,--i)和后缀(i++,i--)的形式，前缀的版本修改迭代器并返回修改后迭代器的引用，后缀版本在修改之前先复制迭代器，然后返回它的拷贝。在不需要考虑返回值的情况下，我们推荐使用前缀运算符(++i,--i)，因为它们稍微快一点。

对于非const的迭代器类型，一元运算符*可以被用在赋值运算符的左边。

对于QMap和QHash，*运算符返回项的值，如果你想要获得键，只需在迭代器上调用key()。为了对称，迭代器类型还提供了value()函数来获得值。举个例子，下面是如何将QMap中的所有项打印到控制台上：

QMap<int,int>map;\n...\nQMap<int,int>::const_iteratori;\nfor(i=map.constBegin();i!=map.constEnd();++i)\nqDebug()<<i.key()<<":"<<i.value();

幸好有隐式共享，函数返回容器中的每个值效率很高。Qt的API包含很多返回QList或QStringList值的函数（比如QSplitter::sizes()）。如果想要使用STL迭代器遍历它们，你应该存储一个拷贝，并在拷贝上进行遍历。比如：

//RIGHT\nconstQList<int>sizes=splitter->sizes();\nQList<int>::const_iteratori;\nfor(i=sizes.begin();i!=sizes.end();++i)\n...\n\n//WRONG\nQList<int>::const_iteratori;\nfor(i=splitter->sizes().begin();\ni!=splitter->sizes().end();++i)

当函数返回容器的const或非const的引用，这个问题将不会发生。

如果你想要按顺序遍历容器中的所有项，你可以使用Qt的foreach关键字。这个关键字是Qt特有的，与C++语言无关，并且使用了预处理器实现。

它的语法是：foreach(variable,container)statement。比如，下面是如何使用foreach遍历QLinkedList<QString>：

QLinkedList<QString>list;\n...\nQStringstr;\nforeach(str,list)\nqDebug()<<str;

foreach代码明显比使用迭代器的代码少：

QLinkedList<QString>list;\n...\nQLinkedListIterator<QString>i(list);\nwhile(i.hasNext())\nqDebug()<<i.next();

除非数据类型包含一个逗号（比如QPair<int,int>），用于遍历的变量可以在foreach语句中定义：

QLinkedList<QString>list;\n...\nforeach(constQString&str,list)\nqDebug()<<str;

和其它任何C++循环一样，你可以在foreach循环中把主体放在括号里，而且你可以使用break来结束循环：

QLinkedList<QString>list;\n...\nforeach(constQString&str,list){\nif(str.isEmpty())\nbreak;\nqDebug()<<str;\n}

在QMap和QHash中，foreach可以获得键值对中值的部分。如果你遍历既想获得键又想获得值，则可以使用迭代器（这样是最快的），或者你可以这样写：

QMap<QString,int>map;\n...\nforeach(constQString&str,map.keys())\nqDebug()<<str<<":"<<map.value(str);

对于一个多值的（multi-valued）map：

QMultiMap<QString,int>map;\n...\nforeach(constQString&str,map.uniqueKeys()){\nforeach(inti,map.values(str))\nqDebug()<<str<<":"<<i;\n}

当进入foreach循环时Qt自动获得容器的一份拷贝，如果想修改你所遍历的容器，并不会影响循环。

foreach创建了容器的一份拷贝，使用变量的非const引用可以禁止你修改最初的容器，但它会影响拷贝，这也许是你不愿看到的。

Qt提供了三个模板类，在一些方面与容器有点像。这些类不提供迭代器，而且不能使用foreach关键字。

其它类似于模板容器的非模板类型有QBitArray、QByteArray、QString和QStringList。

算法复杂度关注当容器中项的数目增长时，函数有多快。例如，在QLinkedList中间插入一项是非常快的，无论其中存了多少项。另一方面，在QVector中项很多时，在中间插入一项是非常低效的，因为一半的项必须在内存中移动位置。

为了描述算法复杂度，我们使用下面的术语，基于“大O”标记法：

下面的表概括了Qt顺序容器的算法复杂度：

在表中，“Amort”指的是“平摊行为”。比如，“Amort.O(1)”指的是如果你只调用函数1次，你可能得到O(n)，但如果你多次调用，平均下来将是O(1)。

下面的表概括了Qt关联容器的算法复杂度：

QVector<T>、QString和QByteArray在内存中连续存储它们的项；QList<T>维护一个指向每一项指针的数组，从而提供快速的基于索引的获得方法；QHash<Key,T>维护一个哈希表，它的大小与其中项的个数成比例。为了避免每次在容器末尾增加一项就分配一次内存，这些容器比实际需要的分配了更多的内存。

我们考虑下面的程序，根据一个QString来建立另一个QString：

QStringonlyLetters(constQString&in)\n{\nQStringout;\nfor(intj=0;j<in.size();++j){\nif(in[j].isLetter())\nout+=in[j];\n}\nreturnout;\n}

我们通过一次增加一个字符来动态地建立字符串。假设需要增加15000个字符，当字符串空间不够时，将会发生18次重新分配内存：4,8,12,16,20,52,116,244,500,1012,2036,4084,6132,8180,10228,12276,14324,16372。最后，QString有16372个Unicode字符被分配，15000个被占用。

这些值可能看起来有点奇怪，下面是增长的规则：

QByteArray和QList<T>使用了与QString差不多的算法。

QVector<T>对一些数据类型也使用同样的算法，这些数据类型可以使用memcpy()在内存中移动（包括基本的C++类型，指针类型以及Qt的共享类）。但是QVector<T>对只能调用构造和析构函数来移动的数据类型使用了不同的算法，这些情况下重新分配内存的代价更高，当空间不够时，QVector<T>通过内存加一倍来减少再分配的次数。

QHash<Key,T>是一个完全不同的情况。QHash的内部哈希表以2的次方增长，每次增长时，项被定为到新的存储块中，通过qHash(key)%QHash::capacity()（存储快的数目）计算。这个机制同样适用于QSet<T>和QCache<Key,T>。

QVector<T>、QHash<Key,T>、QSet<T>、QString和QByteArray提供了一些函数，让你能够检测和确定存储这些项用了多少内存：

如果你知道在容器中大约要存储多少项，可以调用reserve()开始，当你在容器中存储结束，可以调用squeeze()来释放额外的预分配的内存。

关于容器类到此分享完毕，希望能帮助到您。