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>)
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?