templated function argument in C++14

Question

This code does not compile, not even under C++14, because of problems with template type deduction. What is the least inelegant workaround?

#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
}

Here the error message from 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);

==

Later edit, just for the record: Here comes a version of the code that compiles (thanks to received answers) and that executes correctly (several corrections of the above untested code):

#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
}

Unless you are going to overload merge_sorted to death, I would just use a separate template parameter for the type of a_before_b, not require std::function. — Marc Glisse, Mar 08 '17 at 14:01
@Marc: not sure I understand - could you please elaborate, possibly in form of an answer? — Joachim W, Mar 08 '17 at 14:02
Notice, that you can repurpose `std::merge` in `merge_sorted` body. — Revolver_Ocelot, Mar 08 '17 at 14:04
Thank you all for your comments and answers. You convinced me that the predicate template parameter is the way to go. Now my code compiles ... and I see that it is still flawed (accessing *ib after b.end() has been reached) ... but this is a completely different story. — Joachim W, Mar 08 '17 at 14:22

score 3 · Answer 1 · answered Mar 08 '17 at 13:59

You need to make the type of a_brefore_b a non-deduced context somehow. I generally introduce a suitably-named helper for this:

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)

Of course (as @Marc Glisse pointed out in comments), it's quite unnecessary to force use of std::function for the type of a_before_b in the first place. Not to mention the fact that it can easily come with a performance penalty (std::function uses type erasure and dynamic dispatch internally). Just follow what the Standard Library does and type the predicate by a template parameter:

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

NathanOliver · Accepted Answer · 2017-03-08T14:11:37.717

3

The problem here is that f is not a std::function. It is some unnamed class type but it is not a std::function. When the compiler does template argument deduction it does not do any conversions, it works with the parameters as is to deduce their type. That means where it expects to see a std::function<bool(const T, const T)> it sees main()::<lambda(double, double)> as that is the type of the lambda and since those types do not match the deduction fails. In order to get deduction to succeed you need to get them to match.

Without changing the function signature you have to cast f to a std::function in order to get it to work. That would look like

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

If you do not mind changing the function signature then we can use

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

And now it doesn't matter if you pass a std::function or a lambda or a functor.

edited Mar 08 '17 at 14:11

answered Mar 08 '17 at 14:02

NathanOliver

171,901
28
288
402

Great explanation, thanks. I tend to prefer the cast from `f` to `std::function`. How would you that? Is `std::bind` pertinent? – Joachim W Mar 08 '17 at 14:08
1

While we're at it, why not get rid of `std::vector` and rewrite it in terms of iterators? – n. m. could be an AI Mar 08 '17 at 14:09
3

@JoachimWuttke: The plain template is a more generic solution and has a higher potential for inlining. – Pixelchemist Mar 08 '17 at 14:10
@Pixelchemist: "plain template" = Nathan's solution = Angew's solution ? – Joachim W Mar 08 '17 at 14:11
@JoachimWuttke Just updated the answer with the cast. You also have a typo in the code. `ib!=ib.end()` should be `ib!=b.end()` – NathanOliver Mar 08 '17 at 14:11
@JoachimWuttke Study the standard library. There are usually pretty good reasons behind the way it does stuff. Algorithms from `` generally don't take `std::function`. You can't go too much wrong emulating them. – n. m. could be an AI Mar 08 '17 at 14:17
2

@JoachimWuttke `std::function` also prohibits non-copyable types, which can be captured with a lambda. – Kyle Strand Mar 08 '17 at 15:04

Pixelchemist · Answer 3 · 2017-03-08T14:41:37.487

The errror comes from the compiler trying to deduce T where it can't deduce T for the std::function parameter which gets passed a lambda.
The standard uses plain template paramters for such predicates for good reasons.

2.1 The predicate is most generic using a template paramter.

You can pass in std::function, std::bind, function pointers, lambdas, functors...

2.2 Inlining (if possible) is most likely to occur.

With a whole bunch of luck a compiler is smart enough to inline a lambda despite being passed "through" a std::function into a template but I wouldn't bet on that. On the contrary, I'd actually expect a compiler to inline a lambda (if suitable) if I pass it via its own type.
Your code has several other issues.

3.1 for (;;ia!=a.end() || ib!=b.end()) here ; is set incorrectly.

3.2 Even with correctly set ; the predicate is wrong since ia!=a.end() || ib!=b.end() will keep the loop running eventhough either ia == a.end() or ib == b.end() is true. Within the loop both iterators are dereferenced to check the predicate which leads us into undefined behaviourland if we are already one past the last element. The loop condition must therefore be for (;ia!=a.end() && ib!=b.end();) which leaves us with elements in either a or b.

Here is what you would probably want to write if you're after performance and generality:

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;
}

score -2 · Answer 4 · edited May 23 '17 at 11:53

Since I can not comment: Generally what @NathanOliver said. A lambda expression can not be "cast" to a std::function, since it is - internally - a different kind of construct. Of course it would be nice if the compiler could infer (via static analysis) it has to create a std::function object for the lambda. But that doesn't seem to be part of C++11/C++14.

To resolve this, I find it easiest to add a typename to the template:

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

Of course you can also use class. See question Use 'class' or 'typename' for template parameters? and the old MSDN article here.

Also, note you have a typo in line 13. You probably meant:

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

templated function argument in C++14

4 Answers4