C++11 std:: fonction de comparaison lambda

je veux créer un std::set avec une fonction de comparaison personnalisée. Je pourrais le Définir comme une classe avec operator() , mais je voulais profiter de la possibilité de définir un lambda où il est utilisé, donc 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 un membre. Mais je n'arrive pas à trouver le genre de lambda. Avant de poursuivre, voici un exemple:

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

j'ai trouvé deux solutions après recherche: un, en utilisant std::function . Il suffit d'avoir le type de fonction de comparaison de jeu std::function<bool (int, int)> et passer la lambda exactement comme je l'ai fait. La deuxième solution est d'écrire une fonction make_set, comme std::make_pair .

SOLUTION 1:

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

SOLUTION 2:

template <class Key, class Compare>
std::set<Key, Compare> make_set (Compare compare)
{
     return std::set<Key, Compare> (compare);
}

la question Est, ai-je une bonne raison de préférer une solution à l'autre? Je préfère la première parce qu'elle utilise des fonctionnalités standard (make_set n'est pas une fonction standard), mais je me demande si l'utilisation de std::function ralentit (potentiellement) le code? Je veux dire, est-ce que cela réduit la chance que le compilateur inlines la fonction de comparaison, ou il devrait être assez intelligent pour se comporter exactement comme il serait un type de fonction lambda et non std::function (je sais, dans ce cas, il ne peut pas être un type lambda, mais vous savez, je demande en général) ?

(J'utilise GCC, mais j'aimerais savoir ce que font les compilateurs populaires dans general)

RÉSUMÉ, APRÈS QUE J'AI EU BEAUCOUP DE GRANDES RÉPONSES:

Si la vitesse est critique, la meilleure solution est d'utiliser une classe avec operator() aka foncteur. Il est plus facile pour le compilateur d'optimiser et d'éviter toutes les indirectes.

pour un entretien facile et une meilleure solution polyvalente, utilisez les fonctionnalités C++11, utilisez std::function . C'est toujours rapide (juste un peu plus lent que le foncteur, mais il peut être négligeable) et vous pouvez utiliser la fonction std::function , lambda, tout objet 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++11).

il y a une option pour définir la fonction lambda ailleurs, mais alors vous ne gagnez rien de la fonction de comparaison étant une expression lambda, puisque vous pourriez aussi bien en faire une classe avec operator() et le l'emplacement de la définition ne serait pas la construction établie de toute façon.

il y a d'autres idées, comme l'utilisation de la délégation. Si vous voulez une explication plus complète de toutes les solutions, lisez les réponses:)

67
demandé sur Null 2013-02-15 17:40:36

6 réponses

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

Fragile, car avant que le compilateur puisse prouver à lui-même que tous les appels à ce std::function sont effectivement des appels à votre lambda, il doit prouver qu'aucun l'accès à votre std::set définit toujours le std::function pour tout sauf votre lambda. Ce qui signifie qu'il doit traquer 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 pourrait être possible, dans certains cas, mais relativement inoffensif changements pourraient casser même si votre compilateur réussi à le prouver.

d'un autre côté, un fonctionnaire avec un apatride operator() a un comportement facile à prouver, et les optimisations qui impliquent ce sont des choses quotidiennes.

donc oui, dans la pratique, je pense que std::function pourrait être plus lent. D'un autre côté, la solution std::function est plus facile à maintenir que la solution make_set , et l'échange de temps de programmeur pour la performance de programme est assez fongible.

make_set a le grave inconvénient que l'un de ces set type de "doit être déduite de l'appel à make_set . Souvent un set stocke l'état persistant, et pas quelque chose que vous créez sur la pile puis laissez tomber hors de portée.

si vous avez créé une lambda statique ou globale apatride auto MyComp = [](A const&, A const&)->bool { ... } , vous pouvez utiliser la syntaxe std::set<A, decltype(MyComp)> pour créer une set qui peut persister, mais est facile pour le compilateur d'optimiser (parce que toutes les instances de decltype(MyComp) sont des foncteurs apatrides) et en ligne. Je le souligne, parce que vous collez le set dans un struct . (Ou est-ce que votre compilateur soutien

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

que je trouverais surprenant!)

enfin, si vous êtes inquiet au sujet de la performance, considérez que std::unordered_set est beaucoup plus rapide (au prix d'être incapable d'itérer au-dessus du contenu dans l'ordre, et d'avoir à écrire/trouver un bon hachage), et qu'un std::vector trié est mieux si vous avez un 2-phase "tout Insérer" puis "interroger le contenu à plusieurs reprises". Il suffit de le farcir dans le vector d'abord, puis sort unique erase , puis utilisez l'algorithme libre equal_range .

22
répondu Yakk - Adam Nevraumont 2013-02-15 15:21:23

il est peu probable que le compilateur soit capable d'inline un appel de fonction std::, alors que n'importe quel compilateur qui supporte lambdas serait presque certainement inline la version functor, y compris si ce functor est un lambda Non caché par un std::function .

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

#include <set>
#include <iostream>
#include <iterator>
#include <algorithm>

int main()
{
   auto comp = [](int x, int y){ return x < y; };
   auto set  = std::set<int,decltype(comp)>( comp );

   set.insert(1);
   set.insert(10);
   set.insert(1); // Dupe!
   set.insert(2);

   std::copy( set.begin(), set.end(), std::ostream_iterator<int>(std::cout, "\n") );
}

qui imprime:

1
2
10

Voir courir sur Coliru .

21
répondu metal 2018-09-27 04:56:43

un lambda apatride (c'est-à-dire sans capture) peut se décomposer en pointeur de fonction, donc votre type pourrait être:

std::set<int, bool (*)(int, int)> numbers;

sinon j'opterais pour la solution make_set . Si vous n'utilisez pas une fonction de création d'une ligne parce qu'elle n'est pas standard, vous n'obtiendrez pas beaucoup de code écrit!

5
répondu Jonathan Wakely 2013-02-15 14:04:04

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

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

Comme le std::function est généralement un peu trop lourd. Je ne peux pas commenter vos circonstances particulières, car je ne les connais pas.

1
répondu user1095108 2017-04-13 12:40:33

si vous êtes déterminé à avoir le set comme membre de classe, initialisant son comparateur au moment du constructeur, alors au moins un niveau d'indirectement est inévitable. Considérez que pour autant que le compilateur sache, vous pouvez ajouter 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 objet de type Foo , le type du set ne porte pas d'information sur le constructeur qui a initialisé son comparateur, donc pour appeler le lambda correct nécessite une action indirecte sur la lambda sélectionnée operator() .

puisque vous utilisez des lambdas sans captuless, vous pouvez utiliser le type de pointeur de fonction bool (*)(int, int) comme votre type de comparateur, car les lambdas sans captuless ont la fonction de conversion appropriée. Cela impliquerait naturellement une action indirecte par le biais du pointeur de fonction.

1
répondu ecatmur 2013-02-15 14:15:59

la différence dépend fortement des optimisations de votre compilateur. S'il optimise lambda dans un std::function ceux-ci sont équivalents, sinon vous introduisez une indirecte dans le premier que vous n'aurez pas dans le dernier.

0
répondu filmor 2013-02-15 13:43:08