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?
↵
~~~~~↵
#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?
