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:
Code#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<int64_t>,
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.
