Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
2415 connectés 

  FORUM HardWare.fr
  Programmation

  [C++ STL] Quelles sont les différences entre vector et list?

 
 


Dernière réponse
Sujet : [C++ STL] Quelles sont les différences entre vector et list?
wpk dans la vraie vie, il est souvent preferable
d'avoir un tableau bien dimensionne en premier lieu
que d'avoir a le redimensionner meme avec un cout asymptotique nul, le cout c'est la souplesse, le gain c'est
la predictabilite et la limitation des couts "collateraux"
(recopie de tableaux, deplacement des objets pointes).

 
C'est ce que Verdoux et moi lui avons plus ou moins conseille de faire en utilisant un reserve ou en passant par un ctor qui reserve suffisament de place.
 
 
de plus avec ta facheuse tendance a parler en O(x)
on perd toute notion d'ordres de grandeurs veritables
qui sont les seuls interessants.
Un cout d'ajout dans une liste chainee est
toujours O(1) (independant de la longueur de la liste),  
mais evidemment ce n'est pas le meme
O(1) que l'ajout au sommet d'une pile (vecteur) (independant de la longueur de la pile). Tu n'en parles pas et c'est
la seule chose qui est importante ici.
 
euh, l'ajout dans un vecteur independament de sa longueur est en O(1) amorti, ca peut parraitre trompeur comme expression je te l'accorde.
 
 
Pour un acces sequentiel, le vecteur est gagnant d'un poil
(memoire contigue). Pour un acces aleatoire le vecteur
est gagnant mais il ne faut evidemment pas faire n'importe
quoi (on n'accede pas avec des indices sur une liste, on n'accede
pas avec des pointeurs sur un vecteur).
Pour une insertion, c'est plus une affaire d'arbitrage.
Il est errone d'ajouter des elements au milieu d'un vecteur quand par ailleurs on utilise des indices pour adresser les elements. Mais parfois seule la rapidite entre en jeu et dans ce cas la, il faut choisir au cas par cas entre la perte de temps liee a cette operation d'ajout (qui peut intervenir de maniere tres limitee) et les surcouts lies a l'utilisation des listes par ailleurs.  
Si par exemple l'insertion est imposee par une methode de tri,
il peut etre preferable de changer de methode de tri si la structure de donnee adoptee permet des gains appreciables par ailleurs.

 
Entierement d'accord faut choisir au cas par cas (c'est ce que j'ai d'ailleurs egalement mentioné plus haut en proposant une liste voire une DQ) mais pour savoir quoi choisir, faut au moins connaitre la theorie ;)
 

Au cas par cas: Mefiez vous des formules toutes faites.
plus c'est theorique, moins il y a de chances
que la personne qui a ecrit a reflechi a votre probleme.
Ca ne veut pas dire qu'elle a faux, ca veut
dire qu'il faut donc brancher votre cerveau
pour voir si ca s'adapte a votre cas particulier.
 
LEGREG  
 
ouais, on peut certes bidouiller dans son coin pour ecrire son ptit soft en faisant tout plein de tests pour comprendre comment ca marche. C'est pas ce qui est le plus rapide, efficace et lisible. Je partirais plutot de la theorie. Le choix du meilleur conteneur, du meilleur algo, etc... est alors fait en toute connaissance de cause et pas seulement sur des suputations empiriques.

 

[jfdsdjhfuetppo]--Message édité par wpk--[/jfdsdjhfuetppo]

Votre réponse
Nom d'utilisateur    Pour poster, vous devez être inscrit sur ce forum .... si ce n'est pas le cas, cliquez ici !
Le ton de votre message                        
                       
Votre réponse
[b][i][u][strike][spoiler][fixed][cpp][url][email][img][*]   
 
   [quote]
 
Options

 
Vous avez perdu votre mot de passe ?


Vue Rapide de la discussion
wpk dans la vraie vie, il est souvent preferable
d'avoir un tableau bien dimensionne en premier lieu
que d'avoir a le redimensionner meme avec un cout asymptotique nul, le cout c'est la souplesse, le gain c'est
la predictabilite et la limitation des couts "collateraux"
(recopie de tableaux, deplacement des objets pointes).

 
C'est ce que Verdoux et moi lui avons plus ou moins conseille de faire en utilisant un reserve ou en passant par un ctor qui reserve suffisament de place.
 
 
de plus avec ta facheuse tendance a parler en O(x)
on perd toute notion d'ordres de grandeurs veritables
qui sont les seuls interessants.
Un cout d'ajout dans une liste chainee est
toujours O(1) (independant de la longueur de la liste),  
mais evidemment ce n'est pas le meme
O(1) que l'ajout au sommet d'une pile (vecteur) (independant de la longueur de la pile). Tu n'en parles pas et c'est
la seule chose qui est importante ici.
 
euh, l'ajout dans un vecteur independament de sa longueur est en O(1) amorti, ca peut parraitre trompeur comme expression je te l'accorde.
 
 
Pour un acces sequentiel, le vecteur est gagnant d'un poil
(memoire contigue). Pour un acces aleatoire le vecteur
est gagnant mais il ne faut evidemment pas faire n'importe
quoi (on n'accede pas avec des indices sur une liste, on n'accede
pas avec des pointeurs sur un vecteur).
Pour une insertion, c'est plus une affaire d'arbitrage.
Il est errone d'ajouter des elements au milieu d'un vecteur quand par ailleurs on utilise des indices pour adresser les elements. Mais parfois seule la rapidite entre en jeu et dans ce cas la, il faut choisir au cas par cas entre la perte de temps liee a cette operation d'ajout (qui peut intervenir de maniere tres limitee) et les surcouts lies a l'utilisation des listes par ailleurs.  
Si par exemple l'insertion est imposee par une methode de tri,
il peut etre preferable de changer de methode de tri si la structure de donnee adoptee permet des gains appreciables par ailleurs.

 
Entierement d'accord faut choisir au cas par cas (c'est ce que j'ai d'ailleurs egalement mentioné plus haut en proposant une liste voire une DQ) mais pour savoir quoi choisir, faut au moins connaitre la theorie ;)
 

Au cas par cas: Mefiez vous des formules toutes faites.
plus c'est theorique, moins il y a de chances
que la personne qui a ecrit a reflechi a votre probleme.
Ca ne veut pas dire qu'elle a faux, ca veut
dire qu'il faut donc brancher votre cerveau
pour voir si ca s'adapte a votre cas particulier.
 
LEGREG  
 
ouais, on peut certes bidouiller dans son coin pour ecrire son ptit soft en faisant tout plein de tests pour comprendre comment ca marche. C'est pas ce qui est le plus rapide, efficace et lisible. Je partirais plutot de la theorie. Le choix du meilleur conteneur, du meilleur algo, etc... est alors fait en toute connaissance de cause et pas seulement sur des suputations empiriques.

 

[jfdsdjhfuetppo]--Message édité par wpk--[/jfdsdjhfuetppo]
bjone :hello: legreg
LeGreg

wpk a écrit a écrit :

 Ceci presente l'avantage de reduire le nb des redimensionnement donc d'augmenter la vitesse au detriment de l'encombremenet de la mem.
Du fait du nb de + en + faible des redimensionnements, on peut considérer que la complexité asymptotique (ou amortie) de l?opération d?ajout en fin de vecteur est en O(1).



 
dans la vraie vie, il est souvent preferable
d'avoir un tableau bien dimensionne en premier lieu
que d'avoir a le redimensionner meme avec un cout asymptotique nul, le cout c'est la souplesse, le gain c'est
la predictabilite et la limitation des couts "collateraux"
(recopie de tableaux, deplacement des objets pointes).
 
de plus avec ta facheuse tendance a parler en O(x)
on perd toute notion d'ordres de grandeurs veritables
qui sont les seuls interessants.
Un cout d'ajout dans une liste chainee est
toujours O(1) (independant de la longueur de la liste),  
mais evidemment ce n'est pas le meme
O(1) que l'ajout au sommet d'une pile (vecteur) (independant de la longueur de la pile). Tu n'en parles pas et c'est
la seule chose qui est importante ici.
Pour un acces sequentiel, le vecteur est gagnant d'un poil
(memoire contigue). Pour un acces aleatoire le vecteur
est gagnant mais il ne faut evidemment pas faire n'importe
quoi (on n'accede pas avec des indices sur une liste, on n'accede
pas avec des pointeurs sur un vecteur).
Pour une insertion, c'est plus une affaire d'arbitrage.
Il est errone d'ajouter des elements au milieu d'un vecteur quand par ailleurs on utilise des indices pour adresser les elements. Mais parfois seule la rapidite entre en jeu et dans ce cas la, il faut choisir au cas par cas entre la perte de temps liee a cette operation d'ajout (qui peut intervenir de maniere tres limitee) et les surcouts lies a l'utilisation des listes par ailleurs.  
Si par exemple l'insertion est imposee par une methode de tri,
il peut etre preferable de changer de methode de tri si la structure de donnee adoptee permet des gains appreciables par ailleurs.
 
Au cas par cas: Mefiez vous des formules toutes faites.
plus c'est theorique, moins il y a de chances
que la personne qui a ecrit a reflechi a votre probleme.
Ca ne veut pas dire qu'elle a faux, ca veut
dire qu'il faut donc brancher votre cerveau
pour voir si ca s'adapte a votre cas particulier.
 
LEGREG

Krueger Ah ok je vois. Merci.
wpk

Krueger a écrit a écrit :

Que veux-tu dire par le terme "amorti"?  




 
D'apres Andrew Koenig, la technique la plus efficace pour gerer le besoin de croissance dynamique des tableaux, consiste à utiliser un redimensionnement exponentiel. Chaque reallocation fait augmenter la taille par un facteur 1+a a>0 (a=1 que chez Micro$oft et c'est pas le plus efficace). Ceci presente l'avantage de reduire le nb des redimensionnement donc d'augmenter la vitesse au detriment de l'encombremenet de la mem.
Du fait du nb de + en + faible des redimensionnements, on peut considérer que la complexité asymptotique (ou amortie) de l?opération d?ajout en fin de vecteur est en O(1).

Krueger Que veux-tu dire par le terme "amorti"?
wpk

bjone a écrit a écrit :

je sais, là n'est pas le reproche, c la manière d'effectuer le redimmentionnement qui est pas -bo-  




 
qcq elements de rappel sur les vecteurs:
 
 Accès indexé aux éléments en O(1)
 Ajout ou suppression d?un élément à la fin du vecteur sans
redimensionnement en O(1)
 Ajout ou suppression d?un élément à la fin du vecteur avec
redimensionnement en O(n)
 Ajout ou suppression d?un élément à la fin du vecteur en O(1) amorti
 Ajout ou suppression d?un élément au milieu du vecteur en O(n) où n est la taille du vecteur
 
ce qui est, contrairement, à ce que tu affirmes tres bien (si tu peux proposer mieux je suis preneur). De plus, Verdoux a tout à fait raison, si tu fais un reserve suffisant (ou si à la construction tu utilise le ctor
 
explicit vector(size_type n, const T& v = T(), const A& al = A());
 
avec un n qui correspond à tes besoins, t'as une insertion en O(1).
 
Si tu veux avoir une insertion/suppression en O(1), tu utilise une liste à la place, tu perds du coup l'acces indexé en O(1).
 
Si tu veux un compromis, tu peux utiliser les deque pour lesquelles l'insertion en debut et au milieu sont plus rapides que sur un vecteur et l'indexation est en o(log(n)) amortie...

bjone je sais, là n'est pas le reproche, c la manière d'effectuer le redimmentionnement qui est pas -bo-
verdoux C'est juste qu'il faut comprendre le fonctionnement des vecteurs de la STL.
Leur capacité suit une loi géométrique et tu peux en fixer la valeur initiale.
bjone wpk> je suis d'accord pour le 2, mais moins pour le 1, et si tu testes mon exemple, tu verras bien que le vector te crée 2 tableau et fait une recopie... (ce que je n'aime pas c tout ;) )
bjone je suis d'accord avec vous deux, mais fo reconnaitre, que la stl est pas idéal en perfs d'un point de vue implémentation...
wpk bjone>
 
1. Le facteur avec lequel est multiplié la taille initiale n'est jamais 2 (mais un peu moins 1.xx) enfin c'est qu'un detail.
 
2.Il faut savoir utiliser les choses pour ce qu'elles sont faites. Si tu improvise live et si tu ne reflechis pas sur le bon conteneur a utiliser, faut pas venir te plaindre que ton programme est lent et mal ecrit...
verdoux C'est parce que la capacité de ton vector est faible.
Essaie:

Code :
  1. vector<mint> miv;
  2. miv.reserve(10);
bjone par contre fait gaffe, la stl est boeuf....
 
par exemple que tu fais un push_back() avec un vector pour ajouter un élément, le vector ne fait pas de réalloc, il fait un new d'un nouveau tableau de la taille de l'ancien+1, ça fait que que si tu as 100 mo de données en vector (oki c violent :D), tu vas avoir un peu plus que 200 mo d'utilisation crête au moment de l'ajout.....
le tout en utilisant la construction/destruction/recopie lors de la recopie du tableau (dans les règles de l'art du c++ quoi ;) )
 
fait toi une classe type:
 
#include <vector>
#include <iostream>
 
using namespace std;
 
class mint
{
 
public:
 
 int v;
 
 mint(int i)
 {
  v=i;
  cout<<"Cstr Int "<<v<<" "<<this<<endl;
 }
 
 mint()
 {
  cout<<"Cstr "<<v<<" "<<this<<endl;
 }
 
 ~mint()
 {
  cout<<"Dstr "<<v<<" "<<this<<endl;
 }
 
 mint(const mint &j)  
 {
  v=j.v;
  cout<<"Copy "<<j.v<<" "<<this<<"<-"<<&j<<endl;
 }
 
 operator = (int i)
 {
  v=i;
  cout<<"= "<<this<<endl;
 }
};
 
 
void vector_mint()
{
 vector<mint> miv;
 
 miv.push_back(6);
 cout<<endl<<"push_back(3)"<<endl;
 miv.push_back(3);
 cout<<endl<<"push_back(2)"<<endl;
 miv.push_back(2);
 
 cout<<"Ret"<<endl;
}
 
void vector_int()
{
 vector<int> iv;
 
 iv.push_back(1);
 iv.push_back(2);
 iv.push_back(3);
 iv.push_back(4);
 
 int i,sze=iv.size();
 
 for(i=0;i<sze;i++)
  cout<<iv[i]<<"  ";
 
 cout<<endl;  
 
 int *P=iv.begin();
 
 for( i=0 ; i < sze ; i++)
  cout<<*P++<<"  ";
 
 cout<<endl;
 
 cout<<iv[10]<<endl;
 
 try {
  cout<<iv.at(10)<<endl;
 }
 
 catch(out_of_range e)
 {
  cout<<e.what<<endl;
 }
 
 cout<<endl;
 
 
}
 
main()
{
 vector_mint();
 
 return 0;
}
 
et regarde toutes les constructions/destructions/recopies :D :(
 
au début j'étais super cho pour la STL, maintenant que je vois ça j'ai peur que le cpu passe son temps à faire des mov.
Alload Nan, tout ce que j'ai appris c'est par moi-même dans les bouquins ou grâce à vous du forum.
LeGreg

Alload a écrit a écrit :

Mais il doit bien avoir des défauts à la list qu'il n'y a pas dans le vector? Nan?



vector = memoire contigue. passage d'un element au suivant
par un simple incrementation de pointeur, allocation en bloc.
list = memoire discontinue, passage d'un element au suivant par deferencement de pointeur, allocation/desallocation par element.
 
Tu n'as jamais suivi de cours d'algorithmique?
 
A+
LEGREG

wpk c'est plus gros en taille, t'as pas l'acces indexé...
Alload Mais il doit bien avoir des défauts à la list qu'il n'y a pas dans le vector? Nan?
wpk qd tu efface un elt ds un vecteur, y'a deplacement, pareil pour l'insertion. Une list c'est une liste chainée, ca va plus vite, y'a pas de recopie

 

[jfdsdjhfuetppo]--Message édité par wpk--[/jfdsdjhfuetppo]
Alload J'ai cherché la doc sur les vectors et les lists de la STL, et j'ai pas trouvé de différence évidentes, d'accord j'ai pas fuiné dans les fonctions, mais d'après le petit descriptif les deux permettent un accès aléatoire, des rajouts et des effacements aléatoires.
 
Alors je vois pas bien où se situe la différence, donc si vous pouviez m'apporter un peu de votre savoir :)

 

[jfdsdjhfuetppo]--Message édité par Alload--[/jfdsdjhfuetppo]

Forum MesDiscussions.Net, Version 2010.2
(c) 2000-2011 Doctissimo

Copyright © 1997-2025 Groupe LDLC (Signaler un contenu illicite / Données personnelles)