容器类

简介

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

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

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

容器提供了用于遍历的迭代器。最有效的迭代器是 STL-style iterators，它们可以与 Qt 的和 STL 的 通用算法一起使用。提供 Java-style Iterators 以支持向后兼容。

QList<int> list = {1, 2, 3, 4, 4, 5};
QSet<int> set(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 类提供了在有限缓存存储中高效哈希查找对象的解决方案。

容器可以嵌套。例如，使用一个 QMap<<a href="qstring.html" translate="no">QString，QList<int>> 完全可行，其中键类型是 QString，值类型是 QList<int>。

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

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

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

class Employee
{
public:
    Employee() {}
    Employee(const Employee &other);

    Employee &operator=(const Employee &other);

private:
    QString myName;
    QDate myDateOfBirth;
};

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

struct Movie
{
    int id;
    QString title;
    QDate releaseDate;
};

某些容器对它们可以存储的数据类型有额外的要求。例如，QMap<Key, T> 的键类型必须提供 operator<()。这类特殊要求在类的详细说明中有详细说明。在某些情况下，特定函数有特殊要求；这些是按函数分别描述的。如果不符合要求，编译器将始终发出错误。

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

QDataStream &operator<<(QDataStream &out, const Movie &movie)
{
    out << (quint32)movie.id << movie.title
        << movie.releaseDate;
    return out;
}

QDataStream &operator>>(QDataStream &in, Movie &movie)
{
    quint32 id;
    QDate date;

    in >> id >> movie.title >> date;
    movie.id = (int)id;
    movie.releaseDate = date;
    return in;
}

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

遍历容器

基于范围的 for

基于范围的 for 应尽可能用于容器

QList<QString> list = {"A", "B", "C", "D"};
for (const auto &item : list) {
   ...
}

请注意，在非常量上下文中使用 Qt 容器时，隐式共享 可能会执行一个不希望从容器中分离的操作。为了防止这种情况，请使用 std::as_const()

QList<QString> list = {"A", "B", "C", "D"};
for (const auto &item : std::as_const(list)) {
    ...
}

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

基于索引

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

QList<QString> list = {"A", "B", "C", "D"};
for (qsizetype i = 0; i < list.size(); ++i) {
    const auto &item = list.at(i);
    ...
}

迭代器类

迭代器提供了一种一致的方式来访问容器中的元素。Qt的容器类提供了两种类型的迭代器：STL风格的迭代器和Java风格的迭代器。当容器中的数据被修改或因调用非const成员函数而从隐式共享副本中分离出来时，两种类型的迭代器都会失效。

STL风格迭代器

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

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

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

在本讨论中，我们将集中讨论QList和QMap。QSet的迭代器与QList的迭代器具有相同的接口；类似地，QHash的迭代器与QMap的迭代器具有相同的接口。

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

QList<QString> list = {"A", "B", "C", "D"};

for (auto i = list.begin(), end = list.end(); i != end; ++i)
    *i = (*i).toLower();

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

以下图显示了包含四个元素的列表的有效迭代器位置，以红色箭头表示

使用反向迭代器可以以STL风格迭代器逆向遍历

QList<QString> list = {"A", "B", "C", "D"};

for (auto i = list.rbegin(), rend = list.rend(); i != rend; ++i)
    *i = i->toLower();

在之前的代码片段中，我们使用了一元*操作符来检索一定迭代器位置上的元素（类型为QString），然后在其上调用QString::toLower()。

对于只读访问，您可以使用const_iterator，cbegin()，以及cend()。例如

for (auto i = list.cbegin(), end = list.cend(); i != end; ++i)
    qDebug() << *i;

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

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

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

对于QMap和QHash，*运算符返回项目的值部分。如果您想获取键，请在迭代器上调用key()。为了对称，迭代器类型还提供value()函数来获取值。例如，以下是打印QMap中所有项目到控制台的方法：

QMap<int, int> map;
...
for (auto i = map.cbegin(), end = map.cend(); i != end; ++i)
    qDebug() << i.key() << ':' << i.value();

由于隐式共享，函数按值返回容器成本非常低。Qt API包含数十个函数，每个函数按值返回一个QList或QStringList（例如，QSplitter::sizes()()）。如果您想使用STL迭代器遍历这些，应始终复制容器并遍历副本。例如：

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

// WRONG
for (auto i = splitter->sizes().begin();
        i != splitter->sizes().end(); ++i)
    ...

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

隐式共享迭代器问题

隐式共享对STL风格迭代器有另一个影响：在迭代器处于活动状态时，应避免复制容器。迭代器指向内部结构，如果您复制容器，应非常小心地处理迭代器。例如：

QList<int> a, b;
a.resize(100000); // make a big list filled with 0.

QList<int>::iterator i = a.begin();
// 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.

int 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 this is likely to crash.
*/

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

Java风格迭代器

Java风格迭代器是模仿Java的迭代器类构建的。新代码应首选STL风格迭代器。

Qt容器与std容器比较

Qt 容器和 std 算法

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

QList<int> 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 }
*/

int 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> 为存储与类型为 Key 的键关联的类型为 T 的对象提供缓存。
• QContiguousCache<T> 为以连续方式访问的数据提供高效的缓存方法。

与 Qt 的模板容器竞争的一些额外非模板类型包括 QBitArray、QByteArray、QString 和 QStringList。

算法复杂度

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

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

• 常数时间： O(1)。如果一个函数无论容器中有多少个项目都花费相同的 amount of time，则称该函数以常数时间运行。一个例子是 QList::push_back。
• 对数时间： O(log n)。对数时间的函数其运行时间是项目数量的对数的比例。一个例子是对数搜索算法。
• 线性时间： O(n)。线性时间的函数将执行与存储在容器中的项目数成正比的时间。一个例子是 QList::insert。
• 线性对数时间： O(n log n)。线性对数时间的函数与线性时间的函数相比较慢，但比二次时间的函数要快。
• 二次时间： O(n²)。二次时间的函数执行时间是项目数量的平方的比例。

以下表格总结了连续容器 QList<T> 的算法复杂度

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

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

使用 QList，QHash 和 QSet，在追加项目时性能为摊销 O(log n)。通过在插入项目之前预分配预期的项目数量使用 QList::reserve()，QHash::reserve() 或 QSet::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

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

我们通过每次向其中追加一个字符来动态构建字符串 out。假设我们将 15000 个字符追加到 QString 字符串中。然后，当 QString 用尽空间时，以下 11 次重新分配（在可能的 15000 次重新分配中）发生：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) % QHash::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() 来释放额外预分配的内存。