Qt | 关于容器类的一些总结

前言：

之前面试被问过一个问题，关于数据结构的：

问题：“你知道的数据结构有哪些？它们在实际程序中有哪些应用？”

答案： 数据结构分为线性结构和非线性结构，按照存储方式线性结构又分为顺序结构和链式结构，程序中常见的线性结构包括：数组、队列、链表、栈等。程序中常见的非线性结构包括二维数组、多维数组、树、图等。

容器的分类：

顺序容器：

QList、 QLinkedList、QVector、QStack 和 QQueue。因为这些容器中的数据都是一个接一个线性存储的，所以成为顺序容器。

• QList： 是目前最常用的容器类。它存储了给定类型的值的一个列表，这些值可以通过索引访问。在 QList 的内部是通过使用数组实现的，以确保进行快速的基于索引访问。它的一些方法：QList::append()--在列表的尾部添加项目；QList::prepend()--在列表的头部添加项目；QList::insert()--在列表的中间插入项目。常用的 QStringList 就继承自 QList<QString>。

• QLinkedList： 它和 QList 基本相同，区别在于：QLinkedList 使用迭代器访问项目，而 QList 一般使用整数索引访问项目；在向一个很大的列表中间插入项目时，QLinckedList 比 QList 拥有更好的性能。（注意： 当迭代器指向 QLinckedList 的一个项目后，只要这个项目还存在，那么迭代器就依然有效；而当迭代器指向 QList 中的一个项目后，如果 QList 进行了插入或者删除操作，这个迭代器就无效了。）

• QVector： 占用连续的内存控件存储给定类型的值的一个数组。在 vector 的前面或者中间插入项目是非常缓慢的，因为这样可能导致大量的项目在内存中移动一个位置。

• QStack： 它是 QVector 的一个便捷子类，提供了后进先出语义。添加了 push()、pop()、和 top() 等函数。

• QQueue： 它是 QList 的一个便捷子类，提供了先进先出语义。添加了 enqueue()、dequeue() 和 head() 等函数。

关联容器：

QMap、QMultiMap、QHash、QMultiHash 和 QSet。因为这些容器存储的是<键、值>对，比如 QMap<Key, T>，所以被称为关联容器。

• QMap： 它提供了一个字典（关联数组），将 Key 类型的键值映射到值上。一般一个键关联单一的一个值。QMap 使用键顺序来存储它的数据（自动根据键的顺序进行排序）；如果不关心存储顺序，还可以使用 QHash 来代替它，因为 QHash 速度更快。

• QMultiMap： 它是 QMap 的一个便捷类，提供了实现多值映射的接口函数，例如一个键可以关联多个值。

• QHash： 它与 QMap 拥有基本相同的接口，但是它的查找速度更快。QHash 的数据是以任意的顺序存储的。

• QMultiHash： 它是 QHash 的一个便捷类，提供了实现多值散列的接口函数。

• QSet： 它提供了一个可以快速查询单值的数学集。