Блог пользователя CrazzyBeer

Predefined C++ data structure
Автор CrazzyBeer, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 4   Проголосовать: нравится +10 Проголосовать: не нравится

ordered set
http://codeforces.me/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))

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Treap

→ Ответить
»
9 лет назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится 
#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.

→ Ответить