Question about Ordered Set, GNU PBDS (C++)

Revision en2, by zekigurbuz, 2020-05-14 07:46:27

Recently, I was looking at this Kattis problem. I was considering a (perhaps simpler, i.e. smaller bounds on Q) online version of the problem, and considered using it as an opportunity to learn the GNU policy-based ordered set data structure (for C++). I first noticed that the structure of the define statement could be modified to support different data types other than just ints.

For example, this: #define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>

instead of this: #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

Obviously, the two main functionalities of this data structure are find_by_order(x) and order_of_key(x). However, when using the ordered set with pair<int, int> as the data type, I noticed that when trying to use the find_by_order(x) method (by passing in an int as a parameter), my code was immediately throwing a long, practically unreadable error.

I was wondering if anyone familiar with C++ or GNU PBDS could help explain what is going on (I can send my code so far if necessary). Any help would be appreciated.

Thank you.

Tags gnu, pbds, c++, kattis


  Rev. Lang. By When Δ Comment
en3 English zekigurbuz 2020-05-14 18:49:42 17 Tiny change: 'Recently, ' -> 'Edit: Solved.\n\nRecently, '
en2 English zekigurbuz 2020-05-14 07:46:27 2 Edit: spelling.
en1 English zekigurbuz 2020-05-14 07:45:56 1283 Initial revision (published)