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:↵
↵
<spoiler summary="Code">↵
```c++↵
#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;↵
```↵
</spoiler>↵
↵
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 of the node when the structure surrounding that node has changed (nodes shifted), which would only happen when a node is added or deleted. Additionally the structure puts in the key first, operates on the key, then puts in the value. ↵
↵
That means if I change the value (frequency of key), then call find_by_order, the answer will be completely wrong because the internal data didn't update. There's also times where I inserted 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.
I thought it would be a good addition because ordered_set doesn't support duplicate entries very well.↵
↵
Here's some code I wrote:↵
↵
<spoiler summary="Code">↵
```c++↵
#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;↵
```↵
</spoiler>↵
↵
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 of the node when the structure surrounding that node has changed (nodes shifted), which would only happen when a node is added or deleted. Additionally the structure puts in the key first, operates on the key, then puts in the value. ↵
↵
That means if I change the value (frequency of key), then call find_by_order, the answer will be completely wrong because the internal data didn't update. There's also times where I inserted 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.
