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

Ordered set mindfuck

Revision en1, by tribute_to_Ukraine_2022, 2020-02-22 21:45:19

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?

Tags c++

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English tribute_to_Ukraine_2022 2020-02-22 21:49:14 110
en1 English tribute_to_Ukraine_2022 2020-02-22 21:45:19 2991 Initial revision (published)