c++ - Qt 框架中的 QMap 与 QList 类

Question

我正在尝试决定是在我 future 的一些 Qt 项目中使用 QList 还是 QMap 类。为了确定最适合我的选择，我想确定它们的一些相似之处和一些差异，以便了解在某些情况下什么最有效。我对这些异同的理解是否正确？

相似点:

• 都是容器

• 两者都包含无序数据

差异:

• QMap有键值对而QList只有值

• QMap 使用散列函数将值放在适当的索引中而 QList 只是附加条目

是否还有更多的相同点和不同点？

我可以查看通用计算机科学定义，但我在某处读到 Qt 框架中可能存在细微差别。

Answer 1

QList 和 QMap 数据组织方式不同。这会导致不同的性能和略微不同的内存消耗(对于大多数用例，后者通常无关紧要)。您可以找到 computational complexity在Qt documentation .如果您要存储很多元素，这可能会有很大的不同。在选择容器时考虑您希望访问数据的频率(搜索、插入和删除)。

[不过请记住，算法复杂度是一种理论属性，仅对大 n 有用。在实践中，由于 locality of reference，通过具有少量元素(<1,000)的数组进行线性搜索通常优于列表/树。 .如果您关心性能，请不要猜测，请始终测量。]

Both contain unordered data

QMap 实际上不是这样。 QMap 被实现为 self-balancing binary search tree这是一个排序的数据结构。

顺便说一句:您通常可以用一种通用的方式来实现您的代码，这样以后就可以很容易地切换到另一种容器类型(例如，如果访问模式发生变化或您的假设被证明是错误的)。使用 auto 可以帮助简化这一切。