zekigurbuz's blog

Question about Ordered Set, GNU PBDS (C++)
By zekigurbuz, history, 5 years ago, In English

Edit: Solved.

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.

  • Vote: I like it
  • +1
  • Vote: I do not like it

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

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

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

It would be helpful if you provided us with code samples of how do you call find_by_order.

ADD: I just wrote a test:

typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int main() { ordered_set x; auto z = x.find_by_order(1); return 0; }

It compiles without errors.

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

    It turns out that I was just being dumb (not being knowledgable in C++). The reason my code was breaking was because I was doing something like this: x.find_by_order(1).first instead of this: x.find_by_order(1)->first.

    Thank you for helping me realize that.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I recently worked on the same problem. But I came to the conclusion that the ordered_set does not really help.

In this problem we would need a structure wich works like a linked list, but with $$$O(logn)$$$ for insert and query. Inserting into a ordered_set allways works with a key, so to insert we would have to generate a key wich fits between two existing keys. That does not work.

Instead, I came to the conclusion that I would have to implement a binary tree where I can implement this insertAtPosition() operation. But that tree needs to be balanced...somehow, I ended up googling for "How to implement a red black tree".

Can you shortly tell how you want to solve it using ordered_set?

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

    I wasn't really trying to use ordered_set to solve this problem. The reason I mentioned the problem was because it is what caused me to think about learning more about ordered_set in the first place. Thank you, though.

    → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Just write a treap. 5 minutes, 40-50 lines.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Doesnt this degenerate to a simple linked list for certain insertion order? ie if we insert allways on first position?

    Edit: I'm sorry, I did not formulate my argument well. The point is, if we use a key to define the order of the elements, we have to generate a key for each insert operation that is at the desired position in the list. To do this we need a key with up to n bits of information. If we work with a key of this size, we run out of memory when generating and out of time when comparing the keys.

    So, we need to implement somehow that instead of a key, the position information is used. Then, a more or less simple rotation operation can make the treap balanced.

    I would implement something like this tutorial but would have extend that by position informations in the structure. Can we do this by maintaining the subtree sizes in every node, or how?

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

    Will do. I was meaning to learn more about treaps as well.

    Thank you for the reply.

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +12 Vote: I do not like it

The value passed to find_by_order has to be of the same type as the key of the tree. This a pair of ints.

But if you just want a simple solution which is based on a gnu extension I would recommend a rope instead of an ordered set. A rope can do all the required operations in $$$O(\log(n))$$$.

#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;

int main() {
	rope<int> r;
	int n;
	cin >> n;
	for (int i = 0, next = 1; i < n; i++) {
		int q, x;
		cin >> q >> x;
		x--;
		if (q == 1) {
			r.insert(r.mutable_begin() + x, next);
			next++;
		} else {
			cout << *(r.mutable_begin() + x) << endl;
		}
	}
}
→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply