BinaryCrazy's blog

By BinaryCrazy, history, 5 years ago, In English

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

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

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

Instead of int use pair. 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}.