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:)
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
.
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
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!
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.
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.
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.