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().