QVector vs QList

J'ai une liste d'entiers que je dois parcourir mais un tableau est inadéquat. Quelles sont les différences entre les vecteurs et les listes et y a-t-il quelque chose que je dois savoir avant de choisir un type?

Juste pour être clair, j'ai lu les documents QT mais c'est l'étendue de ce que je sais:

QList, QLinkedList et QVector offrent des fonctionnalités similaires. Voici un aperçu:

  • dans la plupart des cas, QList est la bonne classe à utiliser. Son API basée sur l'index est plus pratique que L'API basée sur l'itérateur de QLinkedList, et il est généralement plus rapide que QVector en raison de la façon dont il stocke ses éléments en mémoire. Il se développe également à moins de code dans votre exécutable.
  • Si vous avez besoin d'une vraie liste liée, avec des garanties d'insertions à temps constant au milieu de la liste et des itérateurs aux éléments plutôt qu'aux index, utilisez QLinkedList.
  • Si vous voulez que les éléments occupent des positions de mémoire adjacentes, utilisez QVector.
64
demandé sur jcuenod 2011-07-06 23:47:04

5 réponses

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.

108
répondu Dennis Zickefoose 2011-07-06 20:34:20

Les Choses ont changé

Nous sommes maintenant dans Qt 5.8 et les choses ont changé, donc la documentation. Il donne une réponse claire et différente à cette question:

QVector devrait être votre premier choix par défaut. Qvector sera généralement donner de meilleures performances que QList, parce que QVector toujours stocke ses éléments séquentiellement en mémoire, où QList allouera ses éléments sur le tas sauf sizeof (T)

Voir les avantages et les inconvénients de L'utilisation de QList pour un explication. Cependant, QList est utilisé dans toutes les API Qt pour passer paramètres et pour les valeurs de retour. Utilisez QList pour interfacer avec ceux-ci API.

29
répondu dlewin 2017-04-28 10:00:40

Dans QVector est similaire à std::vector. QLinkedList est similaire à std::list. QList est un vecteur basé sur un index, mais la position de la mémoire n'est pas garantie (comme std::deque).

10
répondu Naszta 2011-07-06 19:50:55

De qtlist doc:

  • QList à utiliser dans la plupart des cas. Pour les structures avec un millier d'éléments, permet une insertion efficace au milieu, et fournit un accès indexé. prepend() et append() très rapide puisque la mémoire est préallouée aux deux extrémités du tableau interne. {[2] } est un tableau de pointeur de type T. Si T a un pointeur ou un type de pointeur partagé Qt, l'objet est stocké directement dans array

  • QVector à privilégier dans le cas d'un lot de append() ou insert() de nouveau éléments de taille supérieure à un pointeur puisque QVector alloue de la mémoire pour ses éléments dans une seule allocation de tas. Pour QList, l'insertion d'un nouvel élément nécessite une allocation de mémoire du nouvel élément sur le tas. En bref, si vous voulez que les éléments occupent des positions de mémoire adjacentes, ou si vos éléments sont plus grands qu'un pointeur et que vous voulez éviter la surcharge de les allouer individuellement sur le tas au moment de l'insertion, utilisez QVector.

2
répondu octoback 2013-05-27 16:44:44

QVector est comme un tableau qui peut changer la taille (augmenter ou diminuer) mais il est livré avec des transactions lourdes et le calcul et le temps.

Par exemple, si vous souhaitez ajouter un élément, un nouveau tableau est créé, tous les éléments sont copiés dans le nouveau tableau, le nouvel élément est ajouté à la fin, et ancien tableau est supprimé. Et vice versa pour supprimer aussi bien.

Cependant, QLinkedList fonctionne avec des pointeurs. Ainsi, lorsqu'un nouvel élément est créé, juste un nouvel espace mémoire est alloué et lié à la seule morceau de la mémoire. Comme il fonctionne avec des pointeurs, il est plus rapide et efficace.

Si vous avez une liste d'éléments que vous ne vous attendez pas à changer beaucoup de taille, QVector est probablement bon, mais généralement QLinkedList est utilisé à la plupart des fins.

-2
répondu Nick 2011-07-07 15:20:15