容器类¶

介绍¶

Qt库提供了一组基于模板的通用容器类。这些类可以用来存储指定类型的项目。例如，如果你需要一个可调整大小的QString数组，可以使用QList < QString >。

这些容器类设计得比STL容器更轻量、更安全、更易于使用。如果您不熟悉STL，或者更喜欢“Qt方式”做事，您可以使用这些类来代替STL类。

容器类是隐式共享的，它们是可重入的，并且它们针对速度、低内存消耗和最小的内联代码扩展进行了优化，从而产生更小的可执行文件。此外，在所有用于访问它们的线程将它们用作只读容器的情况下，它们是线程安全的。

容器提供了用于遍历的迭代器。STL风格的迭代器是最有效的，可以与Qt和STL的通用算法一起使用。Java风格的迭代器是为了向后兼容而提供的。

list = {1, 2, 3, 4, 4, 5}
set = QSet(list.cbegin(), list.cend())
/*
    Will generate a QSet containing 1, 2, 3, 4, 5.
*/

容器类¶

Qt 提供了以下顺序容器：QList、QStack 和 QQueue。对于大多数应用程序，QList 是最适合使用的类型。它提供了非常快速的追加操作。如果你真的需要一个链表，请使用 std::list。QStack 和 QQueue 是提供 LIFO 和 FIFO 语义的便利类。

Qt 还提供了这些关联容器：QMap、QMultiMap、QHash、QMultiHash 和 QSet。“Multi”容器方便地支持与单个键关联的多个值。“Hash”容器通过使用哈希函数而不是在排序集上进行二分查找来提供更快的查找。

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

类	摘要
QList	这是迄今为止最常用的容器类。它存储了一个给定类型（T）的值列表，可以通过索引访问。在内部，它在内存中相邻的位置存储了一个给定类型的值数组。在列表的前面或中间插入可能会非常慢，因为这可能导致大量项目必须在内存中移动一个位置。
QVarLengthArray	这提供了一个低级别的可变长度数组。在速度特别重要的地方，可以用它代替QList。
QStack	这是QList的一个便利子类，提供了“后进先出”（LIFO）的语义。它在QList已有的功能基础上增加了以下函数：push()、pop()和top()。
QQueue	这是QList的一个便利子类，提供了“先进先出”（FIFO）的语义。它在QList已有的函数基础上增加了以下函数：enqueue()、dequeue()和head()。
QSet	这提供了一个具有快速查找功能的单值数学集合。
QMap	这提供了一个字典（关联数组），将类型为 Key 的键映射到类型为 T 的值。通常每个键与一个单一的值相关联。QMap 按照键的顺序存储其数据；如果顺序不重要，QHash 是一个更快的替代方案。
QMultiMap	这提供了一个字典，类似于QMap，但它允许插入多个等效的键。
QHash	这与QMap的API几乎相同，但提供了显著更快的查找速度。QHash以任意顺序存储其数据。
QMultiHash	这提供了一个基于哈希表的字典，类似于 QHash，但它允许插入多个等效的键。

容器可以嵌套。例如，完全可以使用一个QMap < QString , QList >，其中键类型是QString，值类型是QList 。

容器在单独的头文件中定义，文件名与容器名称相同（例如，）。为了方便，容器在中进行了前向声明。

存储在各种容器中的值可以是任何可赋值的数据类型。要符合条件，类型必须提供复制构造函数和赋值运算符。对于某些操作，还需要默认构造函数。这涵盖了您可能希望存储在容器中的大多数数据类型，包括基本类型如int和double，指针类型，以及Qt数据类型如QString，QDate，和QTime，但不包括QObject或任何QObject子类（QWidget，QDialog，QTimer等）。如果您尝试实例化一个QList ，编译器会抱怨QWidget的复制构造函数和赋值运算符被禁用。如果您想将这些类型的对象存储在容器中，请将它们存储为指针，例如QList 。

这里有一个满足可分配数据类型要求的自定义数据类型示例：

class Employee():

# public
    Employee() {}
    Employee(Employee other)
    Employee operator=(Employee other)
# private
    myName = QString()
    myDateOfBirth = QDate()

如果我们不提供拷贝构造函数或赋值运算符，C++会提供一个默认的实现，该实现会逐个成员进行拷贝。在上面的例子中，这已经足够了。此外，如果你不提供任何构造函数，C++会提供一个默认构造函数，该构造函数会使用默认构造函数初始化其成员。尽管它没有提供任何显式的构造函数或赋值运算符，以下数据类型可以存储在容器中：

class Movie():

    id = int()
    title = QString()
    releaseDate = QDate()

一些容器对它们可以存储的数据类型有额外的要求。例如，QMap 的 Key 类型必须提供 operator<()。这些特殊要求在类的详细描述中有记录。在某些情况下，特定函数有特殊要求；这些要求会在每个函数的基础上进行描述。如果未满足要求，编译器将始终发出错误。

Qt的容器提供了operator<<()和operator>>()，以便它们可以轻松地使用QDataStream进行读写。这意味着存储在容器中的数据类型也必须支持operator<<()和operator>>()。提供这样的支持是直接的；以下是我们如何为上面的Movie结构体实现它：

QDataStream operator<<(QDataStream out, Movie movie)

    out << (quint32)movie.id << movie.title
        << movie.releaseDate
    return out

QDataStream operator>>(QDataStream in, Movie movie)

    id = quint32()
    date = QDate()
    in >> id >> movie.title >> date
    movie.id = (int)id
    movie.releaseDate = date
    return in

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

遍历容器¶

基于范围的for循环¶

基于范围的for循环最好用于容器：

list = {"A", "B", "C", "D"}
for item in list:
   ...

请注意，在非const上下文中使用Qt容器时，隐式共享可能会导致容器的意外分离。为了防止这种情况，请使用std::as_const()：

list = {"A", "B", "C", "D"}
for item in list:
    ...

对于关联容器，这将遍历值。

基于索引的¶

对于在内存中连续存储其项目的顺序容器（例如，QList），可以使用基于索引的迭代：

list = {"A", "B", "C", "D"}
for i in range(0, list.size()):
    auto item = list.at(i)
    ...

迭代器类¶

迭代器提供了一种统一的方式来访问容器中的项目。Qt的容器类提供了两种类型的迭代器：STL风格的迭代器和Java风格的迭代器。当容器中的数据被修改或由于调用非常量成员函数而从隐式共享副本中分离时，这两种类型的迭代器都会失效。

STL风格迭代器¶

STL风格的迭代器自Qt 2.0发布以来就已经可用。它们与Qt和STL的通用算法兼容，并且针对速度进行了优化。

对于每个容器类，有两种STL风格的迭代器类型：一种提供只读访问，另一种提供读写访问。应尽可能使用只读迭代器，因为它们比读写迭代器更快。

容器	只读迭代器	读写迭代器
QList , QStack , QQueue	QList ::const_iterator	QList ::iterator
QSet	QSet ::const_iterator	QSet ::iterator
QMap , QMultiMap	QMap ::const_iterator	QMap ::iterator
QHash , QMultiHash	QHash ::const_iterator	QHash ::iterator

STL迭代器的API是模仿数组中的指针设计的。例如，++操作符将迭代器推进到下一个项目，而*操作符返回迭代器指向的项目。事实上，对于QList和QStack，它们将项目存储在相邻的内存位置，iterator类型只是T *的typedef，而const_iterator类型只是const T *的typedef。

在这次讨论中，我们将专注于QList和QMap。QSet的迭代器类型与QList的迭代器具有完全相同的接口；同样，QHash的迭代器类型与QMap的迭代器具有相同的接口。

这是一个典型的循环，用于按顺序遍历QList < QString >的所有元素并将它们转换为小写：

list = {"A", "B", "C", "D"}
for i in list:
    i = (i).toLower()

STL风格的迭代器直接指向项目。容器的begin()函数返回一个指向容器中第一个项目的迭代器。容器的end()函数返回一个指向容器中最后一个项目之后一个位置的假想项目的迭代器。end()标记了一个无效的位置；它绝不能解引用。它通常用于循环的终止条件。如果列表为空，begin()等于end()，因此我们永远不会执行循环。

下图显示了包含四个项目的列表的有效迭代器位置，用红色箭头表示：

使用STL风格的迭代器向后迭代是通过反向迭代器完成的：

list = {"A", "B", "C", "D"}
for i in list:
    i = i.toLower()

在迄今为止的代码片段中，我们使用了一元运算符 * 来检索存储在某个迭代器位置的项（类型为 QString），然后在其上调用 toLower()。

对于只读访问，你可以使用 const_iterator，cbegin()，和 cend()。例如：

for i in list:
    print(i)

下表总结了STL风格迭代器的API：

表达式	行为
*i	返回当前项
++i	将迭代器推进到下一个项目
i += n	将迭代器前进 n 个项目
--i	将迭代器向后移动一个项目
i -= n	将迭代器向后移动 n 个项目
i - j	返回迭代器 i 和 j 之间的项目数

++ 和 -- 运算符既可以作为前缀（++i, --i）也可以作为后缀（i++, i--）使用。前缀版本会修改迭代器并返回修改后的迭代器的引用；后缀版本在修改迭代器之前会先复制一份迭代器，并返回该副本。在忽略返回值的表达式中，我们建议您使用前缀运算符（++i, --i），因为它们稍微快一些。

对于非常量迭代器类型，一元*运算符的返回值可以用于赋值运算符的左侧。

对于QMap和QHash，*运算符返回项目的值组件。如果你想检索键，可以在迭代器上调用key()。为了对称性，迭代器类型还提供了一个value()函数来检索值。例如，以下是我们如何将QMap中的所有项目打印到控制台的方式：

int> = QMap<int,()
...
for i in map:
    print(i.key(), ':', i.value())

感谢隐式共享，函数按值返回容器的成本非常低。Qt API 包含许多按值返回QList或QStringList的函数（例如，QSplitter::sizes()）。如果你想使用 STL 迭代器遍历这些容器，你应该总是获取容器的一个副本并在副本上进行遍历。例如：

# RIGHT
sizes = splitter.sizes()
for i in sizes:
    ...
# WRONG
for (auto i = splitter.sizes().begin()
        i != splitter.sizes().end(); ++i)
    ...

这个问题不会出现在返回容器常量或非常量引用的函数中。

隐式共享迭代器问题¶

隐式共享对STL风格的迭代器有另一个影响：你应该避免在迭代器在容器上活跃时复制容器。迭代器指向一个内部结构，如果你复制容器，你应该非常小心你的迭代器。例如：

a, = QList()
a.resize(100000) # make a big list filled with 0.

# WRONG way of using the iterator i:
b = a
/*
    Now we should be careful with iterator i since it will point to shared data
    If we do i = 4 then we would change the shared instance (both vectors)
    The behavior differs from STL containers. Avoid doing such things in Qt.
*/
a[0] = 5
/*
    Container a is now detached from the shared data,
    and even though i was an iterator from the container a, it now works as an iterator in b.
    Here the situation is that (i) == 0.
*/
b.clear() # Now the iterator i is completely invalid.
j = i # Undefined behavior!
/*
    The data from b (which i pointed to) is gone.
    This would be well-defined with STL containers (and (i) == 5),
    but with QList self is likely to crash.
*/

上面的例子仅展示了QList的问题，但这个问题存在于所有隐式共享的Qt容器中。

Java风格迭代器¶

Java-Style iterators 是基于Java的迭代器类建模的。新代码应优先使用 STL-Style Iterators 。

Qt 容器与 std 容器的比较¶

Qt 容器	最接近的 std 容器
QList	类似于 std::vector QList 和 QVector 在 Qt 6 中统一了。两者都使用 QVector 的数据模型。QVector 现在是 QList 的别名。 这意味着 QList 不是作为链表实现的，所以如果你需要常数时间的插入、删除、追加或前置操作，请考虑使用 std::list。详情请参见 QList。
QVarLengthArray	类似于 std::array 和 std::vector 的混合体。 出于性能考虑，QVarLengthArray 通常驻留在栈上，除非调整大小。调整大小会自动导致其使用堆。
QStack	类似于 std::stack，继承自 QList 。
QQueue	类似于 std::queue，继承自 QList 。
QSet	类似于 std::unordered_set。在内部，QSet 是通过 QHash 实现的。
QMap	类似于 std::map。
QMultiMap	类似于 std::multimap。
QHash	最类似于 std::unordered_map。
QMultiHash	与 std::unordered_multimap 最为相似。

Qt 容器和标准算法¶

你可以使用Qt容器与来自#include 的函数。

list = {2, 3, 1}
std::sort(list.begin(), list.end())
/*
    Sort the list, now contains { 1, 2, 3 }
*/
std::reverse(list.begin(), list.end())
/*
    Reverse the list, now contains { 3, 2, 1 }
*/
even_elements =
        std::count_if(list.begin(), list.end(), [](int element) { return (element % 2 == 0); })
/*
    Count how many elements that are even numbers, 1
*/

其他类似容器的类¶

Qt 包含其他在某些方面类似于容器的模板类。这些类不提供迭代器，并且不能与 foreach 关键字一起使用。

• QCache 提供了一个缓存，用于存储与类型为 Key 的键相关联的特定类型 T 的对象。

• QContiguousCache 提供了一种高效的方式来缓存通常以连续方式访问的数据。

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

算法复杂度¶

算法复杂度关注的是随着容器中项目数量的增加，每个函数的速度（或慢速）如何变化。例如，在std::list的中间插入一个项目是一个非常快速的操作，无论列表中存储了多少项目。另一方面，如果QList包含许多项目，那么在QList的中间插入一个项目可能会非常昂贵，因为一半的项目必须在内存中移动一个位置。

为了描述算法复杂度，我们使用以下术语，基于“大O”符号：

• 常数时间: O(1)。如果一个函数无论容器中有多少项都需要相同的时间，那么它就被称为在常数时间内运行。一个例子是push_back()。

• 对数时间： O(log n)。在对数时间内运行的函数是指其运行时间与容器中项目数量的对数成正比的函数。一个例子是二分查找算法。

• 线性时间： O(n)。一个在线性时间内运行的函数将执行与容器中存储的项目数量成正比的时间。一个例子是 insert()。

• 线性对数时间： O(n log n)。一个在线性对数时间内运行的函数在渐进意义上比线性时间函数慢，但比二次时间函数快。

• 二次时间： O(n²)。一个二次时间函数的执行时间与容器中存储的项目数量的平方成正比。

下表总结了顺序容器 QList 的算法复杂度：

	索引查找	插入	前置	追加
QList	O(1)	O(n)	O(n)	摊销 O(1)

在表中，“Amort.”代表“摊销行为”。例如，“Amort. O(1)”意味着如果你只调用该函数一次，你可能会得到O(n)的行为，但如果你多次调用它（例如，n次），平均行为将是O(1)。

下表总结了Qt的关联容器和集合的算法复杂度：

键查找 +===========+=========== |平均情况 |最坏情况		插入 ===========+=========== 平均情况 |最坏情况
QMap	O(log n)	O(log n)	O(log n)	O(log n)
QMultiMap	O(log n)	O(log n)	O(log n)	O(log n)
QHash	摊销 O(1)	O(n)	摊销 O(1)	O(n)
QSet	摊销 O(1)	O(n)	摊销 O(1)	O(n)

使用QList、QHash和QSet时，追加项目的性能是摊销的O(log n)。通过在插入项目之前调用reserve()、reserve()或reserve()并传入预期的项目数量，可以将其降低到O(1)。下一节将更深入地讨论这个话题。

原始类型和可重定位类型的优化¶

如果存储的元素是可重定位的甚至是原始的，Qt容器可以使用优化的代码路径。然而，并非在所有情况下都能检测到类型是原始的还是可重定位的。您可以通过使用带有Q_PRIMITIVE_TYPE标志或Q_RELOCATABLE_TYPE标志的Q_DECLARE_TYPEINFO宏来声明您的类型是原始的或可重定位的。有关更多详细信息和用法示例，请参阅Q_DECLARE_TYPEINFO的文档。

如果你不使用Q_DECLARE_TYPEINFO，Qt将使用std::is_trivial_v来识别基本类型，并且需要同时满足std::is_trivially_copyable_v和std::is_trivially_destructible_v来识别可重定位类型。这始终是一个安全的选择，尽管可能性能不是最优的。

增长策略¶

QList , QString , 和 QByteArray 将它们的项目连续存储在内存中；QHash 保持一个哈希表，其大小与哈希中的项目数量成正比。为了避免每次在容器末尾添加项目时重新分配数据，这些类通常会分配比必要更多的内存。

考虑以下代码，它从另一个QString构建一个QString：

def onlyLetters(in):

    out = QString()
    for j in range(0, in.size()):
        if in.at(j).isLetter():
            out += in.at(j)

    return out

我们通过一次追加一个字符来动态构建字符串 out。假设我们向 QString 字符串追加了15000个字符。当 QString 空间不足时，会发生以下11次重新分配（可能的总次数为15000）：8, 24, 56, 120, 248, 504, 1016, 2040, 4088, 8184, 16376。最后，QString 分配了16376个Unicode字符，其中15000个被占用。

上面的值可能看起来有点奇怪，但有一个指导原则。它每次通过将大小加倍来前进。更准确地说，它前进到下一个二的幂，减去16字节。16字节对应八个字符，因为QString在内部使用UTF-16。

QByteArray 使用与 QString 相同的算法，但16字节对应16个字符。

QList 也使用该算法，但16字节对应于16/sizeof(T)个元素。

QHash 是一个完全不同的情况。QHash 的内部哈希表以二的幂次增长，每次增长时，项目会被重新定位到一个新的桶中，计算方式为 qHash (key) % capacity()（桶的数量）。这个说明同样适用于 QSet 和 QCache 。

对于大多数应用程序，Qt提供的默认增长算法已经足够。如果你需要更多的控制，QList , QHash , QSet , QString 和 QByteArray 提供了一组函数，允许你检查和指定用于存储项目的内存大小：

• capacity() 返回已分配内存的项目数量（对于 QHash 和 QSet，返回哈希表中的桶数量）。

• reserve (size) 显式地为 size 个项目预分配内存。

• squeeze() 释放不需要用于存储项目的任何内存。

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