Experiments with C++ PBDS: Failed writing a ordered_map

#	User	Rating
1	Benq	3676
2	Kevin114514	3659
3	jiangly	3640
4	turmax	3450
5	tourist	3408
6	strapple	3360
7	Um_nik	3354
8	squareOf105	3348
9	maroonrk	3312
10	idontwannadothis…e	3191

#	User	Contrib.
1	Qingyu	155
2	nik_exists	151
3	maspy	149
4	AmShZ	145
5	Um_nik	143
6	Errichto	139
7	BledDest	136
8	adamant	135
9	maroonrk	132
10	cry	130

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 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.