Reputation: 21
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
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