Policy based data structures (PBDS)

Implement set with the ability to know index of item  --> data structure order statistics tree, (unfortunately only available for the GNU C++)

g++ compiler supports some data structures that are not part of standard C++ library
---> such structures are called policy-based data structures

#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
template< typename Key, // Key type
	  typename Mapped, // Mapped-policy --> USE null_type for sets (bcz no mapping)
	  typename Cmp_Fn = less<Key>, // Key comparison functor
	  typename Tag = rb_tree_tag, // Specifies which underlying data structure to use
	  class Node_Update = null_node_update, // A policy for updating node invariants >
Node_Update — class denotes policy for updating node invariants. By default, set to null_node_update, i.e, additional info not stored in the vertices. In addition, C++ implemented an update policy tree_order_statistics_node_update => WE USE this


This gives the same benefit as set with two extra features :-   
pbds.find_by_order(k) => returns iterator to the k-th index like array --> from zero
order_of_key(7) => return number of items in set that are strictly smaller than 7
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

  • If use greater<int> --> everything is sorted in reversed order

  • If use less_equal<int> --> behaves similar to multiset --> BUT pbds is to store elements in strict ordering => less_equal can cause undefined behavior
    • Instead use pair<int, int>   --> SEE below
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
  • Search - pbds.upper_bound({value, -1})
  • Insert - pbds.insert({value, pbds.size()})
    • Note that the second value of the insertion has to be unique => use size()


  • Delete - pbds.erase(pbds.upper_bound({value, -1}))

Comments

Post a Comment

Popular posts from this blog

Graphs

Image
GRAPH  Modelling - Multi-Source BFS --> Use normal BFS but insert all the sources in queue and make their distance = 0 --> Update the distance for others as usual for normal BFS ( Link ) Transform existing Graph and use BFS (non-weighted) & Dijkstra (weighted) Hot (red)  -  Cold (blue)  problem => Update graph s.t. red & blue are alternate  make 2*n nodes as A => A' and A'' connect A' -> B'' (for hot) and A'' -> B' (for cold) Directed - weighted G + can remove k edges make G => k+1 times as A', A'', A''', ..... Add edge of weight 0 in between the k+1 graphs n city + m roads + max storage (c litre) => weighted road (consume w litre) + cost[i] (cost per litre to refuel at i-th point) => min. cost from s to t We have to move from A to B  capacity = 3. From A -> A' -- 1 litre needed at value in cost array. From A''' -> B' because loss of 2 litres (as shown in the below d...
Read more

Basics

Comment -  for In-line comment (means comment in same line) --> Use //                          for multi-line comment --> Use /* ........ */ Array -  int arr[10] = {4, 5, 8} --> creates array of size 10 with first 3 elements known  Access - 10[arr] or arr[10]  --> both correct bcz *(10+arr) and *(arr+10) are same Pair -  pair<int,string> p  = {2 , "fsf"} How to access ? p.first and p.second Vector -  array with dynamic memory size =>  continuous memory allocation How to  initialize vector ? vector <double> v(10) => declares vector of size 10 with each value as 0 vector <double> v(7 , 3) => declares vector of size 7 with each value as 3 vector <double> v = {1, 3, 5, 10} => declares vector of with given values vector <double> v(st.begin(), st.end()) => declares vector from given set vector <int> v1 =v  ...
Read more

Hashing

When we cannot use hashing -  when  order is important =>  Find key which is just smaller than the given key. COMPRESSION  MAP  => H(key) = key % M (M is prime number close to table size)  POLYNOMIAL  ACCUMULATION  =>  H(string) = [(s[0]*x^0) +  (s[1]*x^1) +  ....] % M   Requirements for hash function => H(key) = value No matter how many times you pass key => value should always be same If M is size of hash table => value must lie between 0 to M-1 Value should be uniformly distributed --> less collision UNIVERSAL  HASHING -  choose any hash function uniformly at random
Read more