QVector vs QList

QVector est essentiellement analogue à std::vector, comme vous pouvez le deviner à partir du nom. QList est plus proche de boost::ptr_deque, malgré l'apparente association avec std::list. Il ne stocke pas directement les objets, mais stocke plutôt des pointeurs vers eux. Vous gagnez tous les avantages des insertions rapides aux deux extrémités, et les réallocations impliquent des pointeurs mélangés au lieu de constructeurs de copie, mais perdent la localité spatiale d'un std::deque ou std::vector réel, et gagnent beaucoup d'allocations de tas. Il a une prise de décision à éviter les allocations de tas pour les petits objets, retrouvant la localité spatiale, mais d'après ce que je comprends, cela ne s'applique qu'aux choses plus petites qu'un int.

QLinkedList est analogue à std::list, et a tous les inconvénients d'elle. D'une manière générale, cela devrait être votre dernier choix d'un conteneur.

La bibliothèque QT favorise fortement l'utilisation d'objets QList, donc les favoriser dans votre propre code peut parfois éviter un ennui inutile. L'utilisation supplémentaire de tas et le positionnement aléatoire de la les données réelles peuvent théoriquement faire mal dans certaines circonstances, mais sont souvent imperceptibles. Donc, je suggère d'utiliser QList jusqu'à ce que le profilage suggère de changer en QVector. Si vous vous attendez à ce que l'allocation contiguë soit importante [lire: vous interfacez avec du code qui attend un T[] au lieu d'un QList<T>] cela peut aussi être une raison de commencer avec QVector dès le départ.

Si vous posez des questions sur les conteneurs en général, et que vous utilisez simplement les documents QT comme référence, alors ce qui précède l'information est moins utile.

Un std::vector est un tableau que vous pouvez redimensionner. Tous les éléments sont stockés les uns à côté des autres, et vous pouvez accéder aux éléments individuels rapidement. L'inconvénient est que les insertions ne sont efficaces à une extrémité. Si vous mettez quelque chose au milieu, ou au début, vous devez copier les autres objets pour faire de la place. En notation big-oh, l'insertion à la fin est O (1), l'insertion nulle part ailleurs est O(N), et l'accès aléatoire est O(1).

Un std::deque est similaire, mais ne garantit pas que les objets sont stockés les uns à côté des autres, et permet l'insertion aux deux extrémités d'être O(1). Cela nécessite également de plus petits morceaux de mémoire à allouer à la fois, ce qui peut parfois être important. L'accès aléatoire est O (1) et l'insertion au milieu est O (N), comme pour A vector. La localité spatiale est pire que std::vector, mais les objets ont tendance à être regroupés afin de gagner des avantages.

Un std::list est une liste liée. Il nécessite le plus de surcharge de mémoire des trois standards conteneurs séquentiels, mais offre une insertion rapide n'importe où... pourvu que vous sachiez à l'avance où vous devez insérer. Il n'offre pas d'accès aléatoire aux éléments individuels, vous devez donc itérer dans O(N). Mais une fois là, L'insertion réelle est O (1). Le plus grand avantage de std::list est que vous pouvez les assembler rapidement... si vous déplacez une plage entière de valeurs vers un std::list différent, l'opération entière est O (1). Il est également beaucoup plus difficile d'invalider les références dans la liste, ce qui peut parfois être important.

En règle générale, je préfère std::deque à std::vector, sauf si je dois pouvoir transmettre les données à une bibliothèque qui attend un tableau brut. {[1] } est garanti contigu, donc &v[0] Fonctionne à cet effet. Je ne me souviens pas de la dernière fois que j'ai utilisé un std::list, mais c'était presque certainement parce que j'avais besoin de la garantie la plus forte sur les références restant valides.