tribute_to_Ukraine_2022's blog

By tribute_to_Ukraine_2022, history, 5 years ago, In English

Let's write some simple code using policy based data structures

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class c, class cmp = less<c> > using ordered_set = tree<c, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
int main() {
	ordered_set<vector <int> > s;
	s.insert({1, 2, 6});
	s.insert({1, 3, 3});
	s.insert({2, 6});
	cout << s.order_of_key({1, 3}) << endl;
	for (int x : *s.find_by_order(1)) cout << x << " ";
	cout << endl;
}

Compiles and outputs:

1
1 3 3 

So far so good, but let's try to compile it with -D_GLIBCXX_DEBUG. Now the compiler spews out an error containing:

/usr/include/c++/7/ext/pb_ds/detail/debug_map_base.hpp:208:7: error: no match for ‘operator<<’ (operand types are ‘std::basic_ostream<char>’ and ‘const std::__debug::vector<int>’)
    std::cerr << __file << ':' << __line << ": check_key_exists "
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
       << r_key << std::endl;

OK, so we need to define output operator for vector <int>, right? Let's see

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class c, class cmp = less<c> > using ordered_set = tree<c, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
ostream &operator<<(ostream &o, vector<int>) {return o;}
int main() {
	ordered_set<vector <int> > s;
	s.insert({1, 2, 6});
	s.insert({1, 3, 3});
	s.insert({2, 6});
	cout << s.order_of_key({1, 3}) << endl;
	for (int x : *s.find_by_order(1)) cout << x << " ";
	cout << endl;
}

I tried various variants of this operator<< including:

template <class c> ostream &operator<<(ostream &o, vector<c>)

template <class c, typename=typename enable_if<!is_same<c,string>::value,decltype(c().end())>::type> ostream &operator<<(ostream &o, c u)

ostream &operator<<(basic_ostream<char> &o, vector<int>)

(EDIT: also tried defining the operator before and after including assoc_container.hpp. Doesn't help either) None of this changes anything, we get the same error as before. To confuse us even more

#include <bits/stdc++.h>
using namespace std;
ostream &operator<<(ostream &o, vector <int> ){return o;}
struct Foo {
	int x;
};
bool operator<(Foo a, Foo b) {
	return a.x < b.x;
}
ostream &operator<<(ostream &o, Foo) {return o;} //If we skip this line, compiler spews out an error as before, but if we include it suddenly all works
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class c, class cmp = less<c> > using ordered_set = tree<c, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
int main() {
	ordered_set<Foo> s;
	s.insert(Foo{5});
	s.insert(Foo{1});
	s.insert(Foo{7});
	cout << s.order_of_key(Foo{4}) << endl;
	cout << s.find_by_order(2)->x << endl;
}

Anyone into C++ enough to explain what's going on here?

Full text and comments »

Tags c++
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);
}

Full text and comments »