0

I have the following piece of code, which is not compiling. Any ideas to what is causing the problem? My compiler is showing error with the declaration of unordered_map itself. I couldn't understand it. It works fine with ordered map(the usual map). 

//ll stands for long long
long long binomial_tpd(ll n,ll k,unordered_map<pair<ll,ll>,ll>mp)
{
    //cout<<"*";
    if(k==0||n==k)
        return 1;
    else if(mp.find(make_pair(n,k))!=mp.end())
    {
        return mp.find(make_pair(n,k))->second;
    }
    else
    {
        ll b = binomial_tpd(n-1,k-1,mp)+binomial_tpd(n-1,k,mp);
        mp[make_pair(n,k)] = b;
        return b;
    }
}
Puneet
  • 45
  • 8
  • What is the error text? – Jeffrey Jul 14 '20 at 17:29
  • And you should definitely receive the map by reference not copy. – Jeffrey Jul 14 '20 at 17:30
  • c:\mingw\lib\gcc\mingw32\6.3.0\include\c++\bits\hashtable_policy.h:85:34: error: no match for call to '(const std::hash >) (const std::pair&)' noexcept(declval()(declval()))> Does this help? I am getting lots of error lines like this only due to unordered_map. It works fine with ordered_map(normal map). – Puneet Jul 14 '20 at 17:32
  • Any chance this is a C++ 11 / 14 thing? – Michael Dorgan Jul 14 '20 at 17:40
  • 2
    OP needs to provide hash function for pair of `ll` – Jeffrey Jul 14 '20 at 17:43
  • BTW, using `std::map` works since it needs a _less-than_ comparison and `std::pair` provides it. But `std::unordered_map` requires a hash function, which is not defined for `std::pair` by default. – Daniel Langr Jul 14 '20 at 17:54
  • Okay, understood. Thanks. By the way, if I replace, unordered_map with ordered_map, what would be the time complexity of my code. I was trying to code a Dynamic Programming Solution for computing Binomial Coefficients. And I found that the code with map runs longer than pure recursive solution. So, I was wondering what is the complexity of the code? – Puneet Jul 15 '20 at 04:02

0 Answers0