argument de fonction modélisé en C++14

Question

Ce code ne compile pas, même sous C++14, à cause de problèmes de déduction de type de template. Quelle est la solution de contournement la moins inélégante ?

#include <vector>
#include <functional>
#include <iostream>

template <class T>
std::vector<T> merge_sorted(
    const std::vector<T>& a, const std::vector<T>& b,
    std::function<bool(const T, const T)> a_before_b)
{
    std::vector<T> ret;
    auto ia=a.begin();
    auto ib=b.begin();
    for (;;ia!=a.end() || ib!=b.end())
        ret.push_back( a_before_b(*ia,*ib) ? *(ia++) : *(ib++) );
    return ret;
}

int main()
{
    std::vector<double> A { 1.1, 1.3, 1.8 };
    std::vector<double> B { 2.1, 2.2, 2.4, 2.7 };
    auto f = [](const double a, const double b) -> bool {
        return (a-(long)(a))<=(b-(long(b))); };
    std::vector<double> C = merge_sorted(A, B, f);
    for (double c: C)
        std::cout << c << std::endl;
    // expected outout: 1.1 2.1 2.2 1.3 2.4 2.7 1.8
}

Voici le message d'erreur de g++ -std=c++14 main.cpp :

main.cpp: In function ‘int main()’:
main.cpp:23:49: error: no matching function for call to ‘merge_sorted(std::vector<double>&, std::vector<double>&, main()::<lambda(double, double)>&)’
     std::vector<double> C = merge_sorted(A, B, f);
                                                 ^
main.cpp:6:16: note: candidate: template<class T> std::vector<T> merge_sorted(const std::vector<T>&, const std::vector<T>&, std::function<bool(T, T)>)
 std::vector<T> merge_sorted(
                ^~~~~~~~~~~~
main.cpp:6:16: note:   template argument deduction/substitution failed:
main.cpp:23:49: note:   ‘main()::<lambda(double, double)>’ is not derived from ‘std::function<bool(T, T)>’
     std::vector<double> C = merge_sorted(A, B, f);

\==

Modification ultérieure, juste pour mémoire : Voici une version du code qui compile (grâce aux réponses reçues) et qui s'exécute correctement (plusieurs corrections du code non testé ci-dessus) :

#include <vector>
#include <functional>
#include <iostream>

template <class T, class Pred>
std::vector<T> merge_sorted(const std::vector<T>& a, const std::vector<T>& b, Pred a_before_b)
{
    std::vector<T> ret;
    auto ia=a.begin();
    auto ib=b.begin();
    for (;ia!=a.end() && ib!=b.end();)
        ret.push_back( a_before_b(*ia,*ib) ? *(ia++) : *(ib++) );
    for (;ia!=a.end();)
        ret.push_back( *(ia++) );
    for (;ib!=b.end();)
        ret.push_back( *(ib++) );
    return ret;
}

int main()
{
    std::vector<double> A { 1.1, 1.3, 1.8 };
    std::vector<double> B { 2.1, 2.2, 2.4, 2.7 };
    auto f = [](const double a, const double b) -> bool {
        return (a-(long)(a))<=(b-(long(b))); };
    std::vector<double> C = merge_sorted(A, B, f);
    for (double c: C)
        std::cout << c << std::endl;
    // expected outout: 1.1 2.1 2.2 1.3 2.4 2.7 1.8
}

Answer 1

Vous devez faire le type de a_brefore_b un contexte non cultivé en quelque sorte. Pour cela, j'introduis généralement un assistant portant un nom approprié :

template <class T>
struct NonDeduced
{
  using type = T;
};

template <class T>
std::vector<T> merge_sorted(
    const std::vector<T>& a, const std::vector<T>& b,
    typename NonDeduced<std::function<bool(const T, const T)>>>::type a_before_b)

Bien sûr (comme @Marc Glisse l'a fait remarquer dans les commentaires), il est tout à fait inutile de forcer l'utilisation de std::function pour le type de a_before_b en premier lieu. Sans parler du fait qu'il peut facilement s'accompagner d'une pénalité de performance ( std::function utilise l'effacement des types et la répartition dynamique en interne). Il suffit de suivre ce que fait la bibliothèque standard et de typer le prédicat par un paramètre de modèle :

template <class T, class Pred>
std::vector<T> merge_sorted(
    const std::vector<T>& a, const std::vector<T>& b,
    Pred a_before_b)

Answer 2

Le problème ici est que f n'est pas un std::function . Il s'agit d'un type de classe sans nom mais ce n'est pas une std::function . Lorsque le compilateur effectue la déduction des arguments de template, il n'effectue aucune conversion, il travaille avec les paramètres tels quels pour en déduire leur type. Cela signifie que lorsqu'il s'attend à voir un std::function<bool(const T, const T)> il voit main()::<lambda(double, double)> car c'est le type de la lambda et comme ces types ne correspondent pas, la déduction échoue. Pour que la déduction réussisse, vous devez les faire correspondre.

Sans changer la signature de la fonction, vous devez couler f à un std::function afin de le faire fonctionner. Cela ressemblerait à

std::vector<double> C = merge_sorted(A, B, static_cast<std::function<bool(const double,const double)>>(f));

Si cela ne vous dérange pas de changer la signature de la fonction, nous pouvons utiliser

template <class T, class Func>
std::vector<T> merge_sorted(
    const std::vector<T>& a, const std::vector<T>& b,
    Func a_before_b)

Et maintenant, cela n'a pas d'importance si vous passez une std::function ou un lambda ou un foncteur.

Answer 3

1. L'erreur vient du fait que le compilateur essaie de déduire T là où il ne peut pas déduire T pour le std::function qui se voit passer un paramètre lambda.

2. La norme utilise des paramètres de modèle simples pour ces prédicats pour de bonnes raisons.

   2.1 Le prédicat est le plus générique en utilisant un paramètre de modèle.

   Vous pouvez passer dans std::function , std::bind , pointeurs de fonctions, lambdas, foncteurs...

   2.2 La mise en ligne (si possible) est la plus probable.

   Avec un peu de chance, un compilateur est assez intelligent pour mettre en ligne un lambda malgré le fait qu'il soit passé "à travers" un fichier de type std::function dans un modèle mais je ne parierais pas là-dessus. Au contraire, je m'attendrais à ce qu'un compilateur mette en ligne une lambda (si elle est appropriée) si je la passe via son propre type.

3. Votre code a plusieurs autres problèmes.

   3.1 for (;;ia!=a.end() || ib!=b.end()) aquí ; est mal réglé.

   3.2 Même avec un réglage correct ; le prédicat est faux puisque ia!=a.end() || ib!=b.end() maintiendra la boucle en cours d'exécution même si l'un ou l'autre ia == a.end() o ib == b.end() est vrai. Dans la boucle, les deux itérateurs sont déréférencés pour vérifier le prédicat, ce qui nous conduit à un comportement indéfini si nous avons déjà dépassé le dernier élément. La condition de la boucle doit donc être for (;ia!=a.end() && ib!=b.end();) ce qui nous laisse des éléments soit dans a o b .

Voici ce que vous voudrez probablement écrire si vous recherchez la performance et la généralité :

template <class InIt, class OutIt, class Predicate>
auto merge_sorted(InIt first1, InIt last1, InIt first2, InIt last2, 
    OutIt dest, Predicate pred)
{
    // as long as we have elements left in BOTH ranges
    for (;first1 != last1 && first2 != last2; ++dest)
    {
        // check predicate which range offers the lowest value
        // and insert it
        if (pred(*first1, *first2)) *dest = *(first1++);
        else *dest = *(first2++);
    }
    // here either first1 == last1 or first2 == last2 is true
    // thus we can savely copy the "rest" of both ranges 
    // to dest since we only have elements in one of them left anyway
    std::copy(first1, last1, dest);
    std::copy(first2, last2, dest);
    return pred;
}

Answer 4

Puisque je ne peux pas faire de commentaires : Généralement ce que @NathanOliver a dit. A lambda expression ne peut pas être "coulé" en un std::function puisqu'il s'agit - en interne - d'un autre type de construction. Bien sûr, ce serait bien si le compilateur pouvait déduire (via l'analyse statique) qu'il doit créer une structure de type std::function pour la lambda. Mais cela ne semble pas faire partie de C++11/C++14.

Pour résoudre ce problème, je trouve que le plus simple est d'ajouter un typename au modèle :

template <class T, typename F>
std::vector<T> merge_sorted(
    const std::vector<T>& a, const std::vector<T>& b,
    F& a_before_b)

Bien sûr, vous pouvez aussi utiliser class . Voir question Utiliser 'class' ou 'typename' pour les paramètres des modèles ? y l'ancien article de MSDN ici .

Notez également que vous avez une coquille à la ligne 13. Vous vouliez probablement dire :

    for (;;ia!=a.end() || ib!=b.end())