parcourrir un vector, efficacement

Bonjour,
souvent je me demande quelle la meilleure façon de parcourir un vector :
soit :

Code:

---

1 2 3 4

unsigned int NbElts = m_Vector.size(); for (unsigned int i=0; i<NbElts; i++) // faire quelque chose

---

ou alors :

Code:

---

1 2 3

for (unsigned int i=0; i<m_Vector.size(); i++) // faire quelque chose

---

ou bien encore en utilisant les itérateurs... mais j'ai souvent besoin de l'index, d'où l'utilité du "i".

A votre avis laquelle des trois méthodes est la plus rapide ?

Entre un seul appel à size() avant la boucle, et un à chaque tour, le choix est vite fait. Par contre comme ce n'est très probablement pas ça qui ralentira ton application, je crois que tu peux ne pas te prendre la tête sur ce genre de considération...

Sinon, quand tu n'as pas besoin de l'indice les itérateurs sont bien sûr préférables.

Citation:

---

Envoyé par Loulou24

Sinon, quand tu n'as pas besoin de l'indice les itérateurs sont bien sûr préférables.

---

Tout à fait d'accord. J'ajouterais que c'est préférable d'une part pour un bon style, mais peut-être aussi pour les performances.

Personnelement je préfère m'en passer. Je trouve l'écriture plus lisible / légère / proche d'un tableau à la C. Pour les performances je suis sceptique.

Code:

---

1 2 3 4

for (size_t i=0, size=m_Vector.size(); i<size; i++) { }

---

Code:

---

1 2 3 4 5 6

for ( std::vector<int>::const_iterator i = m_Vector.begin(), std::vector<int>::const_iterator end = m_Vector.end(); i != end; i++ ) { }

---

Citation:

---

Envoyé par Aurelien.Regat-Barrel

Pour les performances je suis sceptique.

---

Evidemment, cela dépend grandement du contexte. Mais pose toi la question de savoir quel est le plus rapide entre ces deux codes:

Code:

---

1 2 3 4 5 6 7 8

const int n; int v[];   for ( int i = 0 ; i < n ; i++ ) { // Accès à v via v[i]; }

---

Code:

---

1 2 3 4 5 6 7 8

const int n; int v[];   for ( int* i = v ; i < v+n ; i++ ) { // Accès à v via *i. }

---

La réponse est : ça dépend.
Pour les itérateurs, tu conviendra que c'est sensiblement la même chose.

PS: Quand je disais "pour un bon style", je pensais surtout à ce qui venait ensuite. C'est sûr que si c'est juste pour parcourir un tableau, je vais pas faire le snob et parler de style.

En terme de rapidité, il ne devrait pas y avoir trop de différence sur un vecteur.
Ce qui peut changer, c'est le précalcul de la borne de fin -- d'où la supériorité des algorithmes de la SL quand on dispose de foncteurs adaptés, ce qui peut être un peu lourd à écrire parfois.

Sinon, je préfère systématiquement l'écriture itérateur. Il est plus simple de changer de conteneur dans les zones de parcourt si le besoin s'en fait sentir.
Je réserve l'accès tableau aux fois où j'ai besoin d'un accès direct, ou à celles où les itérateurs pourraient être invalidés.

Citation:

---

Envoyé par Selenite

La réponse est : ça dépend.
Pour les itérateurs, tu conviendra que c'est sensiblement la même chose.

---

Biensûr que ça dépend. Mais encore mieux : on s'en fiche. La performance, à mon avis, n'est pas un critère ici.
Celà dit ton exemple est légèrement discutable, car, avec un conteneur STL, l'itérateur est une classe, et on se paye les opérateurs ++ et != en plus. On peut supposer que le compilo optimise bien tout ça. Mais j'avais fait le test du temps de VC++ 6 et l'accès direct était légèrement avantagé. D'où mon "scepticisme" ;)

Euh. Sous VC++, je me souviens d'un std::vector<>::iterator qui était en fait un pointeur. Pour listes et autres conteneurs c'est effectivement obligatoirement une classe, mais là l'accès direct n'est de toutes façons pas comparable : le conteneur n'est pas conçu pour être efficacement accédé de la sorte, la complexité grimpe.

Après, entre pré-incrémentation préventive et utilisation de constantes (pour l'arrêt) précalculées avant le for il ne devrait pas y avoir de différences je pense. A moins que le compilo ne sache pas dérouler la notation pointeur, mais j'en serais surpris.

Sinon, on s'en fiche, je suis parfaitement d'accord!