QList (链表) & QVector (数组)

谁践踏了优雅 2022-01-30 09:31 478阅读 0赞

# QList (链表) & QVector (数组) #

## C++中的list和vector ##

stl提供了三个最基本的容器：vector/list/deque。

**vector**和built-in数组类似，它拥有一段连续的内存空间，并且起始地址不变，因此它能非常好的支持随即存取，即**\[\]****操作符**，但由于它的内存空间是连续的，所以在中间进行插入和删除会造成内存块的拷贝，另外，当该数组后的内存空间不够时，需要重新申请一块足够大的内存并进行内存的拷贝。这些都大大影响了vector的效率。

**list**就是数据结构中的双向链表，因此它的内存空间可以是不连续的，通过指针来进行数据的访问，这个特点使得它的随即存取变的非常没有效率，因此它**没有**提供**\[\]**操作符的重载。但由于链表的特点，它可以以很好的效率支持任意地方的删除和插入。

deque是一个double-ended queue，它的具体实现不太清楚，但知道它具有以下两个特点：

它支持\[\]操作符，也就是支持随即存取，并且和vector的效率相差无几，它支持在两端的操作：push\_back,push\_front,pop\_back,pop\_front等，并且在两端操作上与list的效率也差不多。

因此在实际使用时，如何选择这三个容器中哪一个，应根据你的需要而定，一般应遵循下面的原则：

1.  如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
2.  如果你需要大量的插入和删除，而不关心随即存取，则应使用list
3.  如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque。

vector为存储的对象分配一块连续的地址空间，因此对vector中的元素随机访问效率很高。在vecotor中插入或者删除某个元素，需要将现有元素进行复制，移动。如果vector中存储的对象很大，或者构造函数复杂，则在对现有元素进行拷贝时开销较大，因为拷贝对象要调用拷贝构造函数。对于简单的小对象，vector的效率优于list。vector在每次扩张容量的时候，将容量扩展2倍，这样对于小对象来说，效率是很高的。

list中的对象是离散存储的，随机访问某个元素需要遍历list。在list中插入元素，尤其是在首尾插入元素，效率很高，只需要改变元素的指针。

综上所述：

vector适用：对象数量变化少，简单对象，随机访问元素频繁；

list适用：对象数量变化大，对象复杂，插入和删除频繁。

Qt中的 QList & QVector

Qlist、QVector 与 list、vector似乎不太类似；list插入删除很快，vector查询很快。

但QList是基于index标签存储它的元素项在内存（虽然内存不连续，这点与list 是一样的），可以使用**\[ \]**运算符。

vector注意事项：

如果你添加元素，但是vector的容量（是容量，不是大小，容量比大小大，会预先多分配空间）不够的话，系统就会重新分配一段内存，然后把原先的内容全部拷贝过去，然后删除原先的内容。**所以**，如果你设定了一个指向vector的指针，或者说**迭代器**，在你**添加元素**之后，这个指针（迭代器）需要**重新计算**。

QList和QVector等容器的区别：

1.  大多数情况下可以用QList。像prepend()和insert()这种操作，通常QList比QVector快的多。这是因为QList是基于index标签存储它的元素项在内存中，比那种依赖iterator迭代的更快捷。而且你的代码也更少。
2.  如果你需要一个真正的连接着的list，且需要保证一个固定插入耗时。那就用迭代器，而不是标签。使用QLinkedList();
3.  如果你需要开辟连续的内存空间存储，或者你的元素远比一个指针大，这时你需要避免个别插入操作，出现堆栈溢出，这时候用QVector
4.  如果你需要一个低层的可变数量大小的数组，用QVarLengthArray就够了。他可以预先在栈中分配已知长度大小的数组，如果超过这个长度，会在堆中继续存储。默认大小256。

Qt官方解释翻译：

For most purposes, [QList][] is the right class to use. Operations like [prepend][]() and [insert][]() are usually faster than with QVector because of the way [QList][] stores its items in memory (see [Algorithmic Complexity][] for details), and its index-based API is more convenient than [QLinkedList][]'s iterator-based API. It also expands to less code in your executable.

If you need a real linked list, with guarantees of [constant time][] insertions in the middle of the list and iterators to items rather than indexes, use [QLinkedList][].

If you want the items to occupy adjacent memory positions, or if your items are larger than a pointer and you want to avoid the overhead of allocating them on the heap individually at insertion time, then use QVector.

If you want a low-level variable-size array, [QVarLengthArray][] may be sufficient.

QVarLengthArray<int, 1024> array(n + 1);

QVector

**QVector**，是Qt对所有数组的封装，比如我们想要一个int类型数组，我们原先会写int array\[10\]，我们在Qt里可以写QVector<int> array(10)

赋值的时候，我们依然可以照旧array\[5\]=4;想获取某一项的值也还可以array\[9\]，也就是说，原来的特性我们还可以用。

那么QVector有什么好处呢？

·我们可以用count函数获知数组中有多少个元素，方便遍历；

·原先我们必须预定义好大小，而用QVector我们虽然最好也先定义好大小，但是预先不定义也可以。

我们可以使用append函数或者<<操作符来在数组最后端添加元素而不用担心溢出问题。

[QList]: http://qimo601.iteye.com/admin/blogs/1463047/qlist.html
[prepend]: http://qimo601.iteye.com/admin/blogs/1463047/qvector.html#prepend
[insert]: http://qimo601.iteye.com/admin/blogs/1463047/qvector.html#insert
[Algorithmic Complexity]: http://qimo601.iteye.com/admin/blogs/1463047/containers.html#algorithmic-complexity
[QLinkedList]: http://qimo601.iteye.com/admin/blogs/1463047/qlinkedlist.html
[constant time]: http://qimo601.iteye.com/admin/blogs/1463047/containers.html#constant-time
[QVarLengthArray]: http://qimo601.iteye.com/admin/blogs/1463047/qvarlengtharray.html