C ++ 11 std :: set lambda fonction de comparaison

Je veux créer un ensemble std::set avec une fonction de comparaison personnalisée. Je pourrais le définir comme une classe avec operator() , mais je voulais avoir la possibilité de définir un lambda où il est utilisé, alors j’ai décidé de définir la fonction lambda dans la liste d’initialisation du constructeur de la classe qui a le std::set comme membre. Mais je ne peux pas obtenir le type de lambda. Avant de continuer, voici un exemple:

 class Foo { private: std::set numbers; public: Foo () : numbers ([](int x, int y) { return x < y; }) { } }; 

Après la recherche, j’ai trouvé deux solutions: l’une utilisant std::function . Juste avoir le type de fonction de comparaison d’ensemble std::function et passer le lambda exactement comme je l’ai fait. La seconde solution consiste à écrire une fonction make_set, comme std::make_pair .

SOLUTION 1:

 class Foo { private: std::set<int, std::function numbers; public: Foo () : numbers ([](int x, int y) { return x < y; }) { } }; 

SOLUTION 2:

 template  std::set make_set (Compare compare) { return std::set (compare); } 

La question est la suivante: ai-je une bonne raison de préférer une solution à une autre? Je préfère le premier parce qu’il utilise des fonctionnalités standard (make_set n’est pas une fonction standard), mais je me demande: l’utilisation de std::function rend-elle le code (potentiellement) plus lent? Je veux dire, est-ce que cela réduit les chances que le compilateur mette en ligne la fonction de comparaison, ou qu’il soit assez intelligent pour se comporter exactement comme s’il s’agissait d’un type de fonction lambda et non de std::function (je sais que ne soit pas un type lambda, mais vous savez, je demande en général)?

(J’utilise GCC, mais j’aimerais savoir ce que font généralement les compilateurs populaires)

RÉSUMÉ, APRÈS AVOIR BEAUCOUP DE BELLES RÉPONSES:

Si la vitesse est critique, la meilleure solution consiste à utiliser une classe avec operator() aka functor. Le plus simple pour le compilateur est d’optimiser et d’éviter les indirections.

Pour une maintenance facile et une meilleure solution polyvalente, en utilisant les fonctionnalités C ++ 11, utilisez std::function . Il est toujours rapide (juste un peu plus lent que le foncteur, mais il peut être négligeable) et vous pouvez utiliser n’importe quelle fonction – std::function , lambda, tout object appelable.

Il y a aussi une option pour utiliser un pointeur de fonction, mais s’il n’y a pas de problème de vitesse, je pense que std::function est mieux (si vous utilisez C ++ 11).

Il y a une option pour définir la fonction lambda ailleurs, mais vous n’obtenez rien de la fonction de comparaison étant une expression lambda, puisque vous pourriez aussi bien en faire une classe avec operator() et l’emplacement de la définition ne serait pas la construction de l’ensemble en tous cas.

Il y a plus d’idées, comme utiliser la délégation. Si vous voulez une explication plus approfondie de toutes les solutions, lisez les réponses 🙂

Oui, une std::function introduit une indirection presque inévitable à votre set . Alors que le compilateur peut toujours, en théorie, comprendre que toute utilisation de la std::function de votre set implique de l’appeler sur un lambda qui est toujours exactement le même lambda, c’est à la fois dur et extrêmement fragile.

Fragile, car avant que le compilateur puisse se prouver que tous les appels à cette std::function sont réellement des appels à votre lambda, il doit prouver qu’aucun access à votre std::set ne met jamais la std::function à votre lambda . Ce qui signifie qu’il doit rechercher toutes les routes possibles pour atteindre votre std::set dans toutes les unités de compilation et prouver qu’aucune d’entre elles ne le fait.

Cela peut être possible dans certains cas, mais des modifications relativement anodines peuvent le casser même si votre compilateur a réussi à le prouver.

D’autre part, un foncteur avec un operator() sans état operator() a un comportement facile à prouver et des optimisations impliquant ce sont des choses quotidiennes.

Donc oui, dans la pratique je soupçonne que std::function pourrait être plus lent. Par contre, la solution std::function est plus facile à maintenir que la make_set , et l’échange de temps de programmation pour les performances du programme est assez fongible.

make_set a le grave inconvénient qu’un tel type doit être déduit de l’appel à make_set . Souvent, un set stocke un état persistant, et non quelque chose que vous créez sur la stack, puis laissez tomber hors de la scope.

Si vous avez créé un auto MyComp = [](A const&, A const&)->bool { ... } statique lambda statique ou global auto MyComp = [](A const&, A const&)->bool { ... } , vous pouvez utiliser la syntaxe std::set pour créer un std::set set qui peut persister, mais est facile à optimiser pour le compilateur (car toutes les instances de decltype(MyComp) sont des foncteurs sans état) et en ligne. Je le souligne, car vous collez l’ set dans une struct . (Ou votre compilateur prend-il en charge

 struct Foo { auto mySet = make_set([](int l, int r){ return l 

ce qui me surprendrait!)

Enfin, si vous êtes inquiet au sujet des performances, considérez que std::unordered_set est beaucoup plus rapide (au prix de ne pas pouvoir itérer le contenu dans l’ordre, et de devoir écrire / trouver un bon hachage), et un std::vector sortingé std::vector est préférable si vous avez un "tout insérer" puis "un contenu de requête répété" en deux phases. Insérez-le simplement dans le vector , puis sort erase unique , puis utilisez l’algorithme libre equal_range .

Il n’est pas improbable que le compilateur ne puisse pas incorporer un appel std :: function, alors que tout compilateur supportant lambdas inclurait presque certainement la version du foncteur, y compris si ce foncteur est un lambda non caché par une std::function .

Vous pouvez utiliser decltype pour obtenir le type de comparateur de lambda:

 #include  #include  #include  #include  int main() { auto comp = [](int x, int y){ return x < y; }; auto set = std::set( comp ); set.insert(1); set.insert(10); set.insert(1); // Dupe! set.insert(2); std::copy( set.begin(), set.end(), std::ostream_iterator(std::cout, "\n") ); } 

Quelles impressions:

 1 2 10 

Voyez-le courir sur Coliru .

Un lambda sans état (c.-à-d. Un sans capture) peut se transformer en un pointeur de fonction, votre type pourrait donc être:

 std::set numbers; 

Sinon, j’irais pour la solution make_set . Si vous n’utilisez pas une fonction de création d’une ligne car elle n’est pas standard, vous n’allez pas écrire beaucoup de code!

D’après mon expérience avec le profileur, le meilleur compromis entre performance et beauté consiste à utiliser une implémentation de délégué personnalisée, telle que:

https://codereview.stackexchange.com/questions/14730/impossibly-fast-delegate-in-c11

Comme la std::function est généralement un peu trop lourde. Je ne peux pas commenter vos circonstances spécifiques, cependant, je ne les connais pas.

Si vous êtes déterminé à avoir l’ set tant que membre de la classe, l’initialisation de son comparateur à l’heure du constructeur, alors au moins un niveau d’indirection est inévitable. Considérez que pour autant que le compilateur le sache, vous pouvez append un autre constructeur:

  Foo () : numbers ([](int x, int y) { return x < y; }) { } Foo (char) : numbers ([](int x, int y) { return x > y; }) { } 

Une fois que vous avez un object de type Foo , le type de l’ set ne porte pas d’informations sur le constructeur initialisé de son comparateur, donc appeler le bon lambda nécessite une indirection vers l’ operator() lambda sélectionné operator() .

Comme vous utilisez des lambdas sans codeur, vous pouvez utiliser le type de pointeur de fonction bool (*)(int, int) comme type de comparateur, car les lambdas sans codeur ont la fonction de conversion appropriée. Cela impliquerait bien sûr une indirection via le pointeur de la fonction.

La différence dépend fortement des optimisations de votre compilateur. Si elle optimise lambda dans une std::function celles-ci sont équivalentes, sinon vous indiquez une indirection dans la première que vous n’auriez pas dans la seconde.