16. Qt深入 容器

1. QVector

数组我们都非常熟悉，数据在内存中是连续分布的。这种结构的缺点是当元素很多时，除了在结尾添加一个新元素以及修改某个元素值之外，其他相关的函数（如最开头插入）执行起来会随元素增多而变慢。因为主要是保证是占用连续的内存空间，因此插入新元素后，后面的元素都要顺次往后移动。Qt 库封装数组的类是 QVector。

2. QList

链表是一种在内存中非连续的存储结构，元素的逻辑顺序是通过链表中的指针链接次序实现的。每一个元素都包括两个值：自身数据 + 下一个元素的地址（指针）。Qt 库封装链表的类是 QList。

这种结构在插入的时候可以达到O(1)的复杂度，也就是在任何位置插入一个新元素所执行的时间是固定的。举个例子，假如我在元素2和元素3中间插入一个新元素n，无非就是把元素2和元素3之间的链子砍断，然后重新设置指向而已。这种结构可以克服需要预先知道数据大小的缺点，还可以充分利用计算机内存空间（因为不需要一块连续的内存空间嘛），实现灵活的内存动态管理。缺点就是查找某个元素会特别耗时，它不像数组那样内部用红黑树来查找。

3. QSet

QSet< QString>set;
QSet 是一个集合类，存储不重复的元素。底层基于QHash
元素的顺序是不确定的，不支持索引访问。
使用哈希表实现，具有高效的插入、删除和查找操作。
适用于需要存储不重复元素并且需要高效的插入、删除和查找的场景。

4. QMap

QMap<QString, int> map;
QMap 是一个关联容器类，存储键值对（key-value pairs）。
元素按照键的排序顺序存储，支持按键进行快速查找。
适用于需要按键进行快速查找和排序的场景。

5. QHash

QHash<int, QString> qhash;
QHash 采用哈希表作为底层数据结构。哈希表使用一个哈希函数将元素映射到数组中的一个位置（称为桶）。当发生哈希冲突（不同元素映射到相同的桶）时，QHash 使用链地址法（chaining）来解决冲突，这意味着每个桶实际上是一个链表，存储哈希冲突的元素。

6. QMultiMap

QMultiMap<QString, int> multimap;

7. QStack QQueue

区别

.存储方式
QVector：动态数组，元素在内存中连续存储。
QList：链表，元素在内存中非连续存储。
QSet：集合，元素无序存储，用于快速查找元素是否存在。
QMap：关联数组，元素以键值对的形式存储，支持快速查找。

访问速度
QVector：随机访问元素较快，但插入和删除操作较慢。
QList：插入和删除操作较快，但随机访问元素较慢。
QSet：查找元素是否存在较快，但其他操作较慢。
QMap：快速查找键值对，插入和删除操作也较快。

容量与内存占用
QVector：内存占用相对较小，但容量受限于内存大小。
QList：内存占用相对较大，但容量不受限于内存大小。
QSet：内存占用较小，但容量也较小。
QMap：内存占用较大，但容量也较大。

应用场景
QVector：适用于需要频繁随机访问元素的场景，如数组计算、数据处理等。
QList：适用于需要频繁插入和删除元素的场景，如动态规划、数据结构算法等。
QSet：适用于需要快速检查元素是否存在的场景，如集合运算、事件处理等。
QMap：适用于需要快速查找键值对的场景，如数据持久化、数据缓存等。