Qt中容器 QVector、QList、QSet和QMap 性能与用途比较

1. 表格汇总：

容器	存储结构	随机访问性能	插入/删除性能	主要用途
QVector	连续存储的动态数组	$O(1)$	末尾：$O(1)$，中间：$O(n)$	频繁随机访问，末尾元素的添加/删除
QList	优化存储（类似数组和链表结合）	$O(1)$	中间相对高效	频繁插入/删除，一定程度的随机访问
QSet	基于哈希表，存储唯一元素	不支持	平均 $O(1)$，最坏 $O(n)$	存储唯一元素，检查元素存在性
QMap	存储键值对，基于红黑树	不支持	$O(logn)$	存储键值对，根据键查找值

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