警告

本节包含自动从C++转换为Python的代码段，可能包含错误。

容器类

基于Qt模板的容器类。

简介

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

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

容器类是无处不是可共享的，它们是可重入的，并且针对速度、低内存消耗和最小化内联代码扩展进行了优化，从而产生了更小的可执行文件。此外，当所有线程用作只读容器时，它们是线程安全的。

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

注意

自Qt 5.14以来，大多数容器类都提供了范围构造函数。QMultiMap是一个值得注意的例外。鼓励使用它们来替代Qt 5中已弃用的许多from/to方法。例如

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>	这是最常用的容器类之一。它存储了一个给定类型（T）的值列表，该列表可以通过索引访问。内部，它将给定类型的值存储在内存中相邻的位置的数组中。在列表的开始或中间插入通常会相当慢，因为这可能导致大量项目在内存中移动一个位置。
QVarLengthArray<T, Prealloc>	这提供了一种低级别的可变长度数组。在速度极为重要的地方，它可以替代 QList。
QStack<T>	这是 QList 的一个便捷子类，提供了“后进先出”（LIFO）语义。它新增以下函数到 QList：push()、pop() 和 top()。
QQueue<T>	这是 QList 的一个便捷子类，提供了“先进先出”（FIFO）语义。它新增以下函数到 QList：enqueue()、dequeue() 和 head()。
QSet<T>	这提供了一个具有快速查找的单值数学集合。
QMap<Key, T>	这提供了一种将类型为 Key 的键映射到类型为 T 的值的字典（关联数组）。通常，每个键都与单个值关联。QMap 按键顺序存储其数据；如果顺序不重要，则 QHash 是一个更快的替代方案。
QMultiMap<Key, T>	这是QMap的便捷子类，为多值映射提供了良好的接口，即一个键可以与多个值关联。
QHash <键，T>	其API几乎与QMap相同，但提供显著更快的查找速度。QHash以任意顺序存储其数据。
QMultiHash <键，T>	这是QHash的便捷子类，为多值哈希提供了良好的接口。

容器可以嵌套。例如，可以使用QMap < QString ，QList <int>>，其中键类型为QString，值类型为QList <int>。

容器定义在具有与容器相同名称的单个头文件中（例如，<QList>）。为了方便，容器在<QtContainerFwd>中进行了前置声明。

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

以下是一个符合可赋值数据类型要求的自定义数据类型示例

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, T> 的键类型必须提供 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 格式迭代器。当容器中的数据因调用了非 const 成员函数而发生修改，或从 隐式共享副本 中分离时，这两种类型的迭代器都会被使失效。

STL-风格迭代器

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

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

容器	只读迭代器	读写迭代器
QList <T>，QStack <T>，QQueue <T>	QList<T>::const_iterator	QList<T>::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是基于数组中的指针模型设计的。例如，++运算符将迭代器移动到下一个元素，而*运算符返回迭代器指向的元素。实际上，对于存储元素在相邻内存位置的QList和QStack，迭代器类型只是的别名，而const_iterator类型只是的别名。

在本讨论中，我们将重点讨论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），因为这些稍微快一些。

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

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

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

由于隐式共享（implicit sharing），函数返回一个容器非常便宜。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)
    ...

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

隐式共享迭代器问题

隐式共享 对 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 风格迭代器 是基于 Java 的迭代器类模型。新的代码应优先使用 STL 风格迭代器。

Qt 容器与 std 容器比较

Qt 容器	最近的 std 容器
QList<T>	类似于 std::vector QList 和 QVector 在 Qt 6 中被统一。两者都使用来自 QVector 的数据模型。现在 QVector 是 QList 的别名。 这意味着 QList 不是作为链表实现的，所以如果你需要恒定时间插入、删除、追加或预追加，应考虑使用 std::list。有关详情，请参见 QList。
QVarLengthArray<T, Prealloc>	类似于 std::array 和 std::vector 的混合体。 出于性能考虑，QVarLengthArray 除非调整大小，否则位于栈上。调整它自动导致它使用堆。
QStack<T>	类似于 std::stack，继承自 QList。
QQueue<T>	类似于 std::queue，继承自 QList。
QSet<T>	类似于 std::unordered_set。内部，QSet 使用 QHash 实现。
QMap<Key, T>	类似于 std::map。
QMultiMap<Key, T>	类似于 std::multimap。
QHash <键，T>	与 std::unordered_map 最相似。
QMultiHash <键，T>	与 std::unordered_multimap 最相似。

Qt 容器与 std 算法

你可以使用 Qt 容器与 #include <algorithm> 中的函数。

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 <T> 的算法复杂度

	索引查找	插入	预加	附加
QList<T>	O(1)	O(n)	O(n)	摊销. O(1)

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

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

键查找 +===========+=========== |平均 |最坏情况			插入 ===========+=========== 平均 |最坏情况
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 <键，T>	摊销. 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<T> 来识别原始类型，并需要 std::is_trivially_copyable_v<T> 和 std::is_trivially_destructible_v<T> 来识别可移动类型。这是一个始终安全的选择，也许不是最优的性能。

增长策略

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

考虑以下代码，它从另一个 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 次中的 11 次）：8, 24, 56, 120, 248, 504, 1016, 2040, 4088, 8184, 16376。最后，QString 已分配了 16376 个 Unicode 字符，其中 15000 个被占用。

上述值可能看起来有些奇怪，但仍有一个指导原则。每当它增长时，它都会翻倍。更准确地说，它会增长到下一个2的幂，然后减去 16 字节。16 字节对应于八个字符，因为 QString 在内部使用 UTF-16。

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

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

QHash <Key, T> 完全不同。 QHash 的内部哈希表按2的次幂增长，每次增长时，项目将重新定位到一个新的桶中，计算公式为 qHash (key) % capacity()（桶的数量）。此说明同样适用于 QSet <T> 和 QCache <Key, T>。

对于大多数应用程序，Qt提供的默认增长算法已经足够。如果您需要更多控制，QList <T>、QHash <Key, T>、QSet <T>、QString 和 QByteArray 提供了三个函数，允许您检查和指定用于存储项的内存量

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

• reserve (size) 明确为 size 个项目预分配内存。

• squeeze() 释放存储项所需的任何内存。

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