CODEWITHSUNDEEP
c++templates
Vincenzo
Vincenzo

Reputation: 201

Why can a default template be necessary for template deduction?

I am writing a generic branch and bound algorithm using templates, in C++17.

The code compiles (and runs) fine when I supply the default template argument RealFun2 = RealFun1: 

template <typename Repr, typename SplFun, typename Predicate, 
        typename RealFun1, typename RealFun2=RealFun1>
optional<Repr> branch_and_bound(Repr r0, SplFun split, Predicate goal, 
        RealFun1 F, RealFun2 lower_bound) {
    optional<Repr> BEST; 
    float F_BEST = INFINITY; 
    stack<Repr> ACTIVE; ACTIVE.push(r0); 
    while(!ACTIVE.empty()) {
        Repr r = ACTIVE.top(); ACTIVE.pop(); 
        if(goal(r)) {
            if(F(r) < F_BEST) {
                BEST = r; 
                F_BEST = F(r); 
            }
        }
        else
            for(Repr q: split(r))
                if(lower_bound(q) < F_BEST)
                    ACTIVE.push(q); 
    }
    return BEST; 
}


struct knapsack { /* ... */ }; 
using Repr = pair<knapsack, vector<int>>; 
bool goal(Repr r) { /* ... */ }
float F(Repr r) { /* ... */ }
vector<Repr> split(Repr r) { /* ... */ }
float lower_bound(Repr r) { /* ... */ } 

int main() {
    // ...
    knapsack K(N, cap, weight, value); 
    Repr r0(K, vector<int>(N, 0)); 
    optional<Repr> BEST = branch_and_bound(r0, split, goal, F, lower_bound); 
   // ...
}

However, g++ (7.3.0) complains that it cannot deduce the template parameter RealFun2 if I do not give the default: 

template <typename Repr, typename SplFun, typename Predicate, 
        typename RealFun1, typename RealFun2>
// rest of code is the same

KNAPBB.cpp:105:72: error: no matching function for call to ‘branch_and_bound(Repr&, std::vector<std::pair<knapsack, std::vector<int> > > (&)(Repr), bool (&)(Repr), float (&)(Repr), <unresolved overloaded function type>)’
optional<Repr> BEST = branch_and_bound(r0, split, goal, F, lower_bound);
BRABOUND.cpp:11:16: note:   template argument deduction/substitution failed:
KNAPBB.cpp:105:72: note:   couldn't deduce template parameter ‘RealFun2’
optional<Repr> BEST = branch_and_bound(r0, split, goal, F, lower_bound);

I do not understand the circumstances under which supplying a default should be necessary or not.

Upvotes: 0

Views: 75

Answers (2)

jrok
jrok

Reputation: 55395

So, on to the first part of the error message

no matching function for call to ‘branch_and_bound(Repr&,
std::vector<std::pair<knapsack, std::vector<int> > > (&)(Repr), bool(&)(Repr), float (&)(Repr), <unresolved overloaded function type>)’

The part unresolved overloaded function type> marks the parameter where you pass lower_bound. It means that there are more functions with that name and the compiler can't decide which one you mean.

There are std::lower_bound functions in <algorithm> header, which means you've got using namespace std; somewhere.

It should now be obvious why it works when there's default for the last template parameter - the compiler doesn't have to guess the type.

Upvotes: 2

Vincenzo
Vincenzo

Reputation: 201

The problem turns out to be the name of the function, in the function definition float lower_bound(Repr). Unfortunately, lower_bound clashes with a function from the Standard Library in <algorithm>. Without the template default, the compiler had not enough information to distinguish between the user-provided function and the standard library one.

Upvotes: 1

Related Questions