Bonsoir.

J'ai quelques questions qui va sans doute vous sembler assez bête. 

Je reprends mon apprentissage du c++. Ci-dessous la fonction std::sort avec utilisation d'une fonction lambda (dans le but de trier un vector du plus grand au plus petit). (source du cours : http://guillaume.belz.free.fr/doku.php?id=predicats - très bon cours au passage).

std::sort(begin(v), end(v), [](auto lhs, auto rhs){ return lhs < rhs; });

La documentation de la fonction sort, nous dit (source : https://www.cplusplus.com/reference/algorithm/sort/) : 

Binary function that accepts two elements in the range as arguments, and returns a value convertible to bool. The value returned indicates whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines.

Mes questions (incompréhensions) sont : 

1. Comment la fonction lambda fait le lien avec les valeurs (ici de v et/ou de l'itérateur créé par begin(v). En outre, comment lhs et rhs vont recevoir les valeurs de v à comparer.)

2. Je pensais que pour que la fonction lambda soit exécutée, il fallait des parenthèses après le corps de la fonction lambda afin de spécifier les paramètres  (où non paramètres s'il n'y en a pas). Comment se fait-il que cette fonction lambda s'éxécute ?

3. D'où vient cette notation begin(v) ? J'ai pour habitude d'utiliser v.begin().  -> OK stl propose un begin(), question bête réponse bête (std::begin).

Je suis un peu rouillé, désolé.

Merci pour vos réponses :) 

-
Edité par Didy7 8 juin 2021 à 18:00:02

Hello,
oublions une seconde la lambda et écrivons l'appel avec une fonction classique :

std::sort(begin(v), end(v), comparison_function);

L'algorithme de tri va appeler un certain nombre de fois la fonction comparison_function sur deux des éléments du vecteur (disons x1 et x2) pour savoir lequel des deux est le plus petit : comparison_function(x1, x2)
Sur quels x1 et x2 ? Ca dépend du type d'algo et de l'implémentation.
Par exemple, pour un vecteur qui contient {2, 1, 4}, il est possible que l'algo appelle comparison_function(2, 1), comparison_function(2, 4) et comparison_function(1, 4).

Les paramètres de la lambda sont donnés entre parenthèses, après les crochets : auto lhs, auto rhs
Ce sont les x1 et x2 de mon exemple.

Tes questions sont très pertinentes. Je vais répondre dans l'ordre inverse. Parce que.

Didy7 a écrit:

3. D'où vient cette notation begin(v) ? J'ai pour habitude d'utiliser v.begin().  -> OK stl propose un begin(), question bête réponse bête (std::begin).

Les 2 syntaxes sont valides, c'est pas dramatique si tu utilises v.begin(). J'utilise préférentiellement begin(v) parce que cette syntaxe est plus générique et donc augmente la maintenabilité du code (ie si tu changes ton code, il y a plus de chance que cette syntaxe reste valide).

Pour être concret, imagine que tu écris ce code :

std::vector<type> v;
std::sort(v.begin(), b.end(), foo);

Ce code est parfaitement valide, pas de problème.

Plus tard, pour des raisons diverses, tu décides de changer std::vector par un tableau C :

type v[N];

Et paf, chocapic ! Un tableau C ne possède pas de fonction begin() et ton code n'est plus valide. Il faut le corriger.

Sur un code aussi simple, ca ne posera pas de problème, mais dans un vrai code ? Ou dans un code template qui est utilisé avec pleins de conteneurs différents ?

Le code avec begin(v) et end(v) restera valide avec d'autres conteneurs.

Et en fait, ce code va fonctionner pour n'importe quel type (même potentiellement autre chose que des conteneurs). Il suffit d'ajouter ces fonctions libre begin() et end().

Didy7 a écrit:

2. Je pensais que pour que la fonction lambda soit exécutée, il fallait des parenthèses après le corps de la fonction lambda afin de spécifier les paramètres  (où non paramètres s'il n'y en a pas). Comment se fait-il que cette fonction lambda s'éxécute ?

Et tu as parfaitement raison pour les parenthèses. Il faut donc en conclure... que cette lambda n'est pas exécutée ! Tout au moins, pas où tu penses.

Je ne vais pas entrer dans les détails syntaxiques (de mémoire, tu verras ça plus loin dans le cours), donc je vais utiliser du pseudo code.

L'idée générale est que l'on souhaite passer une fonction en paramètre d'une fonction, dans le but de l'utiliser dans le corps de cette fonction. En code, cela donne :

void une_fonction(FONCTION f) {             // (1)
    std::cout << f();                       // (2)
}

int une_autre_fonction() { return 123; }

une_fonction(une_autre_fonction);           // (3)

Dans ce pseudo-code, la fonction "une_fonction" prend un paramètre une fonction f (ligne 1) et utilise cette fonction dans son corps (ligne 2). Il faut bien distinguer le passage de la fonction "un_autre_fonction" comme argument de "une_fonction" (lignes 1 et 3) et l'appel de la fonction "une_autre_fonction", qui est exécutée ligne 2 (tu peux voir les parenthèses lors de l'appel).

S'il y avait les parenthèse à la ligne 3, cela signifie que "une_autre_fonction()" serait remplacé par un int et "une_fonction" ne prendrait pas une fonction comme paramètre, mais un int :

void une_fonction(int i) {                // (1)
    std::cout << i;                       // (2)
}

int une_autre_fonction() { return 123; }

une_fonction(une_autre_fonction());       // (3)

Dans le code avec std::sort, c'est la même chose. La fonction lambda n'a pas de parenthèse parce qu'elle n'est pas exécutée lors de l'appel, mais passé en paramètre de la fonction std::sort. Et c'est la fonction std::sort qui va appeler, en interne, cette lambda. (Plusieurs fois, pour chaque comparaison).

Didy7 a écrit:

1. Comment la fonction lambda fait le lien avec les valeurs (ici de v et/ou de l'itérateur créé par begin(v). En outre, comment lhs et rhs vont recevoir les valeurs de v à comparer.)

Et donc, si tu as compris que c'est std::sort qui utilise en interne la fonction lambda appelé en paramètre, tu as peut être trouvé la réponse à cette question : c'est la fonction std::sort, lorsqu'elle utilise en interne la fonction lambda, qui va faire en sorte d'appeler cette fonction en lui passant correctement les arguments.

En termes de code, cela ressemble a un truc du genre :

std::sort(begin, end, lambda) {
    ... plein de choses
    ...
    lambda(arg1, arg2);
    ...
    ...
}

J'espère que ca t'aide a comprendre.

Merci à vous deux.

gbdivers a écrit:

J'espère que ca t'aide a comprendre.

Parfaitement, tes explications sont limpides et débloquent beaucoup de chose. Merci infiniment.

Je crois (des plus compétents que moi pourront confirmer ou me corriger) qu'en interne c'est un algorithme "introsort". (à moins que cela ne dépende du compilateur ???)

https://fr.wikipedia.org/wiki/Introsort

une animation rigolote qui illustre un peu ce qui se passe :

https://www.youtube.com/watch?v=67ta5WTjjUo 

Ca n'est pas spécifié par la norme C++. La norme ne spécifie jamais l'implémentation, seulement les interfaces (et dans certains cas, la complexité algo, en général pour imposer une complexité en O(1)). Donc ca dépend de la bibliothèque standard.

gbdivers a écrit:

Ca n'est pas spécifié par la norme C++. La norme ne spécifie jamais l'implémentation, seulement les interfaces (et dans certains cas, la complexité algo, en général pour imposer une complexité en O(1)). Donc ca dépend de la bibliothèque standard.

Ok ! J'avais lu ça par-ci par-là... Comme quoi il faut toujours se méfier   

Sinon attention, ça n'existe pas les algos de tri en O(1), ce serait trop beau  c'est minimum O(n log n) pour le cas moyen.

-
Edité par Umbre37 8 juin 2021 à 23:27:56

Pour GCC, j'ai l'impression que tu as raison et que c'est bien introsort. Pour LLVM, je ne sais pas. Idem pour les autres libs standard.

Il ne faut pas oublier que les algos et classes de la lib standard, c'est générique : assez bon pour être utilisé le plus souvent possible. Mais dès que l'on a des contraintes spécifiques (par exemple la performances), on est parfois obligé (après profiling !!!) d'utiliser des implémentations d'algo dans une autre lib, justement pour être sur d'utiliser un algo spécifique.

Umbre37 a écrit:

Sinon attention, ça n'existe pas les algos de tri en O(1), ce serait trop beau  c'est minimum O(n log n)

Je ne parlais pas des algos en general, mais de certaines fonctions. Par exemple, `std::list::size()` doit être en O(1), d'après la norme. Cela veut dire qu'une bibliothèque standard qui implémente cette classe ne peut pas compter le nombre d'éléments dans cette fonction (puisque cela donnerait une fonction en O(n)).

Donc sans imposer une implémentation particulière, la norme peut spécifier des contraintes qui vont influencer très fortement l'implémentation.

-
Edité par gbdivers 8 juin 2021 à 23:31:34

gbdivers a écrit:

Je ne parlais pas des algos en general, mais de certaines fonctions. Par exemple, `std::list::size()` doit être en O(1), d'après la norme. Cela veut dire qu'une bibliothèque standard qui implémente cette classe ne peut pas compter le nombre d'éléments dans cette fonction (puisque cela donnerait une fonction en O(n)).

Donc sans imposer une implémentation particulière, la norme peut spécifier des contraintes qui vont influencer très fortement l'implémentation.

-
Edité par gbdivers il y a 2 minutes

Ha oui évidement. Désolé on ne s'était pas compris.

C'est mieux qu'il y ait un maximum de garanties de perf sur les algos de la STL. Quand on développe on peut avoir une idée du coût de ce qu'on fait... Après, le détail de l'implémentation c'est juste une curiosité plus qu'autre chose. À mon niveau je m'en fiche un peu... En tout cas je sûr de ne pas faire mieux que gcc ! 

Mais c'est vrai que j'aimais bien les exercices de tri. Je trouvais ça sympa à comprendre et à implémenter. D'ailleurs j'ai l'impression que c'est un peu passé de mode, je n'en ai jamais croisé sur le forum ou sur le site. (mais je ne lis pas tout...)

-
Edité par Umbre37 8 juin 2021 à 23:52:46

Les algos de tri et de recherche font parti des algos les plus étudiés et les mieux connus. Ca fait parti des bases de l'apprentissage de l'algo et il y a encore de la recherche dessus.

Mais c'est vrai qu'en termes de discussion sur le forum, on a vite fait le tour. Dans la grand majorité des cas, ce n'est pas quelque chose de critique.