Hi all,
I hope you are having a great day.
I was solving this problem, which is quite simple with the policy based Data Structure Ordered Set.
However, I wanted to create a Ordered Multiset, but I couldn't get it to work, as I could not erase from the resulting data structure.
Can someone please help me by giving me the code for the ordered_multiset which supports insertion,deletion, order_by_key, and size?
Thanks,
-BC
Edit 2: It finally worked! :) Yay, I solved the problem, but more importantly, I found out some important things when using an ordered_multiset
.
You must include the following in your code, apart from everything else to use the ordered_multiset
.
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
Let's call our ordered_multiset
om
since its suuuuper annoying to type.
We can declare om
with the following code: typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
Search: om.upper_bound({value, -1})
Insert: om.insert({value, om.size() })
Note that the second value of the insertion has to be unique, which is why I use size()
.
Delete: om.erase( om.upper_bound({value, -1}))
Yeah, just combining the Search with om.erase()
.
Finally, my solution: 77420177
Instead of
int
usepair
. First is the value that you need to insert, second is the size of pbds at the moment you insert it. To search just use{value, -1}
.