CrazzyBeer's blog

Predefined C++ data structure
By CrazzyBeer, history, 9 years ago, In English

Hello everybody!

Is there a predefined data structure in C++ that allows you to insert numbers (maybe even dublicate keys) and effectively count the amount of numbers greater or less than a given value?

Now I'm using a recursive implementation of Red Black Tree — Here in original (Java) and Here translated to C++ with count_greater implemented.

One idea would be using std::lower_bound in std::map and then std::distance from map.begin() to the result iterator.

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

»
9 years ago, # |
← Rev. 4   Vote: I like it +10 Vote: I do not like it

ordered set
http://codeforces.com/blog/entry/11080

Can use map<int, int>, where key is number, value is count of dublicates, and insert in ordered set pair e.g. make_pair(number, mp[number]++)
And use order_of_key. Time comlexity O(log(n)2) O(log(n))

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

Treap

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>

template<typename key, typename value> class ext_map: public __gnu_pbds::tree<
		key, value, std::less<key>, __gnu_pbds ::rb_tree_tag,
		__gnu_pbds ::tree_order_statistics_node_update> {
};

ext_map will support find_by_order and order_of_key. Just try it.

→ Reply