Policy Based Data Structures Usecases

pbds.cpp

#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef
tree<
    int,
    null_type,
    less<int>,
    rb_tree_tag,
    tree_order_statistics_node_update
    >
ordered_set;
void tree_order_statistics(){
    ordered_set s;
    // Doest Contain Duplicate keys
    vector<int> arr {1,3,5,10,24,15,45,37};
    // Order of key : 1, 3, 5, 10, 15, 24, 37, 45
    for(int x : arr){
        s.insert(x);
    }
    // find_by_order() can be used to find ith smallest element counting from 0
    // ith largest element can be found by find_by_order(n-i-1) where i >= 1 and n is size of set
    int n = s.size();
    for(int i = 0; i < s.size(); i++){
        // cout << "Order " << i << " : " << *s.find_by_order(i) << "\n";
        cout << (i+1) << "th largest element : " << *s.find_by_order(n-i-1) << "\n";
    }
    cout << "*---------------------------------------*" << "\n";
    // order_by_key() returns no of keys which are strictly smaller than our key
    vector<int> queryKey = {9, 20, 30, 100};
    for(int x : queryKey){
        cout << "No of keys less than " << x << " are " << s.order_of_key(x) << "\n";
    }
    cout << "*---------------------------------------*" << "\n";
    for(int x : queryKey){
        cout << "No of keys greater than " << x << " are " << n - s.order_of_key(x) << "\n";
    }
    /*
    Note : This data structure can used to find inversion in a array
    Online algoritms such are no element less than key in the set
    */
}

/*
Searching Word with given prefix
'+' — add a star's name to the database
'?' — find all the names that start with the characters given in the operation's argument

Input : 
?e
+earth
+egg
?e
+eagle
+earth
?ea
*/

typedef trie<
    string,
    null_type,
    trie_string_access_traits<>,
    pat_trie_tag, // Patricia Trie
    trie_prefix_search_node_update
    >
prefix_trie;
void print_prefix_match(){

    prefix_trie pt;
    pt.insert("sun");
    string q;
    while(cin >> q){
        if(q[0] == '?'){
            cout << q.substr(1) << "\n"; // given query
            auto range = pt.prefix_range(q.substr(1));
            for(auto it = range.first; it != range.second; it++){
                cout << ".." << *it << "\n";
            }
        }else{
            pt.insert(q.substr(1));
        }
    }
}
int main(){
    return 0;
}