集装箱类别

简介

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

与 STL 容器相比，这些容器类更轻便、更安全、更易用。如果您不熟悉 STL，或者喜欢用 "Qt 方式 "做事，可以使用这些类来代替 STL 类。

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

容器提供用于遍历的迭代器。STL 风格的迭代器是最高效的迭代器，可与 Qt XML 和 STL 的generic algorithms 一起使用。为了向后兼容，我们提供了Java 风格的迭代器。

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 是提供后进先出和先进先出语义的便利类。

Qt 还提供了这些关联容器：QMap,QMultiMap,QHash,QMultiHash, 和QSet 。Multi "容器可方便地支持与单个键关联的多个值。散列 "容器通过使用散列函数而不是对排序集进行二进制搜索，提供了更快的查找速度。

作为特例，QCache 和QContiguousCache 类可在有限的缓存中对对象进行高效的哈希查找。

容器可以嵌套。例如，完全可以使用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(const Employee &other);

    Employee &operator=(const Employee &other);

private:
    QString myName;
    QDate myDateOfBirth;
};

如果我们不提供复制构造函数或赋值操作符，C++ 会提供一个默认实现，执行逐个成员复制。在上面的例子中，这就足够了。另外，如果不提供任何构造函数，C++ 也会提供一个默认构造函数，使用默认构造函数初始化其成员。虽然 C++ 没有提供任何显式构造函数或赋值操作符，但以下数据类型可以存储在容器中：

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

某些容器对其可存储的数据类型有额外要求。例如，QMap<Key, T> 的 Key 类型必须提供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() 会在指定 key 不在 map 中时返回默认构造值。对于大多数值类型来说，这仅仅意味着使用默认构造函数创建了一个值（例如QString 的空字符串）。但对于像int 和double 这样的原始类型以及指针类型，C++ 语言没有指定任何初始化；在这种情况下，Qt XML 的容器会自动将值初始化为 0。

对容器进行遍历

基于范围的

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

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

请注意，在非 const 上下文中使用 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 风格迭代器

自 Qt 2.0 发布以来，STL 样式的迭代器一直可用。它们与 Qt XML 和 STL 的generic algorithms 兼容，并对速度进行了优化。

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

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

在本讨论中，我们将集中讨论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()标志着一个无效的位置；它绝不能被取消引用。它通常用于循环的中断条件。如果列表为空，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(autoi=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(autoi=map.cbegin(),end=map.cend(); i!=end;++i)    qDebug() << i.key() << ':' << i.value();

由于隐式共享，函数按值返回容器的成本非常低。Qt XML 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)
    ...

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

隐式共享迭代器问题

隐式共享对 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 容器与标准容器的比较

Qt 容器和 std 算法

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

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 中间插入一个项目可能会非常昂贵，因为有一半的项目必须在内存中移动一个位置。

为了描述算法复杂度，我们使用了以下基于 "big Oh "符号的术语：

• 恒定时间：O(1).如果一个函数无论在容器中存在多少项目，所需的时间都是相同的，那么这个函数就可以说是在恒定时间内运行的。QList::push_back() 就是一个例子。
• 对数时间：O(logn)。运行时间为对数的函数是指其运行时间与容器中条目数的对数成正比的函数。二进制搜索算法就是一个例子。
• 线性时间：O(n)。以线性时间运行的函数，其执行时间与容器中存储的条目数成正比。QList::insert() 就是一个例子。
• 线性对数时间：O（nlogn）。在线性-对数时间内运行的函数在渐近上比线性时间函数慢，但比二次时间函数快。
• 二次时间：O(n²)。二次时间函数的执行时间与容器中存储的项目数的平方成正比。

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

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

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

使用QList 、QHash 和QSet ，追加项目的性能摊销为 O(logn)。在插入条目之前，调用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 XML 将使用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 。假设我们向QString 字符串追加了 15000 个字符。当QString 的空间耗尽时，会发生以下 11 次重新分配（在可能的 15000 次重新分配中）：8、24、56、120、248、504、1016、2040、4088、8184、16376。最后，QString 共分配了 16376 个 Unicode 字符，其中 15000 个已被占用。

上述数值看起来有点奇怪，但有一个指导原则。每次前进时，大小都会加倍。更准确地说，是前进到 2 的下一个幂，减去 16 字节。16 字节对应 8 个字符，因为QString 内部使用 UTF-16。

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

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

QHash<Key, T> 则完全不同。QHash<Key, T> 的内部哈希表以 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）显式地为大小项预先分配内存。
• squeeze() 释放不需要用于存储项目的内存。

如果知道要在容器中存储大约多少个项目，可以先调用reserve() ，当填充完容器后，再调用squeeze() 释放多余的预分配内存。