来源: https://doc.qt.io/archives/qt-5.12/containers.html

简介

Qt库提供基于模板的通用容器类，相比STL容器类更轻量化、安全和易用。

容器类是隐式共享的、可重入的并且针对速度、低内存开销和最小内内联代码拓展进行了优化，这样实现了更小的可执行文件。此外。在某些情况下被用作只读容器时是线程安全的.

为了访问容器内的项目，可以使用两种类型的迭代器:java风格迭代器和STL风格迭代器。java风格迭代器更易用而且提供高级功能。STL风格稍微更高效而且可以和QT和STL的泛型算法一起使用。

QT还提供foreach关键字更方便地遍历容器。

容器类

类	说明
QList<T>	目前最常用的容易。可以通过索引访问存储数据。内部使用数组实现，保证使用索引快速访问。 可以使用QList::append(),QList::prepend(),QList::insert()在列表尾、头、中插入项目。QList经过高度优化，可以在可执行程序中尽可能少地扩展代码。 QStringList继承自QList<QString>
QLinkedList<T>	和QList类似，但是使用迭代器而不是索引访问数据。在大型列表的中间插入项目时性能比QList好，而且有更好的迭代器语义(QLinkedList中只要项目存在，那么指向项目的迭代器就是有效的；而QList的迭代器在任何插入或移除操作后就变成了无效的）
QVector<T>	在使用相邻的内存存储数组。在头部和中间插入数据会很慢
QStatck<T>	QVector子类，提供LIFO语义,添加QVector::push(),QVector::pop(),QVector::top().功能
QQueue<T>	QList子类，提供FIFO语义，添加QQueue::enqueue,QList::dequeue和head()功能
QSet<T>	提供具有快速查找功能的单值数学集
QMap<Key,T>	它提供了一个字典(关联数组)，将Key类型的键映射到T类型的值。通常每个键都与单个值相关联。QMap按Key顺序存储数据;如果顺序不重要，QHash是一个更快的选择。
QMultiMap<Key,T>	这是QMap的一个方便的子类，它为多值映射提供了一个很好的接口，即一个键可以与多个值相关联的映射。
QHash<Key,T>	它具有与QMap几乎相同的API，但提供了明显更快的查找。QHash以任意顺序存储数据。
QMultiHash<Key,T>	这是QHash的一个方便的子类，它为多值哈希提供了一个很好的接口。

容器类可以级联，如QMap<QString,QList<int>>

容器类定义在独立的头文件中，文件名与容器类名一致。为方便起见，在<QtContainerFwd>中向前声明了容器。

存储在各种容器中的值可以是任何可赋值的数据类型。要符合条件，类型必须提供默认构造函数、复制构造函数和赋值操作符。这涵盖了您可能想要存储在容器中的大多数数据类型，包括基本类型，如int和double，指针类型，以及Qt数据类型，如QString, QDate和QTime，但它不包括QObject或任何QObject子类(QWidget, QDialog, QTimer等)。如果尝试实例化QList<QWidget>，编译器将报错QWidget的复制构造函数和赋值操作符是错误的

有些容器对它们可以存储的数据类型有额外的要求。例如，QMap<Key, T>的Key类型必须提供operator<()。这些特殊需求在类的详细描述中都有文档。在某些情况下，特定功能有特殊要求;这些是按功能描述的。如果不满足要求，编译器总是会发出一个错误。

Qt的容器提供了operator<<()和operator>>()，因此它们可以很容易地使用QDataStream进行读写。这意味着存储在容器中的数据类型还必须支持operator<<()和operator>>()。

某些容器类函数的文档引用默认构造的值;例如，QVector用默认构造的值自动初始化它的项。如果指定的键不在映射中，QMap::value()返回一个默认构造的值。对于大多数值类型，这仅仅意味着使用默认构造函数创建一个值(例如 QString 的空字符串)。但是对于int和double这样的基本类型，以及指针类型，c++语言没有指定任何初始化;在这种情况下，Qt的容器会自动将该值初始化为0。

迭代器类

两种迭代器:java风格和STL风格，当由于调用非const成员函数而修改或从隐式共享副本中分离容器中的数据时，这两种类型的迭代器都无效

JAVA风格迭代器

容器	只读迭代器	读-写迭代器
QList<T>,QQueue<T>	QListIterator<T>	QMutableListIterator<T>
QLinkedList<T>	QLinkedListIterator<T>	QMutableLinkedListIterator<T>
QVector<T>,QStack<T>	QVectorIterator<T>	QMutableVectorIterator<T>
QSet<T>	QSetInterator<T>	QMutableVectorIterator<T>
QMap<Key,T>,QMultiMap<Key,T>	QMapIterator<Key,T>	QMutableMapIterator<Key,T>
QHash<Key,T>,QMultiMap<Key,T>	QHashIterator<Key,T>	QMutableHashIterator<Key,T>

Java风格迭代器指向项目之间而不是直接指向数据项

使用迭代器访问QList

QList<QString> list;
list << "A" << "B" << "C" << "D";// 前向访问
QListIterator<QString> i(list);
while (i.hasNext())qDebug() << i.next();
//后向访问
QListIterator<QString> i(list);
i.toBack(); //迭代器移动到末尾
while (i.hasPrevious())qDebug() << i.previous();

QListIterator不提供在迭代时从列表中插入或删除项的函数。要做到这一点，必须使用QMutableListIterator。下面是一个使用QMutableListIterator从QList中删除所有奇数的例子

//前向
QMutableListIterator<int> i(list);
while (i.hasNext()) {if (i.next() % 2 != 0)i.remove();
}
//后向
QMutableListIterator<int> i(list);
i.toBack();
while (i.hasPrevious()) {if (i.previous() % 2 != 0)i.remove();
}

循环中的next()调用每次都进行。它跳过列表中的下一项。remove()函数删除了我们从列表中跳过的最后一项。调用remove()不会使迭代器失效，所以继续使用它是安全的。

与QListIterator一样，QMapIterator提供toFront()、toBack()、hasNext()、next()、peekNext()、hasPrevious()、previous()和peekPrevious()。键和值组件是通过对next()、peekNext()、previous()或peekPrevious()返回的对象调用key()和value()来提取的。

下面的例子删除所有以"City"结尾的(capital, country)对:

QMap<QString, QString> map;
map.insert("Paris", "France");
map.insert("Guatemala City", "Guatemala");
map.insert("Mexico City", "Mexico");
map.insert("Moscow", "Russia");
...QMutableMapIterator<QString, QString> i(map);
while (i.hasNext()) {if (i.next().key().endsWith("City"))i.remove();
}

QMapIterator还提供了一个key()和一个value()函数，它们直接对迭代器进行操作，并返回迭代器跳到上面的最后一项的键和值

STL风格迭代器

容器	只读迭代器	读-写迭代器
QList<T>, QQueue	QList<T>::const_iterator	QList<T>::iterator
QLinkedList<T>	QLinkedList<T>::const_iterator	QLinkedList<T>::iterator
QVector<T>, QStack<T>	QVector<T>::const_iterator	QVector::iterator
QSet<T>	QSet<T>::const_iterator	QSet<T>::iterator
QMap<Key, T>, QMultiMap<Key, T>	QMap<Key, T>::const_iterator	QMap<Key, T>::iterator
QHash<Key, T>, QMultiHash<Key, T>	QHash<Key, T>::const_iterator	QHash<Key, T>::iterator

STL迭代器的API以数组中的指针为模型。例如，++操作符将迭代器推进到下一项，*操作符返回迭代器指向的项。实际上，对于QVector和QStack(它们将元素存储在相邻的内存位置)，迭代器类型只是T *的一个typedef，而const_iterator类型只是const T *的一个typedef。

下面是按顺序遍历QList<QString>中的所有元素并将它们转换为小写的典型循环:

QList<QString> list;
list << "A" << "B" << "C" << "D";QList<QString>::iterator i;
for (i = list.begin(); i != list.end(); ++i)*i = (*i).toLower();

与Java风格的迭代器不同，stl风格的迭代器直接指向项。容器的begin()函数返回一个迭代器，该迭代器指向容器中的第一项。容器的end()函数返回一个迭代器，指向容器中最后一项后面一个位置的虚项。End()标记一个无效的位置;它永远不能被取消引用。它通常用于循环的中断条件。如果列表为空，begin()等于end()，因此我们永远不会执行循环。

使用STL风格的迭代器进行向后迭代可以使用反向迭代器完成:

QList<QString> list;
list << "A" << "B" << "C" << "D";QList<QString>::reverse_iterator i;
for (i = list.rbegin(); i != list.rend(); ++i)*i = i->toLower();
}

由于隐式共享，函数为每个值返回一个容器的成本非常低。Qt API包含几十个函数返回一个QList或QStringList(例如，QSplitter::sizes())。如果希望使用STL迭代器遍历这些对象，则应该始终获取容器的一个副本，并遍历该副本。例如:

// RIGHT
const QList<int> sizes = splitter->sizes();
QList<int>::const_iterator i;
for (i = sizes.begin(); i != sizes.end(); ++i)...// WRONG
QList<int>::const_iterator i;
for (i = splitter->sizes().begin();i != splitter->sizes().end(); ++i)...

对于返回const或非const对容器的引用的函数，不会出现此问题。

隐式共享问题

隐式共享对于STL风格的迭代器还有另一个后果:当迭代器在容器上处于活动状态时，应该避免复制容器。迭代器指向内部结构，如果复制容器，则应该非常小心地使用迭代器.

QVector<int> a, b;
a.resize(100000); // make a big vector filled with 0.QVector<int>::iterator i = a.begin();
// 错误地使用迭代器 i:
b = a;
/*现在我们应该小心使用迭代器i，因为它将指向共享数据如果我们执行*i = 4，那么我们将改变共享实例(两个vector)其行为与STL容器不同。避免在Qt中做这样的事情。
*/a[0] = 5;
/*容器a现在与共享数据分离，即使i是容器a中的迭代器，它现在也可以作为容器b中的迭代器。现在 (*i) == 0而不是5
*/b.clear(); // 现在迭代器i是完全无效的int j = *i; // 未定义的行为!
/*b的数据(i指向的)没有了。对于STL容器这样的操作没有问题，是有定义的行为((*i) == 5)但对于QVector，这可能会崩溃
*/

foreach关键字

如果想顺序遍历容器中的所有项目，可以使用foreach关键字。
语法：foreach(variable,container)

QLinkedList<QString> list;
...
QString str;
foreach (str, list)qDebug() << str

除非数据类型包含逗号(例如，QPair<int, int>)，否则用于迭代的变量可以在foreach语句中定义:

QLinkedList<QString> list;
...
foreach (const QString &str, list)qDebug() << str;

对于QMap和QHash, foreach会自动访问(键、值)对的值组件，因此您不应该在容器上调用values()(它会生成一个不必要的副本，见下文)。如果你想遍历键和值，你可以使用迭代器(更快)，或者你可以获取键，并使用它们来获取值:

QMap<QString, int> map;
...
foreach (const QString &str, map.keys())qDebug() << str << ':' << map.value(str);

Qt在进入foreach循环时自动获取容器的副本。如果在迭代时修改容器，则不会影响循环。(如果不修改容器，复制仍然会发生，但是由于隐式共享，复制容器非常快。)
由于foreach创建了容器的副本，因此使用变量的非const引用不允许修改原始容器，它只影响副本。

Qt的foreach循环的另一种选择是基于范围的循环(range-based for)，这是c++ 11及更新版本的一部分。但是，请记住，基于范围的for可能会强制Qt容器分离，而foreach则不会。但是使用foreach总是复制容器，这对于STL容器来说通常并不便宜。如果有疑问，对于Qt容器首选foreach，对于STL容器首选range based for。

除了foreach, Qt还为无限循环提供了一个forever伪关键字

如果你担心命名空间污染，你可以通过在你的.pro文件中添加以下一行来禁用这些宏:

CONFIG += no_keywords

其他容器类

Qt包含几个模板类，它们在某些方面与容器相似。这些类不提供迭代器，不能与foreach关键字一起使用。

容器类	说明
QVarLengthArray<T,Prealloc>	提供低级可变长度数组。在速度特别重要的地方，它可以代替QVector
QCache<Key, T>	提供了一个缓存来存储与Key类型的键相关联的特定类型T的对象
QContiguousCache<T>	提供一种高效的方式来缓存通常以连续方式访问的数据
QPair<T1, T2>	存储一对元素

与Qt的模板容器竞争的其他非模板类型有QBitArray、QByteArray、QString和QStringList。

算法复杂度

容器类	查找	插入	头部添加	尾部添加
QLinkedList<T>	O(n)	O(1)	O(1)	O(1)
QList<T>	O(1)	O(n)	平摊O(1)	平摊O(1)
QVector<T>	O(1)	O(n)	O(n)	平摊O(1)

容器类	键查找		插入
	平均	最差	平均	最差
QMap<Key,T>	O(log n)	O(log n)	O(log n)	O(log n)
QMultiMap<Key,T>	O(log n)	O(log n)	O(log n)	O(log n)
QHash<Key,T>	平摊O(1)	O(n)	平摊O(1)	O(n)
QSet<Key,T>	平摊O(1)	O(n)	平摊O(1)	O(n)

对于QVector, QHash和QSet，附加项的性能平摊为O(log n)。在插入项之前，通过调用QVector::reserve()， QHash::reserve()或QSet::reserve()，可以将其降至O(1)。下一节将更深入地讨论这个主题。

增长策略

QVector、QString和QByteArray将它们的元素连续存储在内存中;QList维护一个指向它所存储的项的指针数组，以提供快速的基于索引的访问(除非T是指针类型或指针大小的基本类型，在这种情况下，值本身存储在数组中);QHash<Key, T>保存一个哈希表，其大小与哈希表中的项数成正比。为了避免每次在容器末尾添加一个项时重新分配数据，这些类通常会分配比所需更多的内存

考虑下面的代码，它从另一个QString构建一个QString:

QString onlyLetters(const QString &in)
{QString out;for (int j = 0; j < in.size(); ++j) {if (in[j].isLetter())out += in[j];}return out;
}

我们通过每次添加一个字符来动态地构建字符串。假设我们向QString字符串追加了15000个字符。然后，当QString耗尽空间时，将发生以下18次重新分配(可能有15000次):4,8,12,16,20,52,116,244,500,1012,2036,4084,6132,8180,10228,12276,14324,16372。最后，QString分配了16372个Unicode字符，其中15000个已被占用。

上面的价值观可能看起来有点奇怪，但这里是指导原则:

• QString每次分配4个字符，直到它的大小达到20。
• 从20到4084，它的大小每次增加一倍。更准确地说，是2的下一个幂，减12。(有些内存分配器在请求精确的2次幂时表现最差，因为它们每个块使用几个字节进行记录。)
• 从4084开始，它以2048个字符(4096字节)为块前进。这是有意义的，因为现代操作系统在重新分配缓冲区时不会复制整个数据;物理内存页只是重新排序，实际上只需要复制第一页和最后一页上的数据。

QByteArray和QList使用与QString相同的算法。

QVector对于可以使用memcpy()在内存中移动的数据类型(包括基本c++类型、指针类型和Qt的共享类)也使用该算法，但是对于只能通过调用复制构造函数和析构函数来移动的数据类型使用不同的算法。由于在这种情况下重新分配的成本更高，QVector通过在空间耗尽时始终将内存加倍来减少重新分配的次数

QHash<Key, T>是完全不同的情况。QHash的内部哈希表以2的幂增长，每次增长时，项目都被重新定位到一个新的桶(bucket)中，计算为qHash (key) % QHash::capacity()(桶的数量)。这也适用于QSet<T>和QCache<Key, T>。

对于大多数应用程序，Qt提供的默认增长算法可以解决这个问题。如果你需要更多的控制，QVector<T>、QHash<Key, T>、QSet<T>、QString和QByteArray提供了三个函数，允许你检查和指定使用多少内存来存储项:

• capacity()返回分配内存的项数(对于QHash和QSet，是哈希表中的桶数)。
• reserve (size)显式地为size项预先分配内存。
• squeeze()释放存储项不需要的内存

如果您大致知道将在容器中存储多少项，则可以从调用reserve()开始，当您完成容器的填充后，可以调用squeeze()来释放额外的预分配内存。