QVector与QList

我有一个整数列表,我需要迭代,但一个数组是不够的。 向量和列表之间有什么区别,在selecttypes之前有什么我需要知道的?

只是要清楚,我已经阅读了QT文档,但这是我所知道的程度:

QList,QLinkedList和QVector提供了类似的function。 这里有一个概述:

  • 对于大多数目的,QList是正确的类。 它的基于索引的API比QLinkedList的基于迭代器的API更方便,并且由于它将项目存储在内存中的方式通常比QVector更快。 它也扩展到更less的代码在您的可执行文件。
  • 如果你需要一个真正的链表,保证在列表中间有恒定的时间插入,迭代器可以保证项目而不是索引,可以使用QLinkedList。
  • 如果你想要项目占用相邻的内存位置,使用QVector。

QVector大部分类似于std::vector ,正如你可能从名字中猜出的那样。 QList更接近boost::ptr_deque ,尽pipe与std::list有明显的关联。 它不直接存储对象,而是存储指向它们的指针。 你获得了两端快速插入的所有好处,重新分配涉及到洗牌指针而不是复制构造函数,但失去了实际的std::dequestd::vector的空间局部性,并且获得了大量的堆分配。 它确实做出了一些决定,以避免为小对象堆分配,重新获得空间局部性,但从我所了解的情况来看,它只适用于小于int事情。

QLinkedList类似于std::list ,并且具有所有缺点。 一般来说,这应该是你最后一个容器的select。

QT库非常喜欢使用QList对象,所以在你自己的代码中使用它们有时候可以避免一些不必要的乏味。 额外的堆使用和实际数据的随机定位理论上可能会在某些情况下受到伤害,但通常是不可忽略的。 所以我会build议使用QList直到分析build议更改为QVector 。 如果你期望连续的分配是重要的[阅读:你正在接口的代码,而不是一个QList<T> ]的T[] ],也可能是一个理由,从QVector立即开始。


如果您一般询问容器,只是使用QT文档作为参考,那么上面的信息就没那么有用了。

std::vector是一个可以resize的数组。 所有元素都相邻存储,您可以快速访问各个元素。 缺点是插入仅在一端有效。 如果你把东西放在中间,或者在开始的时候,你必须复制其他的东西来腾出空间。 在大的表示法中,最后插入的是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 ,但几乎肯定是因为我需要更强大的引用保持有效。

QVector中类似于std::vectorQLinkedList类似于std::listQList是一个基于索引的向量,但内存的位置是不能保证的(如std::deque )。

事情变了

我们现在在Qt 5.8,事情已经改变,所以文件。 它给这个问题提供了一个明确而不同的答案:

QVector应该是你默认的第一select。 QVector通常会比QList提供更好的性能,因为QVector始终将其项目顺序存储在内存中,除非sizeof(T)<= sizeof(void *)且T被声明为Q_MOVABLE_TYPE或使用Q_DECLARE_TYPEINFO的Q_PRIMITIVE_TYPE。

请参阅使用QList的优点和缺点以获得解释。 但是,QList在整个Qt API中用于传递参数和返回值。 使用QList来与这些API接口。

从QtList文档:

  • QList将在大多数情况下使用。 对于有一千个项目的结构,可以在中间高效插入,并提供索引访问。 prepend()append()非常快,因为在内部数组的两端预先分配了内存。 QList<T>QList<T>types指针的数组。如果T有一个指针或Qt共享types的指针types,则对象直接存储在数组中

  • 由于QVector在单个堆分配中为其项目分配内存, QVector大于append()insert()大于指针的新项目的情况下是首选。 对于QList ,添加新项目的插入需要在堆上分配新项目的内存。 简而言之,如果您希望项目占用相邻的内存位置,或者您的项目大于指针,并且希望避免在插入时分别在堆上分配它们的开销,则使用QVector

QVector就像一个数组,可以改变大小(增加或减less),但它带有繁重的交易,计算和时间。

例如,如果要添加项目,则创build一个新数组,将所有项目复制到新数组,将新项目添加到结尾,并删除旧数组。 反之亦然删除以及。

但是,QLinkedList与指针一起工作。 所以当创build一个新的项目时,只有一个新的内存空间被分配并链接到唯一的内存块。 由于它与指针一起工作,速度更快,效率更高。

如果你有不希望改变大小的项目列表,QVector可能是好的,但通常QLinkedList用于大多数目的。