Comment correctement parcourir un vector en C++14 et plus

**Matthieu76** · 28/02/2018, 00h30

Bonjour, quelle est le mieux et pourquoi ? Quelle est le plus rapide ? (Et venez pas faire c**** à dire que la vitesse c'est pas le plus important et bla bla bla lisibilité bla bla bla. Je le sais très bien)

SOLUTION 1 :

Code :

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

1
2
3
4
5
 
for(unsigned int i = 0; i < v.size(); i++) // D’ailleurs, i++ ou ++i ?
{
        v[i] = 1;
}

SOLUTION 2 :

Code :

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

1
2
3
4
5
 
for (auto& i : v) // Convertie en solution 3 à la compilation ?
{
        i = 1;
}

SOLUTION 3 :

Code :

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

1
2
3
4
5
 
for (std::vector<int>::iterator i = myvector.begin() ; i != myvector.end(); i++)
{
        *i = 1;
}

Je sais que ce sujet à été maintes et maintes fois traiter mais je voulais votre avis sur la question.

Et sinon dans quelle ordre est-il péférable de parcourir un vector, de 0 à size ou de size à 0 ?

**JolyLoic** · 28/02/2018, 09h57

La 1 et la 3 présentent le risque que le compilateur ne sorte pas de la boucle le calcul de v.size() / v.end().
Mais je crois que globalement les différences, s'il y en a, vont être minimes, et que si tu en es à ce niveau de finesse, il y aura probablement d'autres choses qui vaudront le coup d'être regardées (vector de structures / structure de vectors, vectorisation des instructions...), et les resultats peuvent dépendre de la situation (donc, mesurer, mesurer et mesurer).

Pour ta deuxième question, je ne sais pas trop. J'aurais tendance à penser sans aucune preuve qu'aller de 0 à n est plus courant, dont probablement mieux optimisé.

**Bktero** · 28/02/2018, 12h31

Je dirais la 2, à cause d'une expérimentation que j'ai faite ces jours-ci (https://gradot.wordpress.com/2018/02...-ce-quil-fait/) où gcc optimisait (un peu) mieux un parcours de tableau avec cette écriture.

L'écriture 2 est sans ambiguïté pour le compilateur qui peut alors appliquer toutes les optimisations à sa disposition.

**dalfab** · 28/02/2018, 18h27

Ici j'utiliserais plutôt une quatrième option :

Code :

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

std::fill( begin(v), end(v), 1 );

Si le compilateur fait son boulot correctement, toutes les 4 devraient donner exactement le même code. La première préconise l'utilisation d'index, les 3 autres l'utilisation d'itérateurs, mais le compilateur peut voir qu'il n'y a aucun effet de bord et choisir son moyen d'itérer.
Les 4 ajoutent inutilement une contrainte de faire une mise à jour dans l'ordre. L'optimiseur pourrait ici effectuer une mise à jour en partant de la fin car cela est parfois un peu plus optimal (on peut ôter une contrainte sur un registre processeur) à condition qu'il détecte qu'ici il n'y a aucun effet de bord.
On pourrait "aider" l'optimiseur en utilisant std::fill( std::execution::par_unseq , begin(v), end(v), 1 ); pour mieux signifier que l'on se fout ici de la chronologie, mais là c'est peut être risqué quand on voit que des optimiseurs n'arrivent pas à voir que les 4 premiers cas sont vraiment identiques, et pourrait ici compliquer inutilement le code.

**LittleWhite** · 01/03/2018, 11h25

Bonjour,

La solution avec std::fill est intéressante, notamment car cela pourrait être parallélisé par l'implémenteur. J'ose croire que c'est vers quoi les nouvelles version tendent, non ?
Par contre, ce n'est pas un parcours générique, c'est un remplissage

.

**Matthieu76** · 01/03/2018, 13h49

Envoyé par LittleWhite

Par contre, ce n'est pas un parcours générique, c'est un remplissage

.

Oui, ma question s'orientait plus sur le parcours du vector que sur le remplissage de celui-ci.

La solution 2 me parait effectivement la mieux mais je suis obligé d'utiliser sur la solution 1 quand il y a 2 vectors dans ma boucle c'est pour cela que dans mon code j'utilise tout le temps la solution 1, en plus je la trouve plus compréhensible car dans mon code j'ai des variables du genre numberOfNeurons = neurons.size().

Avec des trucs du genre :

Code :

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

1
2
3
4
for(unsigned int i = 0; i < numberOfNeurons; i++)
{
    result[i] = neurons[i].calculateOutput();
}

Es-ce que cette implémentation est correct ? Avez-vous autre chose de mieux à proposer ?

Personnellement je préfère ne pas mélanger les implémentations, du coup j'utilise tout le temps la solution 1.

**wolinn** · 01/03/2018, 14h06

J'avais fait des tests pour comparer 1 et 2, sur des grands tableaux, sans mesurer de différence significative, avec g++. Et pourtant, je fais attention à ce genre de chose (applications de calcul intensif).
Du coup, j'utilise indifféremment les deux syntaxes, suivant la lisibilité.
La forme 1 est toujours intéressante pour la lisibilité, pour retrouver dans le code du corps de la boucle les indices des formulations mathématiques.
Mais la forme 2 est aussi intéressante quand l'indexation a moins d'importance.

**LittleWhite** · 01/03/2018, 14h20

Il ne faut pas oublier que la solution 2 permet de prendre n'importe quel iterable, sans avoir à retoucher le code. Pour que ce soit le cas avec la solution 3, il faut utiliser auto, afin d'éviter de spécifier un type fixe. Pour la solution 1, il faut avoir un size() (vrai pour la majorité des cas, mais pas non plus à 100 %).
Pour la solution 3, il faut plutôt utiliser ++i. Cela n'a pas d'importance pour les types de base, mais l'itérateur n'en est pas un

.

**koala01** · 01/03/2018, 17h16

Salut,

Comme jolyloic, je crois que, avant de t'inquiéter de ce genre de choses, il y a beaucoup d'autres points à aborder...

La priorité, pour une optimisation, est de travailler sur l'algorithme,l'idéal étant, d'obtenir une complexité dans l'ordreO(1) ou O(log(n)) ou O(n)ou O(n * log(n)) ou enfin O(n²) et supérieure. Autrement, des techniques "simples" permettent également de gagner des performances "à peu de frais", comme

le fait d'éviter les copies inutiles: cela rajoute -- certes -- une indirection, mais cela permet de gagner le temps nécessaire à la copie, qui est généralement bien supérieur à celui "perdu" par le fait de devoir suivre l'indirection
le fait d'éviter les autant que possible cache misses, car, quand une donnée n'est pas dans un des caches du processeur, il perd un max de temps
le fait de choisir la collection ad-hoc pour le traitement que l'on doit effectuer, bien que seuls les tableaux (et peut être std::dequeue) soient effectivement à même d'éviter les cache misses

Et je confirme que la seule manière d'avoir une certitude dans une situation particulière est de mesurer, et de mesurer encore

Pour le reste, je pense que les essais effectués par les autres ont donné la réponse à ta question, et, comme les résultats semblent indiquer qu'il n'y a que peu (voire pas du tout) de différence, autant utiliser la solution qui te permettra le maximum d'expressivité pour chaque situation particulière

**Matthieu76** · 02/03/2018, 09h59

Envoyé par LittleWhite

Pour la solution 3, il faut plutôt utiliser ++i. Cela n'a pas d'importance pour les types de base, mais l'itérateur n'en est pas un

.

Ouais d'accord mais pourquoi ?

Envoyé par koala01

autant utiliser la solution qui te permettra le maximum d'expressivité pour chaque situation particulière

D'accord merci

Je me disais juste que faire des boucles for(int i=0 ; i < v.size(); i++) ce n'était peut-être pas très moderne comme façon de faire et qu'on ne faisait plus ça dans des projets récents.

**LittleWhite** · 02/03/2018, 10h18

https://cpp.developpez.com/faq/cpp/?...s-ou-plusplusi
https://stackoverflow.com/a/17367081
(Je réponds des liens, car je ne sais pas le formuler correctement.)

**Bousk** · 02/03/2018, 10h27

i++ retourne la valeur courante de i puis l'incrémente : y'a forcément une copie créée
++i incrémente puis retourne i

Je me disais juste que faire des boucles for(int i=0 ; i < v.size(); i++) ce n'était peut-être pas très moderne comme façon de faire et qu'on ne faisait plus ça dans des projets récents.

Déjà c'est quoi un projet récent ? Un projet qui utilise que du C++17 et s'interdit tout autre chose ?
Pourquoi on ne ferait plus ça si ça marche ? Sans compter les millions de fois où ce code existe dans des projets et donc il faut toujours le connaître pour le comprendre.
As-tu une quelconque alternative si tu as besoin d'un index ?
size retourne un size_t

**Luc Hermitte** · 02/03/2018, 13h17

Envoyé par Matthieu76

Code :

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

1
2
3
4
for(unsigned int i = 0; i < numberOfNeurons; i++)
{
    result[i] = neurons[i].calculateOutput();
}

Est-ce que cette implémentation est correct ? Avez-vous autre chose de mieux à proposer ?

Personnellement je préfère ne pas mélanger les implémentations, du coup j'utilise tout le temps la solution 1.

Le problème ici, c'est calculateOutput(). Suivant comment c'est foutu, cela va te faire perdre la vectorisation. Et au final, le comment la boucle est réalisée à ce niveau-ci n'a plus la moindre importance.
L'important, c'est d'abord la boucle de plus bas niveau. Après, il faut regarder les caches, etc.

**Bousk** · 02/03/2018, 15h35

Sinon std::for_each que je n'ai jamais vu utilisé nulle part d'ailleurs.

**Matthieu76** · 02/03/2018, 17h43

Envoyé par Bousk

Sinon std::for_each que je n'ai jamais vu utilisé nulle part d'ailleurs.

Bah maintenant en C++14 on a ça :

Code :

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

1
2
3
4
for (auto& i : v)
{
        i = 1;
}

Le std::for_each était bien avant mais maintenant c'est dépassé, on ne devrait plus l'utiliser, il n'apport rien en plus.

**Luc Hermitte** · 02/03/2018, 17h53

Envoyé par Matthieu76

Le std::for_each était bien avant mais maintenant c'est dépassé, on ne devrait plus l'utiliser, il n'apport rien en plus.

Si. Il apporte les politiques de parallélisation. Avec les for-range loops, on est limités à OpenMP et son standard.

**LittleWhite** · 02/03/2018, 20h59

Ah ! Donc ça revient à ce que je disais sur mon premier message, avec le std::fill.

**Kalith** · 08/03/2018, 23h21

J'utilise la version 2 autant que je peux, car elle évite d'avoir à écrire et exécuter v[i].

Ne pas avoir à l'écrire, ça évite de faire des erreurs sur les indices (aller au delà de la taille du vecteur, utiliser des indices négatifs, etc.).

Ne pas avoir à l'exécuter, dans la plupart des cas ça ne change rien, sauf si l'implémentation de std::vector (ou du conteneur que tu utilises) faits des tests pour s'assurer que l'indice i est valide. Si c'est le cas, alors la version 2 sera un poil plus rapide.

Si je ne peux pas utiliser la version 2, j'utilise une variante de la version 1:

Code :

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

1
2
3
4
for(unsigned int i : range(v))
{
        v[i] = 1;
}

range(v) est une fonction perso dans ma bibliothèque de traitement de données (cf. signature) qui retourne une structure toute bête avec des membres begin() et end() qui vont bien, de façon à faire exactement v.size() itérations. L'implémentation en C++11:

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <cmath>
#include <type_traits>
 
namespace range_impl {
    template<typename T>
    struct range_t;
 
    template<typename T>
    struct has_size_t {
        template <typename U> static std::true_type dummy(typename std::decay<
            decltype(std::declval<U&>().size())>::type*);
        template <typename U> static std::false_type dummy(...);
        using type = decltype(dummy<T>(0));
    };
 
    template<typename T>
    using has_size = typename has_size_t<T>::type;
 
    template<typename T, bool integral>
    struct dtype_impl;
 
    template <typename T>
    struct dtype_impl<T,true> {
        using type = typename std::make_signed<T>::type;
    };
 
    template <typename T>
    struct dtype_impl<T,false> {
        using type = T;
    };
 
    template<typename T>
    using dtype = typename dtype_impl<T, std::is_integral<T>::value>::type;
 
    template <typename T>
    dtype<T> make_step(dtype<T> e, dtype<T> b, dtype<T> n) {
        return (e-b)/n;
    }
 
    template<typename T>
    struct iterator_t;
 
    template<typename T>
    struct iterator_t<range_t<T>> {
        const range_t<T>& range;
        std::size_t i;
 
        iterator_t& operator++ (int) {
            ++i;
            return *this;
        }
 
        iterator_t operator++ () {
            return iterator_t{range, i++};
        }
 
        T operator * () const {
            return range.b + range.d*i;
        }
 
        bool operator == (const iterator_t& iter) const {
            return iter.i == i && &iter.range == &range;
        }
 
        bool operator != (const iterator_t& iter) const {
            return iter.i != i || &iter.range != &range;
        }
    };
 
    template<typename T>
    struct range_t {
        T b, e;
        dtype<T> d;
        std::size_t n;
 
        explicit range_t(T b_, T e_, std::size_t n_) : b(b_), e(e_),
            d(n_ == 0 ? 0 : make_step<T>(e_, b_, n_)), n(n_) {}
 
        using iterator = iterator_t<range_t>;
 
        iterator begin() const { return iterator{*this, 0}; }
        iterator end() const { return iterator{*this, n}; }
    };
}
 
// Define a range from start 'i', end 'e' (exclusive), and number of steps 'n'
template<typename T, typename U = T>
range_impl::range_t<T> range(T i, U e, std::size_t n) {
    return range_impl::range_t<T>(i, e, n);
}
 
// Define a range from start 'i', end 'e' (exclusive) in integer steps
template<typename T, typename U = T, typename enable = typename std::enable_if<std::is_integral<T>::value>::type>
range_impl::range_t<T> range(T i, U e) {
    return range(i, e, std::abs(range_impl::dtype<T>(e)-range_impl::dtype<T>(i)));
}
 
// Define a range from '0' to 'n' (exclusive) in integer steps
template<typename T, typename enable = typename std::enable_if<std::is_integral<T>::value>::type>
range_impl::range_t<T> range(T n) {
    return range(T(0), n);
}
 
// Define a range from '0' to 'n.size()' (exclusive) in integer steps
template<typename T, typename enable = typename std::enable_if<range_impl::has_size<T>::value>::type>
auto range(const T& n) -> range_impl::range_t<decltype(n.size())> {
    return range(n.size());
}

Comparé à la version 1 de base, ça évite les erreurs d'inattention, par exemple confondre deux variables différentes (for (int i = 0; j < v.size(); ++i), si j existe dans le code qui entoure la boucle), ou se tromper sur la condition de sortie (for (int i = 0; i <= v.size(); ++i), noter l'opérateur de comparaison). Et puis, je dois l'avouer, pour moi l'argument principal c'est qu'il y a bien moins de touches du clavier à marteler

Comment correctement parcourir un vector en C++14 et plus

Langage C++

Discussions similaires

Partager

Partager