Ça boucle
Publié le
En C++, il est une forme d'écriture qui, j'en m'en suis aperçu il y a quelque temps, m'irrite de plus en plus à la lecture. Elle m'irrite car c'est une forme face à laquelle je me retrouve souvent lors de longues séance de debug. Et pourtant, c'est une forme qui est probablement enseignée dans bon nombre de cours comme canonique et utilisée à longueur de code.
for(int i = 0; i < data.size(); ++i)
{
const Entry & entry = data[i];
if (entry.m_value == value)
{
return entry;
}
}
return DEFAULT_ENTRY;
Simple pourtant. Une bête boucle qui va chercher des éléments dans un tableau, compare une valeur à une autre et renvoie la valeur qui convient.
En fait, c'est ici une version dépouillée. Cette boucle se trouvera souvent au fond d'une fonction complexe, et le traitement sur les éléments sera beaucoup plus complexe.
Ce petit bout de code, simple, si souvent vu, est un nid à fautes. Fautes de frappes, d’inattention, de copier/coller,... Le schéma est tellement usé que le programmeur n'y fait plus très attention et que les erreurs pourtant évidentes passent même le contrôle de la peer review.
Les erreurs classiques sont :
- la variable d'index (ici le classique i) en cache une autre du même nom, et le code à l'intérieur de la boucle est censé utiliser la variable hors scope,
- la variable itérée (++i) n'est pas la bonne, erreur classique de copier/coller,
- la variable temporaire n'est pas prise en référence,
- l'index du tableau n'est pas prise dans la bonne variable
- ... j'en passe.
Ce sont tous des cas que je vois encore et toujours. Évidemment, si ce morceau de code était bien séparé dans sa propre fonction, beaucoup d'erreurs de portées de variables malencontreuses seraient évitées.
Reste que ce code se lit : pour chaque élément de mon conteneur, je fais telle action. L'important, ce qui différencie ce morceau de tous les autres morceaux similaires du programme, c'est bien entendu l'action à faire. Or près de la moitié des lignes servent à décrire la boucle sur les éléments. Et ce fonctionnement est strictement identique à celui de toutes les autres boucles sur les éléments du reste du programme.
Voyons un peu comment on pourrait écrire cela différemment, en utilisant pour base le programme C++ complet suivant.
#include <string>
#include <vector>
struct Entry
{
int m_value;
std::string m_name;
};
Entry DEFAULT_ENTRY;
void fill(std::vector<Entry> & data)
{
for(int i = 0; i < data.size(); ++i)
{
Entry & entry = data[i];
entry.m_value = i;
entry.m_name = "1234";
}
}
const Entry & find(const std::vector<Entry> & data, int value)
{
for(int i = 0; i < data.size(); ++i)
{
const Entry & entry = data[i];
if (entry.m_value == value)
{
return entry;
}
}
return DEFAULT_ENTRY;
}
int main(int argc, char const *argv[])
{
std::vector<Entry> allData;
allData.resize(argc + 1000);
fill(allData);
const int valueToSearch = argc + 500;
const Entry & entry = find(allData, valueToSearch);
return entry.m_value;
}
Note : les utilisations de argc sont là pour empêcher le compilateur d'effectuer des optimisations trop fortes. Ne pouvant pas connaître la valeur de argc lors de la compilation, le compilateur ne peut pas déployer la batterie d'optimisations qui nous sont utiles dans des cas réels. De même l'utilisation en valeur de retour de l'entrée trouvée.
Dans la suite de l'étude, la fonction main() ne changera pas, ni la structure Entry et son instance globale par défaut DEFAULT_ENTRY. Seules les fonctions fill() et find() seront modifiées.
Itérateurs
La première chose que nous allons faire est de transformer le code en utilisant des itérateurs. Il est toujours possible de prendre un itérateur sur un conteneur, mais il n'est pas toujours possible d'utiliser l'opérateur [] (du moins de manière efficace).
Les itérateurs nous amènent vers du code moins sensible au type du conteneur et évitera du refactor trop important.
void fill(std::vector<Entry> & data)
{
int count = 0;
for(std::vector<Entry>::iterator i = data.begin();
i < data.end(); ++i)
{
Entry & entry = *i;
entry.m_value = count++;
entry.m_name = "1234";
}
}
const Entry & find(const std::vector<Entry> & data, int value)
{
for(std::vector<Entry>::const_iterator i = data.begin();
i < data.end(); ++i)
{
const Entry & entry = *i;
if (entry.m_value == value)
{
return entry;
}
}
return DEFAULT_ENTRY;
}
Côté fill(), cela nous oblige à utiliser une variable supplémentaire count. Dans les deux cas, cela complexifie beaucoup la lecture du code. Ce n'est pas terrible. Arrangeons ça un peu avec un typedef.
typedef std::vector<Entry> Data;
void fill(Data & data)
{
int count = 0;
for(Data::iterator i = data.begin(); i < data.end(); ++i)
{
Entry & entry = *i;
entry.m_value = count++;
entry.m_name = "1234";
}
}
const Entry & find(const Data & data, int value)
{
for(Data::const_iterator i = data.begin(); i < data.end(); ++i)
{
const Entry & entry = *i;
if (entry.m_value == value)
{
return entry;
}
}
return DEFAULT_ENTRY;
}
Grâce au typedef, le code déclarant les itérateurs est plus léger. Au passage, le code devient aussi plus générique. Envie d'utiliser un deque ? À un #include <deque> près, il suffit de changer le typedef, le reste du code reste le même.
Il y a du mieux côté typage et généricité, mais l'implémentation de la boucle est toujours là.
On peut encore simplifier les choses en arrivant sur les terres du C++11 et en remplaçant les types d'itérateurs des boucles par auto. Ça évite comme cela de se poser la question du iterator vs. const_iterator. Le compilateur sait ce qu'il a à faire.
for(auto i = data.begin(); i < data.end(); ++i)
Note importante : tous ces remplacements se font à code généré égal ou similaire. Pour cela, compilez les différentes versions en optimisation maximum, puis allez jeter un œil au code assembleur généré.
Disparition des itérateurs
Si l'on revient sur le problème initial, nous avions surtout beaucoup de code écrit pour décrire la boucle plutôt que l'action. Les modifications faites dans le paragraphe précédent n'y changent rien. Le code est plus générique, c'est tout.
Le C++11 nous offre un outil que beaucoup d'autres langages ont eu avant lui : la boucle sur conteneur. Autrement dit, la boucle for(auto i = data.begin(); i < data.end(); ++i) est réduite à une seule instruction. Exactement ce que l'on cherche.
void fill(Data & data)
{
int count = 0;
for(auto &entry: data)
{
entry.m_value = count++;
entry.m_name = "1234";
}
}
const Entry & find(const Data & data, int value)
{
for(auto &entry: data)
{
if (entry.m_value == value)
{
return entry;
}
}
return DEFAULT_ENTRY;
}
Et voilà. Toute la machinerie de la boucle est générée automatiquement. Plus besoin d'itérer manuellement, plus besoin de déférencer un itérateur pour récupérer la valeur. L’œil peut se concentrer sur l'action faite par la boucle. Et c'est bien. Moins de code, moins d'erreurs, moins de fatigue, plus de concentration sur ce qui compte vraiment.
Ce qui est déjà fait...
... n'est pas à faire.
Et j'en vois qui ricanent en se disant que c'est bien beau tout ça, mais tout de même, lorsqu'on veut faire une recherche dans un container, la librairie standard offre déjà tout ce qu'il faut.
Et ils ont raison !
L'exemple, comme je le disais au début, était simplifié. Les erreurs viennent justement souvent d'une action plus complexe qu'une bête recherche par rapport à la valeur d'un membre. Cependant, puisque les boucles de recherches reprogrammées manuellement restent légions, continuons l'exercice.
La STL a les fonctions qu'il nous faut ; pour fill(), c'est std::generate() ; pour find(), c'est find_if().
Recherche
Commençons par find_if. La fonction prendre deux itérateurs pour définir l'espace de recherche, et un prédicat.
Le problème jusqu'à avant le C++11 est que si le prédicat doit capturer une variable, cela se traduit par l'utilisation d'un foncteur. Et un foncteur nous ramène au problème initial : beaucoup de code de machinerie, pour peu de code utile.
struct ValueFinder
{
int m_value;
ValueFinder(int value) : m_value(value) {}
bool operator() (const Entry & entry)
{
return entry.m_value == m_value;
}
};
const Entry & find(const Data & data, int value)
{
auto i = std::find_if(data.begin(), data.end(), ValueFinder(value));
if (i == data.end())
{
return DEFAULT_ENTRY;
}
return *i;
}
Nous revoilà aussi avec l'utilisation d'itérateurs. Il eut été intéressant d'avoir une version de la fonction prenant un conteneur et en déduisant le begin() and end()... ça s'ajoute.
Du coup, ce sont tous les programmeurs C# qui ont l'habitude d'utiliser LINQ qui se mettent à ricaner.
Heureusement, la STL du C++ nous permettait déjà depuis quelques temps grâce aux fonctions telles bind1st d'écrire un code plus simple. Le foncteur est alors généré sous le capot. Voici une version C++11 utilisant une fonction plutôt qu'un foncteur ainsi que la forme moderne de binding std::bind.
bool ValueFinder(const Entry & entry, int value)
{
return entry.m_value == value;
}
const Entry & find(const Data & data, int value)
{
using namespace std::placeholders;
auto i = std::find_if(data.begin(), data.end(),
std::bind(ValueFinder, _1, value));
if (i == data.end())
{
return DEFAULT_ENTRY;
}
return *i;
}
Côté prédicat, c'est nettement plus simple, et donc nettement plus lisible. Du côté appel par contre, c'est un peu moins bon, avec en plus un encombrant using namespace nécessaire pour que la syntaxe des placeholders de std::bind soit lisible (_1, _2, ...).
Lambda
Grâce aux fonctions anonymes, autrement appelées lambdas, on arrive en C++11 à quelque chose d'assez concis. La syntaxe peut surprendre car elle est nouvelle par rapport à l'âge du langage, mais on s'y fait assez vite.
const Entry & find(const Data & data, int value)
{
auto i = std::find_if(data.begin(), data.end(),
[value](const Entry & e) { return e.m_value == value; });
if (i == data.end())
{
return DEFAULT_ENTRY;
}
return *i;
}
La lambda ([value](const Entry & e) { return e.m_value == value; }) se lit ainsi :
- entre crochets, on signale que l'on capture
value; c'est-à-dire que cette variable (capturée par valeur) sera disponible pour le corps de la fonction. - entre parenthèses, les paramètres d'une fonction de manière tout à fait ordinaire.
- puis le corps de la fonction. Ici la variable à droite de l'égalité aura la valeur de
valueau moment de l'évaluation de la fonction (et non de l'exécution de la fonction évaluée).
Pour un petit prédicat, comme l'exemple ici, utiliser une lambda est évident. Pour un traitement plus complexe, un foncteur peut être intéressant.
Génération
Côté génération, la STL offre aussi ce qu'il faut. On a vu les principes, on va donc aller plus vite.
Version foncteur :
struct EntryGenerator
{
int m_count;
EntryGenerator() : m_count(0) {}
Entry operator () ()
{
return Entry{m_count++, "1234"};
}
};
void fill(Data & data)
{
std::generate(data.begin(), data.end(), EntryGenerator());
}
Version lambda (avec initialiseur d'objet) :
void fill(Data & data)
{
int count = 0;
std::generate(data.begin(), data.end(),
[&count]() { return Entry{count++, "1234"}; } );
}
Cette lambda est un peu différente :
- la valeur capturée l'est par référence. Les modifications faites à cette variable dans le corps de la fonction seront donc visible sur la variable
countdéclarée dans la fonctionfill(): c'est la même variable. - il n'y a pas de paramètres à la fonction.
- le corps de la fonction modifie la variable prise par référence.
Conclusion
Le C++11 offre la possibilité d'écrire des choses beaucoup plus concises qu'auparavant. La STL permet de se passer de l'écriture récurrente des mêmes motifs de programmation.
Écrire de manière plus concise, c'est s'éviter des bugs dus à une complexité inutile. Cela permet d'avoir sous les yeux le nécessaire à la compréhension, en s'évitant la lecture de la machinerie nécessaire. 1
Utiliser des fonctions déjà écrites, c'est s'éviter de les réécrire en introduisant une erreur bête et de signaler clairement ce qui est fait.
Alors, si vous avez la possibilité de travailler dans un environnement à jour de la norme C++11, n'hésitez-pas à utiliser une syntaxe et une bibliothèque moderne !
-
Attention à ne pas confondre la concision et la cryptographie ! ↩