I was trying to write an ordered map, which will work like a frequency table. I thought it would be a good addition because ordered_set doesn't support duplicate entries very well.

Here's some code I wrote: ~~~~~

include <ext/pb_ds/assoc_container.hpp>

include <ext/pb_ds/tree_policy.hpp>

using namespace std; using namespace __gnu_pbds;

template<class Node_CItr, class Node_Itr, class Cmp_Fn, class _Alloc> struct order_statistics_frequency_list_update { typedef size_t metadata_type; void operator()(Node_Itr it, Node_CItr end_it) { cout<<(*it)->first<<"**"<<(*it)->second<<endl; metadata_type x = (*it)->second; const auto left_child = it.get_l_child(); const auto right_child = it.get_r_child(); if (left_child != end_it) { x += left_child.get_metadata(); } if (right_child != end_it) { x += right_child.get_metadata(); } const_cast<metadata_type&>(it.get_metadata()) = x; } size_t order_of_key(int64_t key) { size_t order = 0; auto it = node_begin(); const auto end = node_end(); while (it != end) { const auto left_child = it.get_l_child(); const auto right_child = it.get_r_child(); if (Cmp_Fn()(key, (*it)->first)) { it = left_child; } else { if (left_child != end) order += left_child.get_metadata(); if (key == (*it)->first) return order; order += (*it)->second; it = right_child; } } return order; } metadata_type find_by_order(size_t order) { auto it = node_begin(); const auto end = node_end(); while (it != end) { const auto left_child = it.get_l_child(); const auto right_child = it.get_r_child(); size_t lchild_size = (left_child == end)? 0 : left_child.get_metadata(); if (order >= lchild_size) { order -= lchild_size; if (order >= (*it)->second) { order -= (*it)->second; it = right_child; } else return (*it)->first; } else { it = left_child; } } return (*it)->first; } virtual Node_CItr node_begin() const = 0; virtual Node_CItr node_end() const = 0; };

typedef tree< int64_t, size_t, less, rb_tree_tag, order_statistics_frequency_list_update

ordered_multiset;

~~~~~

Basically, it changes the update policy to take the frequencies of the keys into account when calculating find_by_order and order_of_key.

However, in the end. I found that this wouldn't work. The tree in pb_ds was implemented only to update the internal data when the tree has changed, so it only operates when a node is added or deleted, and I think it looks at the key first, then puts in the values last. That means if I change the value (frequency of key), then call find_by_order, the answer will be completely wrong because they internal data didn't update. There's also times where I insert key value pairs and it didn't update my frequency into the internal data, resulting in wrong answers.

So in the end I figured it wouldn't work. It was a fairly fruitless exploration for me. But at least I found some good links, so if you are interested in PBDS, here they are:

https://ideone.com/jOxlgl (an example of custom defined operator) https://ideone.com/JlJ86R (print tree)

A few useful blogs: https://codeforces.me/blog/entry/11080 (basics) https://codeforces.me/blog/entry/13279 (creating custom policies, tutorial-ish) https://codeforces.me/blog/entry/110677 (sum of segment) https://neveropen.tech/interval-tree-using-gnu-tree-based-container/

GCC documentation? https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures_design.html#pbds.design.container.tree

Hopefully this is helpful if you're interested in learning about PBDS as well.