（38）存储容器
最后更新于：2022-04-01 06:29:39
#（38）：存储容器
存储容器（containers）有时候也被称为集合（collections），是能够在内存中存储其它特定类型的对象，通常是一些常用的数据结构，一般是通用模板类的形式。C++ 提供了一套完整的解决方案，作为标准模板库（Standard Template Library）的组成部分，也就是常说的 STL。
Qt 提供了另外一套基于模板的容器类。相比 STL，这些容器类通常更轻量、更安全、更容易使用。如果你对 STL 不大熟悉，或者更喜欢 Qt 风格的 API，那么你就应该选择使用这些类。当然，你也可以在 Qt 中使用 STL 容器，没有任何问题。
本章的目的，是让你能够选择使用哪个容器，而不是告诉你这个类都哪些函数。这个问题可以在文档中找到更清晰的回答。
Qt 的容器类都不继承`QObject`，都提供了隐式数据共享、不可变的特性，并且为速度做了优化，具有较低的内存占用量等。另外一点比较重要的，它们是线程安全的。这些容器类是平台无关的，即不因编译器的不同而具有不同的实现；隐式数据共享，有时也被称作“写时复制（copy on write）”，这种技术允许在容器类中使用传值参数，但却不会出现额外的性能损失。遍历是容器类的重要操作。Qt 容器类提供了类似 Java 的遍历器语法，同样也提供了类似 STL 的遍历器语法，以方便用户选择自己习惯的编码方式。相比而言，Java 风格的遍历器更易用，是一种高层次的函数；而 STL 风格的遍历器更高效，同时能够支持 Qt 和 STL 的通用算法。最后一点，在一些嵌入式平台，STL 往往是不可用的，这时你就只能使用 Qt 提供的容器类，除非你想自己创建。顺便提一句，除了遍历器，Qt 还提供了自己的 foreach 语法（C++ 11 也提供了类似的语法，但有所区别，详见[这里](http://www.devbean.net/2012/06/cpp11-in-qt4/)的 foreach 循环一节）。
Qt 提供了顺序存储容器：`QList`，`QLinkedList`，`QVector`，`QStack`和`QQueue`。对于绝大多数应用程序，`QList`是最好的选择。虽然它是基于数组实现的列表，但它提供了快速的向前添加和向后追加的操作。如果你需要链表，可以使用`QLinkedList`。如果你希望所有元素占用连续地址空间，可以选择`QVector`。`QStack`和`QQueue`则是 LIFO 和 FIFO 的。
Qt 还提供了关联容器：`QMap`，`QMultiMap`，`QHash`，`QMultiHash`和`QSet`。带有“Multi”字样的容器支持在一个键上面关联多个值。“Hash”容器提供了基于散列函数的更快的查找，而非 Hash 容器则是基于二分搜索的有序集合。
另外两个特例：`QCache`和`QContiguousCache`提供了在有限缓存空间中的高效 hash 查找。
我们将 Qt 提供的各个容器类总结如下：
* `QList<T>`：这是至今为止提供的最通用的容器类。它将给定的类型 T 的对象以列表的形式进行存储，与一个整型的索引关联。`QList`在内部使用数组实现，同时提供基于索引的快速访问。我们可以使用 `QList::append()`和`QList::prepend()`在列表尾部或头部添加元素，也可以使用`QList::insert()`在中间插入。相比其它容器类，`QList`专门为这种修改操作作了优化。`QStringList`继承自`QList<QString>`。
* `QLinkedList<T>`：类似于 `QList`，除了它是使用遍历器进行遍历，而不是基于整数索引的随机访问。对于在中部插入大量数据，它的性能要优于`QList`。同时具有更好的遍历器语义（只要数据元素存在，`QLinkedList`的遍历器就会指向一个合法元素，相比而言，当插入或删除数据时，`QList`的遍历器就会指向一个非法值）。
* `QVector<T>`：用于在内存的连续区存储一系列给定类型的值。在头部或中间插入数据可能会非常慢，因为这会引起大量数据在内存中的移动。
* `QStack<T>`：这是`QVector`的子类，提供了后进先出（LIFO）语义。相比`QVector`，它提供了额外的函数：`push()`，`pop()`和`top()`。
* `QQueue<T>`：这是`QList`的子类，提供了先进先出（FIFO）语义。相比`QList`，它提供了额外的函数：`enqueue()`，`dequeue()`和`head()`。
* `QSet<T>`：提供单值的数学上面的集合，具有快速的查找性能。
* `QMap<Key, T>`：提供了字典数据结构（关联数组），将类型 T 的值同类型 Key 的键关联起来。通常，每个键与一个值关联。`QMap`以键的顺序存储数据；如果顺序无关，`QHash`提供了更好的性能。
* `QMultiMap<Key, T>`：这是`QMap`的子类，提供了多值映射：一个键可以与多个值关联。
* `QHash<Key, T>`：该类同`QMap`的接口几乎相同，但是提供了更快的查找。`QHash`以字母顺序存储数据。
* `QMultiHash<Key, T>`：这是`QHash`的子类，提供了多值散列。
所有的容器都可以嵌套。例如，`QMap<QString, QList<int> >`是一个映射，其键是`QString`类型，值是`QList<int>`类型，也就是说，每个值都可以存储多个 int。这里需要注意的是，C++ 编译器会将连续的两个 > 当做输入重定向运算符，因此，这里的两个 > 中间必须有一个空格。
能够存储在容器中的数据必须是**可赋值数据类型**。所谓可赋值数据类型，是指具有默认构造函数、拷贝构造函数和赋值运算符的类型。绝大多数数据类型，包括基本类型，比如 int 和 double，指针，Qt 数据类型，例如`QString`、`QDate`和`QTime`，都是可赋值数据类型。但是，`QObject`及其子类（`QWidget`、`QTimer`等）都不是。也就是说，你不能使用`QList<QWidget>`这种容器，因为`QWidget`的拷贝构造函数和赋值运算符不可用。如果你需要这种类型的容器，只能存储其指针，也就是`QList<QWidget *>`。
如果要使用`QMap`或者`QHash`，作为键的类型必须提供额外的辅助函数。`QMap`的键必须提供`operator<()`重载，`QHash`的键必须提供`operator==()`重载和一个名字是`qHash()`的全局函数。
作为例子，我们考虑如下的代码：
~~~
struct Movie
{
int id;
QString title;
QDate releaseDate;
};
~~~
作为 struct，我们当做纯数据类使用。这个类没有额外的构造函数，因此编译器会为我们生成一个默认构造函数。同时，编译器还会生成默认的拷贝构造函数和赋值运算符。这就满足了将其放入容器类存储的条件：
~~~
QList<Movie> movs;
~~~
Qt 容器类可以直接使用`QDataStream`进行存取。此时，容器中所存储的类型必须也能够使用`QDataStream`进行存储。这意味着，我们需要重载`operator<<()`和`operator>>()`运算符：
~~~
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;
}
~~~
根据数据结构的相关内容，我们有必要对这些容器类的算法复杂性进行定量分析。算法复杂度关心的是在数据量增长时，容器的每一个函数究竟有多快（或者多慢）。例如，向`QLinkedList`中部插入数据是一个相当快的操作，并且与`QLinkedList`中已经存储的数据量无关。另一方面，如果`QVector`中已经保存了大量数据，向`QVector`中部插入数据会非常慢，因为在内存中，有一半的数据必须移动位置。为了描述算法复杂度，我们引入 O 记号（大写字母 O，读作“大 O”）：
* 常量时间：O(1)。如果一个函数的运行时间与容器中数据量无关，我们说这个函数是常量时间的。`QLinkedList::insert()`就是常量时间的。
* 对数时间：O(log n)。如果一个函数的运行时间是容器数据量的对数关系，我们说这个函数是对数时间的。`qBinaryFind()`就是对数时间的。
* 线性时间：O(n)。如果一个函数的运行时间是容器数据量的线性关系，也就是说直接与数量相关，我们说这个函数是限行时间的。`QVector::insert()`就是线性时间的。
* 线性对数时间：O(n log n)。线性对数时间要比线性时间慢，但是要比平方时间快。
* 平方时间：O(n²)。平方时间与容器数据量的平方关系。
基于上面的表示，我们来看看 Qt 顺序容器的算法复杂度：
| 查找 | 插入 | 前方添加 | 后方追加 || -- |
| -- | -- | --| -- |
| `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) |
上表中，所谓“统计”，意思是统计意义上的数据。例如“统计 O(1)”是说，如果只调用一次，其运行时间是 O(n)，但是如果调用多次（例如 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<T>`、`QString`和`QByteArray`在连续内存空间中存储数据。`QList<T>`维护指向其数据的指针数组，提供基于索引的快速访问（如果 T 就是指针类型，或者是与指针大小相同的其它类型，那么 QList 的内部数组中存的就是其实际值，而不是其指针）。`QHash<Key, T>`维护一张散列表，其大小与散列中数据量相同。为避免每次插入数据都要重新分配数据空间，这些类都提供了多余实际值的数据位。
我们通过下面的代码来了解这一算法：
~~~
QString onlyLetters(const QString &in)
{
QString out;
for (int j = 0; j < in.size(); ++j) {
if (in[j].isLetter())
out += in[j];
}
return out;
}
~~~
我们创建了一个字符串，每次动态追加一个字符。假设我们需要追加 15000 个字符。在算法运行过程中，当达到以下空间时，会进行重新分配内存空间，一共会有 18 次：4，8，12，16，20，52，116，244，500，1012，2036，4084，6132，8180，10228，12276，14324，16372。最后，这个 out 对象一共有 16372 个 Unicode 字符，其中 15000 个是有实际数据的。
上面的分配数据有些奇怪，其实是有章可循的：
* `QString`每次分配 4 个字符，直到达到 20。
* 在 20 到 4084 期间，每次分配大约一倍。准确地说，每次会分配下一个 2 的幂减 12。（某些内存分配器在分配 2 的幂数时会有非常差的性能，因为他们会占用某些字节做预订）
* 自 4084 起，每次多分配 2048 个字符（4096 字节）。这是有特定意义的，因为现代操作系统在重新分配一个缓存时，不会复制整个数据；物理内存页只是简单地被重新排序，只有第一页和最后一页的数据会被复制。
`QByteArray`和`QList<T>`实际算法与`QString`非常类似。
对于那些能够使用`memcry()`（包括基本的 C++ 类型，指针类型和 Qt 的共享类）函数在内存中移动的数据类型，`QVector<T>`也使用了类似的算法；对于那些只能使用拷贝构造函数和析构函数才能移动的数据类型，使用的是另外一套算法。由于后者的消耗更高，所以`QVector<T>`减少了超出空间时每次所要分配的额外内存数。
`QHash<Key, T>`则是完全不同的形式。`QHash`的内部散列表每次会增加 2 的幂数；每次增加时，所有数据都要重新分配到新的桶中，其计算公式是`qHash(key) % QHash::capacity()`（`QHash::capacity()`就是桶的数量）。这种算法同样适用于 `QSet<T>`和`QCache<Key, T>`。如果你不明白“桶”的概念，请查阅数据结构的相关内容。
对于大多数应用程序。Qt 默认的增长算法已经足够。如果你需要额外的控制，`QVector<T>`、`QHash<Key, T>`、`QSet<T>`、`QString`和`QByteArray`提供了一系列函数，用于检测和指定究竟要分配多少内存：
* `capacity()`：返回实际已经分配内存的元素数目（对于`QHash`和`QSet`，则是散列表中桶的个数）
* `reserve(size)`：为指定数目的元素显式地预分配内存。
* `squeeze()`：释放那些不需要真实存储数据的内存空间。
如果你知道容器大约有多少数据，那么你可以通过调用`reserve()`函数来减少内存占用。如果已经将所有数据全部存入容器，则可以调用`squeeze()`函数，释放所有未使用的预分配空间。