Codeforces и Polygon могут быть недоступны в период с 6 декабря, 22:00 (МСК) по 7 декабря, 00:00 (МСК) в связи с проведением технических работ. ×

Блог пользователя tribute_to_Ukraine_2022

Автор tribute_to_Ukraine_2022, история, 7 лет назад, По-английски

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);
}

  • Проголосовать: нравится
  • +22
  • Проголосовать: не нравится

»
7 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

I misunderstood what's happening

»
7 лет назад, # |
Rev. 5   Проголосовать: нравится +16 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

In any case, you should use forward declaration:

https://ideone.com/HKSCYx

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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