Discussion :

[Colbix]

Voila, la question est surement très bête, mais je voulais savoir comment afficher le Xième élément d'une slist...

J'ai été voir sur http://www.sgi.com/tech/stl/Slist.html, mais je n'ai pas trouvé...

Merci d'avance

[Syrmonsieur]

Si tu veut accéder au Nième élément, alors tu as sans doute choisi le mauvais conteneur.

Une liste permets un accès séquentiel, cad pour accéder au nième élément, tu doit parcourir les n-1 éléments précédents.

Pour un accès aléatoire, utilise plutôt vector.

Aussi si tu veux réellement une liste, slist n'est pas dans le standard et, à mon avis, apporte peu par rapport à une classique doublement chainée std::list (économie de mémoire : 1 pointeur par élément, économie de calcul : pas grand chose à mon avis)

[Laurent Gomila]

Au cas où : slist est une extension de la STL SGI, ce n'est pas une classe standard. Pour accéder au x-ème élément d'une liste il faut utiliser std::advance.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
slist<int>::iterator It = l.begin();
std::advance(It, x);

[Syrmonsieur]

Je ne connaissais pas std::advance.

Dans tout les cas, en interne, il faut parcourir la liste, ce qui est très lent.

Accès aléatoire rapide (temps constant) => std::vector

++

[Colbix]

Merci pour les infos, pour ce qui est du vector, je n'en au pas besoin ici parceque ma liste va beaucoup changer, dans le cas du vector, si il grandi trop, il sera recopier en mémoir avec un Malloc plus grande. Donc j'ai besoin de la liste pour diminuer les recopiages au détriment du parcours de la liste...

Je vais essayer avec std::advance(It, x)...

Je vous tiens au courant !

A bientôt !

[loufoque]

std:multi)set ?

[alskaar]

Merci pour les infos, pour ce qui est du vector, je n'en au pas besoin ici parceque ma liste va beaucoup changer, dans le cas du vector, si il grandi trop, il sera recopier en mémoir avec un Malloc plus grande. Donc j'ai besoin de la liste pour diminuer les recopiages au détriment du parcours de la liste...

Je vais essayer avec std::advance(It, x)...

Je vous tiens au courant !

A bientôt !

et tu connais pas la taille a l'avance ?

[Alp]

On dirait bien que non...
Si le conteneur doit souvent grandir, souvent "changer de taille", le vector risque d'être vraiment lent comparé à une list.
De plus, parcourir avec advance est assez pratique, mais c'est en O(n)... Il faut tester les performances du code avec une list et un vector sur une mise en situation.

[Sylvain Togni]

Si le conteneur doit souvent grandir, souvent "changer de taille", le vector risque d'être vraiment lent comparé à une list.

Au contraire, sauf si les objets sont vraiment très lourds à copier, std::vector sera bien plus rapide que std::list. Example :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <ctime>
#include <iostream>
#include <vector>
#include <deque>
#include <list>
 
template<typename C>
double test()
{
  clock_t t0 = std::clock();
  for(int n = 10; n > 0; --n)
  {
    C c;
    for(int i = 1000000; i > 0; --i)
    {
      c.push_back(i);
    }
  }
  return double(std::clock() - t0)/CLOCKS_PER_SEC;
}
 
int main()
{
  std::cout << "vector:\t" << test< std::vector<int> >() << "s\n";
  std::cout << "deque:\t" << test< std::deque<int> >() << "s\n";
  std::cout << "list:\t" << test< std::list<int> >() << "s\n";
}

donne chez moi

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
vector: 0.5s
deque:  3s
list:   11s

[loufoque]

Je vois que mon message n'a pas été pris en compte.
set::set ou std::multiset permettent la recherche et l'insertion n'importe où en temps logarithmique.
Comme c'est à base de noeuds, il n'y a pas de déplacement à faire quand la capacité ne suffit pas.

[Alp]

Non mais une fois très grand. C'est pas le fait même de resizer qui est lent, bien sûr que le vector est plus rapide que list dans ce cas.
Mais s'il faut effectuer des copies ensuites avec un très gros vector, prenant une sacrée place en mémoire, là ca sera dur.
Enfin, le mieux est de contourner la copie.

Toujours est-il que le sujet est résolu

[alskaar]

Je vois que mon message n'a pas été pris en compte.
set::set ou std::multiset permettent la recherche et l'insertion n'importe où en temps logarithmique.
Comme c'est à base de noeuds, il n'y a pas de déplacement à faire quand la capacité ne suffit pas.

effectivement loufoque mais dans la mesure ou la question de base est de savoir
comment acceder au Nieme element
on suppose que l'ordre d'insertion a son importance ...
tu vas certainement nous repondre qu'on peut avoir une clef du set qui est un index a increment...