J’utilise beaucoup en ce moment les conteneurs de la STL et j’ai eu deux petites surprises sur les std::list et les std::set, vous allez voir elle sont encore mieux que celles des Kinder Surprise.

Dans mon code je devais faire le transfert d’éléments d’une liste dans une autre, ce qui donnait quelque chose de ce genre :

list<int> l1;
for(int i=0; i < 10e5; ++i)
   l1.push_back(i);

list<int> l2;
for(int i=0; i < 10e5; ++i)
   l2.push_back(i);

//algo de malade

//copie des éléments de l2 dans l1
for (list<int>::iterator it = l2.begin(); it != l2.end(); ++it)
   l1.push_front(*it);

Si je remplaçais ce code d’une complexité en O(n) par celui utilisant la fonction splice qui elle est en O(1), j’avais tout de même un temps d’exécution plus long ! (note : dans mon cas il était plus long, je ne sais pas si dans cet exemple précis il l’ait, d’ailleurs le code mis n’est là que pour se mettre dans le contexte, je m’amuse rarement à compter deux fois jusqu’à l’infini 😉

l1.splice(l1.begin(), l2);

Quand on sait que splice doit relier la chaine de l2 au début de l1, soit seulement faire quelques modifications de pointeurs, il y a de quoi se poser des questions. En cherchant un peu, j’ai pu constater que la version Debug de Visual Studio s’amuser à avoir un algorithme en o(n) pour effectuer des choses et d’autres dans le but d’aider le debuggage. Bref, lorsqu’on compare la rapidité de deux code il ne faut pas trop faire confiance à ce que disent les chiffres, bien comprendre ce qu’il se passe derrière et, éviter de trop tester la rapidité d’un code par rapport à un autre en mode Debug.

Passons au conteneur set de la STL et sur sa façon de d’éliminer les doublons. J’avais besoin d’une liste d’éléments uniques, je décide donc d’utiliser un set qui fera tout seul le bouleau pour éliminer ceux qui sont égaux. Pour lui permettre d’effectuer sa tâche, on doit lui donner en paramètre une fonction ou un foncteur de comparaison stricte. Par défaut c’est le foncteur less qui est utilisé, qui lui même utilise l’opérateur « < ». Pour ne pas m’embêter j’ai surchargé l’opérateur « < » pour des objets de ma classe mais de façon laxiste : deux objets différents pouvaient donner ceci :

a < b est faux
b < a donne aussi faux
a == b vrai ou faux ?

On a donc deux objets qui semblent égaux mais qui pourtant ne le sont pas, du moins pas de la façon dont je voyais la chose. Effectivement set ne se fie qu’à l’opération de comparaison fourni pour savoir si deux éléments sont égaux,  si bien qu’il m’en éliminait certain non égaux (au sens de l’opérateur « == » ) concidérant qu’ils étaient déjà prèsent. J’ai donc dû recoder un opérateur « < » respectant la régle : « si a < b et b < a alors a et b sont égaux ».

Publicités