Discussion :

[salseropom]

Bonjour, qu'elle est la différence majeure entre ces quatre lignes ?

double tab[5];
vector<double> tab(5);
list<double> tab(5);
deque<double> tab(5);

Quelle ligne est la mieux en tant que temps d'accès à un élément ?
Et si j'ai le choix, que me conseillez-vous ?

merci beaucoup

[bigboomshakala]

tout dépend de ce que tu as besoin.

vector : tu accèdes aux éléments par leur indice.
list : tu accèdes à l'élément suivant/précédant

il faut aussi penser à l'insertion/suppression éventuelle d'éléments
...

même si tu prends la structure la plus rapide en terme d'accès d'un élément à un autre, si elle n'est pas adapté à ton problème, ça ne sera pas la solution optimale.

[Laurent Gomila]

Les conteneurs de la bibliothèque standard ont chacun leurs avantages / inconvénients. En l'occurence pour chaque opération ils n'auront pas la même complexité, il faudra donc choisir le bon selon ce que tu vas en faire.

L'important c'est d'avoir en tête la structure de donnée qui est (généralement) utilisée pour implémenter chacune de ces structures :

- Tableau dynamique contigü en mémoire pour std::vector
- Liste de tableaux pour std::deque
- Liste doublement chaînée pour std::list

Donc pour l'accès :

- std::vector permet un accès indicé en temps constant, comme les tableaux style C.
- std::list permet un accès en temps linéaire.
- std::deque permet un accès indicé en temps logarithmique (à vérifier ?)

Ensuite il faut voir si tu as des insertions, des recherches, des suppressions, ...

Et ne pas oublier non plus les conteneurs associatifs : std::map, std::multimap, std::set et std::multiset.

[Selenite]

double tab[5];
Temps d'accès, d'initialisation et de destruction optimal. Impossibilité de rajouter des éléments.


vector<double> tab(5);
Temps d'accès quasi-optimal. Temps d'initialisation et de destruction un peu moins. On peut ajouter ou supprimer rapidement des éléments à la fin du tableau. Plus lent au début ou au milieu du tableau.


list<double> tab(5);
Temps d'accès, d'initialisation et de destruction plutôt lent. Ajout, suppression et insertion d'élement n'importe où en temps constant. Les éléments ne sont pas contigu en mémoire. Le temps d'accès aléatoire est plutôt lent, mais parcourir le tableau et rapide.


deque<double> tab(5);
Temps d'accès rapide. Temps d'initialisation et de destruction un peu moins. Eléments contigus en mémoire. Insertion et déletion rapides à la fin ET au début du tableau. Lent au milieu.



Donc le choix dépend vraiment de tes besoins.


PS: Quand je dis lent, c'est relatif. Si as une machine de moins de 15 ans, toutes les opérations sont quasiment instantané. La lenteur se fait ressentir si tu fais des appels répétés.

[salseropom]

Merci de vos nombreuses réponses.
En fait je suis en train de reprendre un prgm matlab et le mettre en C++. J'ai des tableaux de constantes que j'avais codés par des double tab[27][3] par exemple mais j'ai quelques tableaux pour lesquels je dois rajouter des valeurs à la fin au cours de chaque itérations (et j'en ai plus d'un million) d'où ma question sur le temps d'accès à un élément.

Vu ce que vous m'avez répondu, je vais opter pour des vector.

Merci

[Selenite]

Taille constante: double[] où vector<double>.

Ajout d'élément en fin de tableau: vector<double>

Voila ;-).

[JolyLoic]

- std::vector permet un accès indicé en temps constant, comme les tableaux style C.
- std::list permet un accès en temps linéaire.
- std::deque permet un accès indicé en temps logarithmique (à vérifier ?)

Ma lecture de la norme (table 68 ) indique un accès en temps constant pour std::deque.

deque<double> tab(5);
Temps d'accès rapide. Temps d'initialisation et de destruction un peu moins. Eléments contigus en mémoire. Insertion et déletion rapides à la fin ET au début du tableau. Lent au milieu.

Les éléments d'un deque ne sont pas continus en mémoire.

[Selenite]

deque<double> tab(5);
Temps d'accès rapide. Temps d'initialisation et de destruction un peu moins. Eléments contigus en mémoire. Insertion et déletion rapides à la fin ET au début du tableau. Lent au milieu.

Les éléments d'un deque ne sont pas continus en mémoire.

C'est vrai ;-). Au temps pour moi.

[salseropom]

Merci !
J'ai tout de même gagné 2h 40 par rapport au prgm Matlalb !!
Merci bcp