QVector与QList

Question

我有一个整数列表,我需要迭代,但数组是不合适的.之间有什么区别vectors和lists,是有什么我需要知道我挑式前？

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

QList<T>,QLinkedList<T>并QVector<T>提供类似的功能.这是一个概述:

• 对于大多数用途,QList是正确的使用类.它的基于索引的API比QLinkedList's基于迭代器的API更方便,并且通常比QVector将其项目存储在内存中的速度更快.它还扩展到可执行文件中较少的代码.
• 如果您需要一个真实的链表,保证在列表中间插入常量时间,并将迭代器设置为项而不是索引,请使用QLinkedList.
• 如果您希望项目占据相邻的内存位置,请使用QVector.

Answer 1

QVectorstd::vector正如你可能从名字中猜到的那样,大致类似于. 尽管有明显的联系,但是QList更接近于.它不直接存储对象,而是存储指向它们的指针.您两端获得快速插入的所有优点,和再分配涉及洗牌指针而不是拷贝构造函数,但失去了实际的空间局部性或,并获得了大量堆分配的.它确实有一些决策可以避免小对象的堆分配,重新获得空间局部性,但据我所知它只适用于小于a的东西.boost::ptr_dequestd::liststd::dequestd::vectorint

QLinkedList类似于std::list,并具有它的所有缺点.一般来说,这应该是您最后选择的容器.

QT库非常倾向于使用QList对象,因此在您自己的代码中使用它们有时可以避免一些不必要的乏味.在某些情况下,额外的堆使用和实际数据的随机定位在理论上可能会受到伤害,但通常是不可察觉的.所以我建议使用,QList直到分析建议改为a QVector.如果你期望连续分配是重要的[读取:你正在与代表期望T[]而不是a的代码接口,QList<T>这也可能是一个开始时立即开始的理由QVector.

如果您一般询问容器,并且仅使用QT文档作为参考,那么上述信息就不那么有用了.

An std::vector是一个可以调整大小的数组.所有元素彼此相邻存储,您可以快速访问各个元素.缺点是插入只在一端有效.如果你把东西放在中间或开头,你必须复制其他对象以腾出空间.在大写符号中,最后插入是O(1),其他地方的插入是O(N),随机访问是O(1).

An std::deque类似,但不保证对象彼此相邻存储,并允许两端插入为O(1).它还需要一次分配较小的内存块,这有时很重要.随机访问是O(1),中间插入是O(N),与a相同vector.空间位置比较差std::vector,但物体往往聚集在一起,因此您可以获得一些好处.

An std::list是一个链表.它需要三个标准顺序容器的最大内存开销,但可以在任何地方快速插入...前提是您事先知道需要插入的位置.它不提供对单个元素的随机访问,因此您必须迭代O(N).但是一旦那里,实际插入是O(1).最大的好处std::list是可以快速将它们拼接在一起......如果将整个值范围移动到不同的值std::list,整个操作就是O(1).使列表中的引用无效也更加困难,这有时很重要.

作为一般规则,我宁愿std::deque到std::vector,除非我需要能够将数据传递给需要原始阵列库. std::vector保证连续,所以&v[0]为此目的.我不记得我最后一次使用a了std::list,但几乎可以肯定,因为我需要更强大的关于引用仍然有效的担保人.

Answer 2

事情变了

我们现在在Qt 5.8中,事情发生了变化,所以文档.它为这个问题提供了一个清晰而不同的答案:

QVector应该是您的默认首选.QVector<T>通常会提供比QList<T> 更好的性能,因为它QVector<T>始终将其项目按顺序存储在内存中,QList<T>除非将sizeof(T) <= sizeof(void*)T声明为a Q_MOVABLE_TYPE或者Q_PRIMITIVE_TYPE使用, 否则将在堆上分配其项目Q_DECLARE_TYPEINFO.

有关说明,请参阅使用的优点和缺点QList.但是,QList在整个Qt API中用于传递参数和返回值.用于QList与这些API进行交互.

Answer 3

在QVector类似于std::vector.QLinkedList类似于std::list.QList是一个基于索引的向量,但不保证内存位置(如std::deque).