Codeforces и Polygon могут быть недоступны в период с 6 декабря, 22:00 (МСК) по 7 декабря, 00:00 (МСК) в связи с проведением технических работ. ×

Блог пользователя tribute_to_Ukraine_2022

Автор tribute_to_Ukraine_2022, история, 5 лет назад, По-английски

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?

Теги c++
  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
namespace std {
    ostream &operator<<(ostream &o, vector<int>) {return o;}
}

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится +28 Проголосовать: не нравится

      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.