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

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?

Tags c++
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by tribute_to_Ukraine_2022 (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

After reading the first few lines of the blog I thought it was a tutorial blog :> You got me in the first half XP.

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it
namespace std {
    ostream &operator<<(ostream &o, vector<int>) {return o;}
}

I don't know about the other cases, but this compiles.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    OK, thanks. I tried putting other variants of this operator in namespace std, and it works too. Do you have any idea why does this help?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      I think it is because of how in C++ operator<< is searched for. See: https://en.cppreference.com/w/cpp/language/lookup. In short: if the operator<< is not declared within std::ostream class, then the only way the compiler can find it is through ADL: https://en.cppreference.com/w/cpp/language/adl. So because std::ostream and std::vector<> are in namespace std::, only std:: will be searched for the operator<<. In case of Foo, std::ostream is in std::, but Foo is in global namespace, so both are searched and a matching definition in global namespace is found. This is because ADL examines only innermost namespace containing the declaration of type of the argument. There are other aspects to how ADL works, but AFAIK only the above applies here.