Skip to content

Instantly share code, notes, and snippets.

@onkar27
Created February 1, 2018 12:59
Show Gist options
  • Save onkar27/8fa3cd46781eb0d655857101c99f8903 to your computer and use it in GitHub Desktop.
Save onkar27/8fa3cd46781eb0d655857101c99f8903 to your computer and use it in GitHub Desktop.
Policy Based Data Structure
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
int main(){
pbds A;
//Add elements in any random order
A.insert(11);
A.insert(1);
A.insert(5);
A.insert(3);
A.insert(7);
A.insert(9);
//Total contents
cout << "1, 3, 5, 7, 9, 11" << endl;
//K-th smallest
int k = 3;
cout << k << "rd smallest: " << *A.find_by_order(k-1) << endl;
k = 5;
cout << k << "th smallest: " << *A.find_by_order(k-1) << endl;
//NO OF ELEMENTS < X
int X = 9;
cout << "No of elements less than " << X << " are " << A.order_of_key(X) << endl;
//DELETE Elements
cout << "Deleted 3" << endl;
A.erase(3);
//Total contents
cout << "1, 5, 7, 9, 11" << endl;
cout << "No of elements less than " << X << " are " << A.order_of_key(X) << endl;
//NEXT BIGGER/SMALLER ELEMENT than X
X = 8;
cout << "Next greater element than " << X << " is " << *A.upper_bound(X) << endl;
return 0;
}
@thundrbol8
Copy link

Does this works for repeated elements too ?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment