我有一个需要迭代的整数列表,但数组是不够的。 vectors
和 lists
之间有什么区别?在选择类型之前我需要了解什么?
为了清楚起见,我已经阅读了 QT 文档,但这是我所知道的范围:
QList
QVector
与 std::vector
大体相似,正如您可能从名称中猜到的那样。 QList
更接近于 boost::ptr_deque
,尽管与 std::list
有明显关联。它不直接存储对象,而是存储指向它们的指针。您可以获得两端快速插入的所有好处,并且重新分配涉及改组指针而不是复制构造函数,但会丢失实际 std::deque
或 std::vector
的空间局部性,并获得大量堆分配。它确实有一些决策来避免小对象的堆分配,重新获得空间局部性,但据我了解,它仅适用于小于 int
的事物。
QLinkedList
类似于 std::list
,并且具有它的所有缺点。一般来说,这应该是您最后选择的容器。
QT 库非常喜欢使用 QList
对象,因此在您自己的代码中使用它们有时可以避免一些不必要的乏味。理论上,在某些情况下,额外的堆使用和实际数据的随机定位可能会造成伤害,但通常不会引起注意。所以我建议使用 QList
,直到分析建议更改为 QVector
。如果您希望连续分配很重要 [阅读:您正在与需要 T[]
而不是 QList<T>
的代码进行交互],这也可能是立即开始使用 QVector
的原因。
如果您是一般性地询问容器,并且只是使用 QT 文档作为参考,那么上述信息就没那么有用了。
std::vector
是一个可以调整大小的数组。所有元素彼此相邻存储,您可以快速访问各个元素。缺点是插入仅在一端有效。如果你把一些东西放在中间,或者放在开头,你必须复制其他对象来腾出空间。在大哦符号中,末尾的插入是 O(1),其他任何地方的插入是 O(N),随机访问是 O(1)。
std::deque
类似,但不保证对象彼此相邻存储,并且允许在两端插入 O(1)。它还需要一次分配较小的内存块,这有时很重要。随机访问是 O(1),中间插入是 O(N),与 vector
相同。空间局部性比 std::vector
差,但对象往往会聚集在一起,因此您可以获得一些好处。
std::list
是一个链表。它需要三个标准顺序容器中最多的内存开销,但可以在任何地方快速插入……前提是您提前知道需要插入的位置。它不提供对单个元素的随机访问,因此您必须在 O(N) 中进行迭代。但是一旦到了那里,实际的插入是 O(1)。 std::list
的最大好处是您可以将它们快速拼接在一起......如果将整个范围的值移动到不同的 std::list
,则整个操作是 O(1)。使列表中的引用无效也更加困难,这有时很重要。
作为一般规则,我更喜欢 std::deque
而不是 std::vector
,除非我需要能够将数据传递到需要原始数组的库。 std::vector
保证是连续的,因此 &v[0]
用于此目的。我不记得我上次使用 std::list
是什么时候了,但这几乎可以肯定是因为我需要更强有力的保证来保证引用保持有效。
事情变了
我们现在在 Qt 5.8 中并且事情发生了变化,所以文档。它对这个问题给出了明确而不同的答案:
QVector 应该是您的默认首选。 QVector
QVector
中类似于 std::vector
。 QLinkedList
类似于 std::list
。 QList
是基于索引的向量,但不能保证内存位置(如 std::deque
)。
来自 QtList 文档:
在大多数情况下使用的 QList。对于具有一千个项目的结构,可以在中间有效插入,并提供索引访问。 prepend() 和 append() 非常快,因为内存是在内部数组的两端预先分配的。 QList
QVector 在大量大小大于指针的新项目的 append() 或 insert() 的情况下是首选,因为 QVector 在单个堆分配中为其项目分配内存。对于 QList,插入新项的追加需要在堆上分配新项的内存。简而言之,如果您希望项目占据相邻的内存位置,或者如果您的项目大于指针并且您希望避免在插入时将它们单独分配到堆上的开销,那么使用 QVector。
QVector
就像一个可以改变大小(增加或减少)的数组,但它伴随着繁重的事务、计算和时间。
例如,如果要添加一项,则创建一个新数组,将所有项复制到新数组中,将新项添加到末尾,并删除旧数组。反之亦然删除。
但是,QLinkedList
适用于指针。因此,当创建一个新项目时,只会分配一个新的内存空间并链接到唯一的内存块。因为它与指针一起工作,所以它更快更高效。
如果您有不希望改变大小的项目列表,则 QVector
可能很好,但通常 QLinkedList
用于大多数用途。
std::deque
与std::vector
进行了实际基准测试?你会惊讶...