Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

tribute_to_Ukraine_2022's blog

Weird C++ template question
By tribute_to_Ukraine_2022, history, 7 years ago, In English

I tried to define two template functions outputing pairs and vectors of any type. If it is overloaded operator it works fine, but for standard functions lookup fails to find function defined for pair if it is declared after called. Does anybody know why?

# include <bits/stdc++.h>
using namespace std;
int Hash(int x) {
	return x;
}
template <typename T> int Hash(vector<T> x) {
	int ans = 0;
	for (auto c : x)
		ans = 2 * ans + Hash(c);//Fails if c is a pair: no matching function for call to ‘Hash(std::pair<int, int>&)
	return ans;
}
template <typename T, typename C> auto Hash(pair <T, C> x) -> int {
	return Hash(x.first) + Hash(x.second) * 14;
}
template <typename T>
ostream &operator<<(ostream &os, vector <T> x)
{
	os << "{";
	int cou = 0;
	for (auto c : x) {
		if (cou++) os << ", ";
		os << c;//Works even if c is a pair despite calling operator declared late
	}
	return os << "}";
}
template <typename T, typename C> ostream & operator<< (ostream &os, pair<T, C> x) {
	return os << "<" << x.first << ", " << x.second << ">"; 
}
ostream & Output(ostream &os, const char * x) {
	return os << x;
}
ostream & Output(ostream &os, int x) {
	return os << x;
}
template <typename T>
ostream &Output(ostream &os, vector <T> x)
{
	Output(os, "{");
	int cou = 0;
	for (auto c : x) {
		if (cou++) Output(os,  ", ");
		Output(os, c);//Fails if c is a pair: no matching function for call to ‘Output(std::ostream&, std::pair<int, int>&)
	}
	return Output(os, "}");
}
template <typename T, typename C> ostream & Output (ostream &os, pair<T, C> x) {
	return Output(Output(Output(Output(Output(os, "<"), x.first), ", "), x.second), ">"); 
}
int main() {
	vector <pair <int, int> > x;
	x.emplace_back(13, 10);
	x.emplace_back(1, 16);
	cout << x << endl;//Compiles and outputs {<13, 10>, <1, 16>}
	cout << Hash(x) << endl;//no matching function for call to ‘Hash(std::pair<int, int>&)    ans = 2 * ans + Hash(c);
	Output(cout, x);//no matching function for call to ‘Output(std::ostream&, std::pair<int, int>&)   Output(os, c);
}
  • Vote: I like it
  • +22
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I misunderstood what's happening

→ Reply
»
7 years ago, # |
← Rev. 5   Vote: I like it +16 Vote: I do not like it

I suppose that

cout << x << endl;//Compiles and outputs {<13, 10>, <1, 16>}

compiles only due to the GCC bug: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56943

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In any case, you should use forward declaration:

https://ideone.com/HKSCYx

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I believe that the correct answer was already produced above: operators lookup rules should not differ much from standard lookup rules; you cannot call an operator if it's declared below the line of code which calls it. You should use forward declarations to enable this.

On a related note: I think your code can be significantly improved:

  1. You don't need Output(x, y) function at all—it only clutters the code; use x << y directly. In particular, return Output(Output(Output(Output(Output(os, "<"), x.first), ", "), x.second), ">"); can be replaced with os << "<" << x.first << ", " << x.second << ">", which is much less verbose. It's C++, not Java, we know what << means in IO-context.
  2. You should accept arguments which you want to print by a const reference: operator<< (ostream &os, const pair<T, C> &x), not operator<< (ostream &os, pair<T, C> x). Otherwise, the pair may be copied for output, which is useless. The same thing applies for vector<T> and for (auto c : x); use for (const auto &c : x).
  3. ans = 2 * ans + Hash(c); is a very bad polynomial hash. The base should be greater than number of distinct hashes of a single element at the very least, otherwise, {0, 2} and {1, 0} have the same hash.
  4. Same here: Hash(x.first) + Hash(x.second) * 14;. Use a bigger constant.
  5. Do not multiply numbers which are expected to overflow (i.e. hashes) in signed types, it's undefined behavior. Use unsigned int (or simply unsigned) or unsigned long long.
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ad 1. The whole point is that it is the same, but operator<< compiles, while Ourput doesn't Ad 2,3,4,5. That's not a real code i want to use, just a sample code to illustrate the problem with name visibility

    → Reply