Qt学习之路第38篇存储容器

兰博

Qt学习之路第38篇存储容器 [复制链接]

存储容器（containers）有时候也被称为集合（collections），是能够在内存中存储其它特定类型的对象，通常是一些常用的数据结构，一般是通用模板类的形式。C++ 提供了一套完整的解决方案，作为标准模板库（Standard Template Library）的组成部分，也就是常说的 STL。

Qt 提供了另外一套基于模板的容器类。相比 STL，这些容器类通常更轻量、更安全、更容易使用。如果你对 STL 不大熟悉，或者更喜欢 Qt 风格的 API，那么你就应该选择使用这些类。当然，你也可以在 Qt 中使用 STL 容器，没有任何问题。

本章的目的，是让你能够选择使用哪个容器，而不是告诉你这个类都哪些函数。这个问题可以在文档中找到更清晰的回答。

Qt 的容器类提供了隐式数据共享、不可变的特性，并且为速度做了优化，具有较低的内存占用量等。另外一点比较重要的，它们是线程安全的。这些容器类是平台无关的，即不因编译器的不同而具有不同的实现；隐式数据共享，有时也被称作“写时复制（copy on write）”，这种技术允许在容器类中使用传值参数，但却不会出现额外的性能损失。遍历是容器类的重要操作。Qt 容器类提供了类似 Java 的遍历器语法，同样也提供了类似 STL 的遍历器语法，以方便用户选择自己习惯的编码方式。相比而言，Java 风格的遍历器更易用，是一种高层次的函数；而 STL 风格的遍历器更高效，同时能够支持 Qt 和 STL 的通用算法。最后一点，在一些嵌入式平台，STL 往往是不可用的，这时你就只能使用 Qt 提供的容器类，除非你想自己创建。顺便提一句，除了遍历器，Qt 还提供了自己的 foreach 语法（C++ 11 也提供了类似的语法，但有所区别，详见这里的 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 的对象以列表的形式进行存储，与一个整型的索引关联。QList 在内部使用数组实现，同时提供基于索引的快速访问。我们可以使用 QList::append() 和 QList::prepend() 在列表尾部或头部添加元素，也可以使用 QList::insert() 在中间插入。相比其它容器类，QList 专门为这种修改操作作了优化。QStringList 继承自 QList。
QLinkedList：类似于 QList，除了它是使用遍历器进行遍历，而不是基于整数索引的随机访问。对于在中部插入大量数据，它的性能要优于 QList。同时具有更好的遍历器语义（只要数据元素存在，QLinkedList 的遍历器就会指向一个合法元素，相比而言，当插入或删除数据时，QList 的遍历器就会指向一个非法值）。
QVector：用于在内存的连续区存储一系列给定类型的值。在头部或中间插入数据可能会非常慢，因为这会引起大量数据在内存中的移动。
QStack：这是 QVector 的子类，提供了后进先出（LIFO）语义。相比 QVector，它提供了额外的函数：push()，pop() 和 top()。
QQueue：这是 QList 的子类，提供了先进先出（FIFO）语义。相比 QList，它提供了额外的函数：enqueue()，dequeue() 和 head()。
QSet：提供单值的数学上面的集合，具有快速的查找性能。
QMap：提供了字典数据结构（关联数组），将类型 T 的值同类型 Key 的键关联起来。通常，每个键与一个值关联。QMap 以键的顺序存储数据；如果顺序无关，QHash 提供了更好的性能。
QMultiMap：这是 QMap 的子类，提供了多值映射：一个键可以与多个值关联。
QHash：该类同 QMap 的接口几乎相同，但是提供了更快的查找。QHash 以字母顺序存储数据。
QMultiHash：这是 QHash 的子类，提供了多值散列。

所有的容器都可以嵌套。例如，QMap > 是一个映射，其键是 QString 类型，值是 QList 类型，也就是说，每个值都可以存储多个 int。这里需要注意的是，C++ 编译器会将连续的两个 > 当做输入重定向运算符，因此，这里的两个 > 中间必须有一个空格。

能够存储在容器中的数据必须是可赋值数据类型。所谓可赋值数据类型，是指具有默认构造函数、拷贝构造函数和赋值运算符的类型。绝大多数数据类型，包括基本类型，比如 int 和 double，指针，Qt 数据类型，例如 QString、QDate 和 QTime，都是可赋值数据类型。但是，QObject 及其子类（QWidget、QTimer 等）都不是。也就是说，你不能使用 QList 这种容器，因为 QWidget 的拷贝构造函数和赋值运算符不可用。如果你需要这种类型的容器，只能存储其指针，也就是 QList。

如果要使用 QMap 或者 QHash，作为键的类型必须提供额外的辅助函数。QMap 的键必须提供 operator<() 重载，QHash 的键必须提供 operator==() 重载和一个名字是 qHash() 的全局函数。

作为例子，我们考虑如下的代码：

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

[color=rgb(0, 204, 255) !important]复制代码

作为 struct，我们当做纯数据类使用。这个类没有额外的构造函数，因此编译器会为我们生成一个默认构造函数。同时，编译器还会生成默认的拷贝构造函数和赋值运算符。这就满足了将其放入容器类存储的条件：

QList movs;

[color=rgb(0, 204, 255) !important]复制代码

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;
}

[color=rgb(0, 204, 255) !important]复制代码

根据数据结构的相关内容，我们有必要对这些容器类的算法复杂性进行定量分析。算法复杂度关心的是在数据量增长时，容器的每一个函数究竟有多快（或者多慢）。例如，向 QLinkedList 中部插入数据是一个相当快的操作，并且与 QLinkedList 中已经存储的数据量无关。另一方面，如果 QVector 中已经保存了大量数据，向 QVector 中部插入数据会非常慢，因为在内存中，有一半的数据必须移动位置。为了描述算法复杂度，我们引入 O 记号（大写字母 O，读作“大 O”）：

常量时间：O(1)。如果一个函数的运行时间与容器中数据量无关，我们说这个函数是常量时间的。QLinkedList::insert() 就是常量时间的。
对数时间：O(log n)。如果一个函数的运行时间是容器数据量的对数关系，我们说这个函数是对数时间的。qBinaryFind() 就是对数时间的。
线性时间：O(n)。如果一个函数的运行时间是容器数据量的线性关系，也就是说直接与数量相关，我们说这个函数是限行时间的。QVector::insert() 就是线性时间的。
线性对数时间：O(n log n)。线性对数时间要比线性时间慢，但是要比平方时间快。
平方时间：O(n2)。平方时间与容器数据量的平方关系。

基于上面的表示，我们来看看 Qt 顺序容器的算法复杂度：

	查找	插入	前方添加	后方追加
QLinkedList	O(n)	O(1)	O(1)	O(1)
QList	O(1)	O(n)	统计 O(1)	统计 O(1)
QVector	O(1)	O(n)	O(n)	统计 O(1)

上表中，所谓“统计”，意思是统计意义上的数据。例如“统计 O(1)”是说，如果只调用一次，其运行时间是 O(n)，但是如果调用多次（例如 n 次），则平均时间是 O(1)。

下表则是关联容器的算法复杂度：

	查找键		插入
	平均	最坏	平均	最坏
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)

QVector、QHash 和 QSet 的头部添加是统计意义上的 O(log n)。然而，通过给定插入之前的元素个数来调用 QVector::reserve()、QHash::reserve() 和 QSet::reserve()，我们可以把复杂度降到 O(1)。我们会在下面详细讨论这个问题。

QVector、QString 和 QByteArray 在连续内存空间中存储数据。QList 维护指向其数据的指针数组，提供基于索引的快速访问（如果 T 就是指针类型，或者是与指针大小相同的其它类型，那么 QList 的内部数组中存的就是其实际值，而不是其指针）。QHash 维护一张散列表，其大小与散列中数据量相同。为避免每次插入数据都要重新分配数据空间，这些类都提供了多余实际值的数据位。

我们通过下面的代码来了解这一算法：

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

[color=rgb(0, 204, 255) !important]复制代码

我们创建了一个字符串，每次动态追加一个字符。假设我们需要追加 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 实际算法与 QString 非常类似。

对于那些能够使用 memcry()（包括基本的 C++ 类型，指针类型和 Qt 的共享类）函数在内存中移动的数据类型，QVector 也使用了类似的算法；对于那些只能使用拷贝构造函数和析构函数才能移动的数据类型，使用的是另外一套算法。由于后者的消耗更高，所以 QVector 减少了超出空间时每次所要分配的额外内存数。

QHash 则是完全不同的形式。QHash 的内部散列表每次会增加 2 的幂数；每次增加时，所有数据都要重新分配到新的桶中，其计算公式是 qHash(key) % QHash::capacity()（QHash::capacity() 就是桶的数量）。这种算法同样适用于 QSet 和 QCache。如果你不明白“桶”的概念，请查阅数据结构的相关内容。

对于大多数应用程序。Qt 默认的增长算法已经足够。如果你需要额外的控制，QVector、QHash、QSet、QString 和 QByteArray 提供了一系列函数，用于检测和指定究竟要分配多少内存：

capacity()：返回实际已经分配内存的元素数目（对于 QHash 和 QSet，则是散列表中桶的个数）
reserve(size)：为指定数目的元素显式地预分配内存。
squeeze()：释放那些不需要真实存储数据的内存空间。

如果你知道容器大约有多少数据，那么你可以通过调用 reserve() 函数来减少内存占用。如果已经将所有数据全部存入容器，则可以调用 squeeze() 函数，释放所有未使用的预分配空间。

Qt学习之路第38篇 存储容器 [复制链接]

Qt学习之路第38篇存储容器 [复制链接]