QList versus QVector ?

Salut à tous, j'aimerais savoir quelles sont les différences entre les deux conteneurs personnalisé de Qt : QList, et QVector.

J'aimerais aussi savoir, si il existe une classe (pas nécessairement Template) dans Qt, permettant de manipuler les données dans comme dans un tableau 2D. Dans le cas contraire, quel est la classe entre les deux précédentes, le plus adapté pour ce cas de figure. Merci à vous.

Code:

---

1 2 3

typedef QList< QList< T > > Table2DOfType; typedef QVector< QVector< T > > Table2DOfType;

---

La définition de la doc te suffit pas ?

Citation:

---

Envoyé par Doc Qt

QVector<T> is one of Qt's generic container classes. It stores its items in adjacent memory locations and provides fast index-based access.

QList<T>, QLinkedList<T>, and QVarLengthArray<T> provide similar functionality. Here's an overview:

* 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.

---

Salut,
voici un extrait de la documentation de QList tiré du DOC QT4.6:

Citation:

---

For most purposes, QList is the right class to use. Its index-based API is more convenient than QLinkedList's iterator-based API, and it is usually faster than QVector because of the way it stores its items in memory. It also expands to less code in your executable.

---

...si tu as bien compris,QList est plus générale dans tous les cas et plus rapide que QVector...:ccool:
a propos d'autres classes similaire aux tableaux 2D ,il existe QVarLengthArray pour les tableaux à taille faible et variable,mais il utilise les templates...:calim2:
j'éspére que ça va t'aider!;)

Citation:

---

Envoyé par Abdelite

Dans le cas contraire, quel est la classe entre les deux précédentes, le plus adapté pour ce cas de figure.

---

aucune des deux....
Si c'est un tableau 2D, c'est que chaque ligne à la même taille.
Il est beaucoup plus intéressant (et sûr) de faire un tableau 1D et de jouer sur le id

QVarLengthArray est un tableau 1D.

Ah oui,désolé,QVarLengthArray est un tableau 1D pas 2D...j'ai commit une faute
d'orthographe!

Ou tu fais une QList<QList<int>> de taille 2, avec la liste une pour les "x", et la liste 2 pour les "y".

Sinon, il me semble que ça existe dans Qwt, tu peux regarder comment ils ont fait.
EDIT : Dans Qwt, en fait, il y a juste une classe avec deux QVector membre.

G.

Merci pour vos réponses, pour le tableau 2D, je peux faire comme Qwt mais au lieu d'utiliser des QVector, j'utilise des QList, qui sont un peu plus rapide. Ça peux sembler correct, quels sont vos avis ?

:koi:
qu'es ce que tu appel un tableau2D au finale??

Un exemple de ce que j'appelle un tableau 2D :

Code:

---

table[x][y];

---

Un tableau de tableau comme : *argv[]

Citation:

---

Merci pour vos réponses, pour le tableau 2D, je peux faire comme Qwt mais au lieu d'utiliser des QVector, j'utilise des QList, qui sont un peu plus rapide. Ça peux sembler correct, quels sont vos avis ?

---

Ca depend, si tes données sont amenées à être utilisées sous forme de tableaux "C", alors il faut mieux utiliser des QVector. Sinon tu seras obligé de passer tes QList en QVector puis en tableaux "C", donc le peu de temps que tu gagneras à la manipulation de ta Qlist sera vite perdu.

Et puis je crois que si tu utilise la methode "reserve(int)" de QVector pour réserver une taille suffisante au préalable, les performances sont équivalentes.

G.

Je pense que ça dépend surtout de l'utilisation que tu en fais, si la taille de ta matrice (tableau 2D) est amenée à changer souvent ou pas du tout, si tu vas plutôt parcourir les éléments des tableaux dans l'ordre ou y accéder aléatoirement etc.
Je pense qu'une matrice de taille fixe sera optimale avec un tableau de tableaux directement en C++ sans classe conteneur. Sinon la doc Qt dit bien quelle structure utiliser selon ses besoins.

Ok, merci pour vos précision, je vais créer ma propre classe avec des QList.

Citation:

---

Je pense qu'une matrice de taille fixe sera optimale avec un tableau de tableaux directement en C++ sans classe conteneur.

---

Le problème est la gestion de la mémoire (qu'il faut gérer soit même) et l'accès aux données (il faut alors utiliser des pointeurs bruts, avec les risques associés)

Citation:

---

Je pense que ça dépend surtout de l'utilisation que tu en fais

---

D'accord à 100%
Qlist est un tableau de pointeur. Lors d'une opération de recopie, tu ne recopies que les pointeurs et pas les objets eux-même. Si tu as une QList de type complexe, c'est très intéressant.

Par contre, si tu utilises un type simple (char, double...), il n'y a plus aucun intérêt. C'est la cas par exemple des matrices et des heighmaps (tableau 2d de double de taille fixe en général). Dans ce cas, il vaut mieux créer un vecteur de dimension ligne*colonne et de créer les accésseurs qui vont bien (begin, end, begin_colonne, begin_ligne, begin_ligne, end_ligne, next_ligne, next_colonne, operator(x,y)...) de type STL-like

Citation:

---

Envoyé par gbdivers

Qlist est un tableau de pointeur. Lors d'une opération de recopie, tu ne recopies que les pointeurs et pas les objets eux-même. Si tu as une QList de type complexe, c'est très intéressant.

---

QList a pourtant un constructeur de copie qui recréer aussi les objets contenus, et non les pointeurs, je ne me trompe pas ?

Citation:

---

Envoyé par gbdivers

Par contre, si tu utilises un type simple (char, double...), il n'y a plus aucun intérêt. C'est la cas par exemple des matrices et des heighmaps (tableau 2d de double de taille fixe en général). Dans ce cas, il vaut mieux créer un vecteur de dimension ligne*colonne et de créer les accésseurs qui vont bien (begin, end, begin_colonne, begin_ligne, begin_ligne, end_ligne, next_ligne, next_colonne, operator(x,y)...) de type STL-like

---

Oui, mais c'est la taille fixe qui me gène, il n'y a pas un moyen pour avoir un tableau bidimensionnel à taille variable ? Je pensai que les QList suffisaient...

Les objets ne sont recopiés que lors du premier accès en écriture aux données (système COW).

Je pensais en particulier aux recopies lors des redimenssionment des vectors (si la nouvelle taille dépasse la taille resrvée) : on commence par créer un nouveau bloc mémoire de taille suffisante puis on recopie tous les éléments (des pointeurs dans le cas d'une QList, des objets dans le cas d'un vecteur).
C'est pour ça que lorsque l'on veut insérer beaucoup d'élément dans un std::vector (par exemple une boucle qui insère 100000 éléments à l'aide de push_back), on commence par faire un vector::reserve(size) pour ne pas refaire une réallocation mémoire avec copie à chaque push_back.
Et c'est pour ça que les std::list et autre sont plus efficace pour les opérations d'insertion/deletion/resize (implémenté en liste chainée)

Quand je parle de taille fixe, c'est que les opérations de resize sont souvent couteuse en temps, donc on évite de redimenssionner toute les 2 lignes. Mais la taille peut varier lors de l'execution.
C'est la cas d'une heighmap qui peut changer au cours du temps (en fonction de la résolution ou lors d'un resize de la fenêtre) mais les calculs sont fait sur une matrice de taille fixe (comprendre "fixe durant la phase de calcul")

Ca te laisse un 3eme type de conteneur à coder... basé sur les listes chainées (1 objet pointé = 1 cellule avec des pointeurs vers les éléments suivant) :)

Merci pour ta réponse, je vais faire un petit tri et m'y mettre :ccool:

Citation:

---

Envoyé par gbdivers

Par contre, si tu utilises un type simple (char, double...), il n'y a plus aucun intérêt.

---

Dans ce cas QList == QVector ;)

Citation:

---

Dans ce cas QList == QVector ;)

---

Pas exactement puisque QList est un tableau de pointeur alors que QVector est un tableau.
Ce qui fait que pour QList, la mémoire occupée est plus grande (sizeof(T)+sizeof(void*) vs sizeof(T) pour QVector) et l'accès neccessite un déréfrencement du pointeur. Dans le cas de grands tableaux (et dans l'embarqué ou les portables), cette différence peut être importante

Citation:

---

Envoyé par gbdivers

Pas exactement puisque QList est un tableau de pointeur alors que QVector est un tableau.
Ce qui fait que pour QList, la mémoire occupée est plus grande (sizeof(T)+sizeof(void*) vs sizeof(T) pour QVector) et l'accès neccessite un déréfrencement du pointeur. Dans le cas de grands tableaux (et dans l'embarqué ou les portables), cette différence peut être importante

---

Citation:

---

Internally, QList<T> is represented as an array of pointers to items of type T. If T is itself a pointer type or a basic type that is no larger than a pointer, or if T is one of Qt's shared classes, then QList<T> stores the items directly in the pointer array.

---

j'ai un doute maintenant :koi: c'est soit
sizeof(void*) vs sizeof(T) soit la même choses.
Mais ce n'est pas sizeof(T)+sizeof(void*) vs sizeof(T)

C'est bien un tableau de taille n*sizeof(void*) pour QList et n*sizeof(T) pour QVector. De plus, pour QList, les pointeurs pointent vers des objets T de taille sizeof(T). Donc on a bien une taille totale de n*(sizeof(void*)+sizeof(T)) pour QList (mais effectivement qu'un tableau de taille n*sizeof(void*))

Citation:

---

Envoyé par gbdivers

Donc on a bien une taille totale de n*(sizeof(void*)+sizeof(T)) pour QList (mais effectivement qu'un tableau de taille n*sizeof(void*))

---

tout dépend de la taille de T. C'est ce que dit la doc

:oops: En effet, j'avais oublié cette particularité de QList...
La prochaine fois, je ramènerais plus ma fraise un dimanche après un samedi soir très... tard :aie:

QVector assure également de stocker le tableau dans un segment mémoire adjecent, ce qui permet de récupérer éventuellement un pointeur sur les données et de les manipuler autrement.

Citation:

---

Envoyé par yan

j'ai un doute maintenant :koi: c'est soit
sizeof(void*) vs sizeof(T) soit la même choses.

---

la réponse est

sizeof(void*) vs sizeof(T).

C'est bien sizeof(void*) pour QList et sizeof(T) pour QVector ? Je ne me trompe pas ?

Citation:

---

Envoyé par Abdelite

C'est bien sizeof(void*) pour QList et sizeof(T) pour QVector ? Je ne me trompe pas ?

---

oui.