Qt中容器 QVector、QList、QSet和QMap 性能与用途比较
- 表格汇总：
| 容器 | 存储结构 | 随机访问性能 | 插入/删除性能 | 主要用途 |
|---|---|---|---|---|
QVector | 连续存储的动态数组 | O ( 1 ) O(1) O(1) | 末尾： O ( 1 ) O(1) O(1)，中间： O ( n ) O(n) O(n) | 频繁随机访问，末尾元素的添加/删除 |
QList | 优化存储（类似数组和链表结合） | O ( 1 ) O(1) O(1) | 中间相对高效 | 频繁插入/删除，一定程度的随机访问 |
QSet | 基于哈希表，存储唯一元素 | 不支持 | 平均 O ( 1 ) O(1) O(1)，最坏 O ( n ) O(n) O(n) | 存储唯一元素，检查元素存在性 |
QMap | 存储键值对，基于红黑树 | 不支持 | O ( l o g n ) O(log n) O(logn) | 存储键值对，根据键查找值 |
- 存储结构与特点：
- QVector：
- 存储结构：是一个动态数组，元素在内存中是连续存储的。这使得它可以像普通数组一样支持快速的随机访问，通过下标访问元素的时间复杂度为 O ( 1 ) O(1) O(1)。例如，对于
QVector<int> vec;，可以使用vec[3]快速访问第 4 个元素（索引从 0 开始）。 - 特点：当添加元素超过其容量时，会自动分配更大的内存空间并复制元素，可能会产生性能开销和内存浪费（预留但未使用的空间）。但对于随机访问操作非常高效，并且由于内存连续性，在缓存利用上有一定优势。
- 存储结构：是一个动态数组，元素在内存中是连续存储的。这使得它可以像普通数组一样支持快速的随机访问，通过下标访问元素的时间复杂度为 O ( 1 ) O(1) O(1)。例如，对于
- QList：
- 存储结构：使用了一种优化的存储方式，结合了数组和链表的特点，并非严格的链表。提供快速的插入和删除操作，并且支持通过索引快速访问元素，时间复杂度为 O ( 1 ) O(1) O(1)。它的内部存储不是完全连续，但在性能表现上类似于同时具备了数组和链表的优点。
- 特点：在中间插入和删除元素时相对高效，相比纯数组结构，其内部存储策略可以更好地处理元素的动态添加和删除操作，同时保持了一定的随机访问能力。
- QSet：
- 存储结构：基于哈希表实现，存储一组唯一元素。元素的存储位置由其哈希值决定，元素是无序的。
- 特点：由于使用哈希表，插入、删除和查找元素的操作在平均情况下时间复杂度接近 O ( 1 ) O(1) O(1)，但在最坏情况下可能退化为 O ( n ) O(n) O(n)。它主要用于存储不允许重复元素的集合，并且在判断元素是否存在方面表现出色。
- QMap：
- 存储结构：是一个关联容器，存储键值对，内部基于红黑树实现，键是唯一的。
- 特点：元素是按照键的顺序存储（默认为升序），插入、删除和查找操作的时间复杂度为 O ( l o g n ) O(log n) O(logn)。可以根据键快速查找对应的值，适合需要按键进行查找、排序的场景。
- QVector：
- 性能比较：
- 随机访问：
- QVector：具有最好的随机访问性能，因为其内存连续，对于随机访问密集型操作是最优选择。
- QList：也能提供较好的随机访问性能，但在性能上稍逊于
QVector，不过在频繁插入和删除元素时，其综合性能可能会优于QVector。 - QSet：不支持随机访问，其重点在于快速的元素存在性检查和集合操作，如添加、删除元素。
- QMap：不适合随机访问，主要用于通过键查找值，查找性能为 O ( l o g n ) O(log n) O(logn)。
- 插入和删除操作：
- QVector：在末尾插入和删除元素通常比较快，时间复杂度为 O ( 1 ) O(1) O(1)，但在中间插入或删除元素时，需要移动大量元素，时间复杂度为 O ( n ) O(n) O(n)。
- QList：在中间插入和删除元素比
QVector更高效，因为其内部存储结构的优势，但在极端情况下（例如大量元素）可能仍会有一定性能开销。 - QSet：插入和删除元素的平均性能为 O ( 1 ) O(1) O(1)，但在哈希冲突较多时性能会下降。
- QMap：插入、删除和查找操作的时间复杂度为 O ( l o g n ) O(log n) O(logn)，相对稳定，适合需要维护键值对的有序性和频繁插入、删除键值对的场景。
- 随机访问：
- 用途比较：
- QVector：
- 适合需要频繁随机访问元素，并且元素的添加和删除操作主要在末尾进行的场景。例如，存储图像数据、矩阵元素、传感器读数等，这些数据通常需要根据索引快速访问，且数据增长相对稳定。
- QList：
- 适用于需要频繁插入和删除元素，同时也需要一定程度的随机访问的情况。比如在图形用户界面的列表组件中，用户可以对列表项进行频繁的添加、删除和重新排序操作，同时也可能需要根据索引查看元素。
- QSet：
- 主要用于存储一组唯一元素，并且需要快速检查元素是否存在的情况。例如，存储唯一的用户标识符、已访问过的 URL 集合等。
- QMap：
- 适用于存储键值对，并且需要根据键快速查找值的场景，例如存储配置信息、字典数据，其中键可以是配置项名称或单词，值可以是相应的配置内容或解释。
- QVector：