user21692
user21692

Reputation: 21

Why am I getting this error as part of hashing?

I am solving this question on leetcode.

This is my code where I am basically created an adjacency list and doing a bfs and calculating the result on the way. (not adding too many details wrt the logic and approach because the error I am getting is more related to the unordered_map data structure utilisation):

public:
    vector<double> calcEquation(vector<vector<string>>& eq, vector<double>& val, vector<vector<string>>& queries) 
{
        // create AL
        unordered_map<string, vector<pair<string, double>> > al;
        int n = eq.size();
        int number_nodes = 0;
        for(int i = 0; i < n; ++i)
        {
            auto pair = eq[i];
            al[pair[0]].push_back({pair[1], val[i]});
            al[pair[1]].push_back({pair[0], 1/val[i]});
            number_nodes += 2;
        }
        n = queries.size();
        // check if node is visited
        unordered_map<string, int> vis(number_nodes, 0); // 0=>unvisi
        vector<double>ans;
        for(int i = 0; i < n; ++i)
        {
            string src = queries[i][0];
            string dst = queries[i][1];
            
            // bfs
            queue<pair<string, double>> q;
            q.push({src, 1});
            // mark as vis
            vis[src] = 1;
            int flag = 0;
            while(!q.empty())
            {
                auto curr = q.front();
                q.pop();
                string node = curr.first;
                double val = curr.second;
                // iterate neighs
                for(auto neigh: al[node])
                {
                    string node1 = neigh.first;
                    double val1 = neigh.second;
                    if(!vis[node1])
                    {
                        int calc_result = val1 * val;
                        if(node1 == dst)
                        {
                            ans.push_back(calc_result);
                            flag = 1;
                            cout << val1 << endl;
                            break;
                        }
                        
                        q.push({node1, calc_result});
                        vis[node1] = 1;                             
                    }  
                }
                if(flag) // dst reached stop bfs
                {
                    break;
                }
            }
            ans.push_back(-1);
        }
        return ans;
    }       
};

But I am getting the following compile-time error:

In file included from prog_joined.cpp:1:
In file included from ./precompiled/headers.h:34:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/algorithm:71:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/pstl/glue_algorithm_defs.h:13:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/functional:61:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/unordered_map:46:
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/hashtable.h:981:20: error: no matching function for call to '__distance_fw'
        auto __nb_elems = __detail::__distance_fw(__f, __l);
                          ^~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/hashtable.h:456:4: note: in instantiation of function template specialization 'std::_Hashtable<std::__cxx11::basic_string<char>, std::pair<const std::__cxx11::basic_string<char>, int>, std::allocator<std::pair<const std::__cxx11::basic_string<char>, int>>, std::__detail::_Select1st, std::equal_to<std::__cxx11::basic_string<char>>, std::hash<std::string>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true>>::_Hashtable<int>' requested here
        : _Hashtable(__f, __l, __n, __hf, _H2(), _Hash(), __eql,
          ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/unordered_map.h:177:4: note: in instantiation of function template specialization 'std::_Hashtable<std::__cxx11::basic_string<char>, std::pair<const std::__cxx11::basic_string<char>, int>, std::allocator<std::pair<const std::__cxx11::basic_string<char>, int>>, std::__detail::_Select1st, std::equal_to<std::__cxx11::basic_string<char>>, std::hash<std::string>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true>>::_Hashtable<int>' requested here
        : _M_h(__first, __last, __n, __hf, __eql, __a)
          ^
Line 18: Char 36: note: in instantiation of function template specialization 'std::unordered_map<std::__cxx11::basic_string<char>, int, std::hash<std::string>, std::equal_to<std::__cxx11::basic_string<char>>, std::allocator<std::pair<const std::__cxx11::basic_string<char>, int>>>::unordered_map<int>' requested here
        unordered_map<string, int> vis(number_nodes, 0); // 0=>unvisi
                                   ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/hashtable_policy.h:76:5: note: candidate template ignored: substitution failure [with _Iterator = int]: no type named 'difference_type' in 'std::iterator_traits<int>'
    __distance_fw(_Iterator __first, _Iterator __last)
    ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/hashtable_policy.h:64:5: note: candidate function template not viable: requires 3 arguments, but 2 were provided
    __distance_fw(_Iterator __first, _Iterator __last,
    ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/hashtable_policy.h:70:5: note: candidate function template not viable: requires 3 arguments, but 2 were provided
    __distance_fw(_Iterator __first, _Iterator __last,
    ^

I tried to search for this issue on Google but did not get any clear answer. I found something on the lines that when the key is not hash-able some errors similar to the error that I am getting are thrown but in this case my key is a string and strings are hash-able, so there must be some other issue. Does anyone know the reason for this?

Upvotes: 1

Views: 1256

Answers (1)

yano
yano

Reputation: 5275

The template parameters for vis are <string, int>, yet you try to initialize it with (number_nodes, 0), which is <int, int>. That's an improper way to initialize a map anyway. Aside from the default constructor, there are range-based, copy, move, and initializer-list constructors. Something like

std::map<std::string, int> vis(std::string("hello"), 0);

doesn't match a valid constructor. Perhaps you want something like:

std::map<std::string, int> vis;  // default empty constructor
// there are many ways to insert items into maps, this is an example
vis.insert(std::make_pair(std::to_string(number_nodes), 0));

Also see Why is “using namespace std;” considered bad practice?

Upvotes: 2

Related Questions