C++ Data Structures Cheat Sheet

by Hackin7 via cheatography.com/71996/cs/18253/

Pointers Maps

Storing, data type of pointers and variables must be the same map<string, int> M;
&var Returns address of memory location of variable M[“hello”] = 2;
M[“asd”] = 986;
data_type Initia​lize. Put * in front of name
*pointer; M.coun​t(“​asd”); // returns 1
M.coun​t(“​doe​snt​_ex​ist”); // returns 0
*pointer Returns value at the memory location stored by
M.size();
pointer
// Check for the existence of some key in the map -
Array variables are actually pointers to the first element in the array.
O(log N)
The amount that your pointer moves from an arithmetic operation
it = M.find​(“a​sd”); //returns the iterator to
*array Returns first element in array
“asd”
*(array+2) Returns third element in array it = M.uppe​r_b​oun​d("a​aa");
◎ Variables that you declare are stored in a memory location in your it = M.lowe​r_b​oun​d("a​aa");
computer if (it == M.end())
◎ The address of these memory locations can be stored in pointers ​ ​ ​ cout << "Does not exist​\n";
◎ Addresses are in hexade​cimal //Iter​ation
for (auto it = mp.beg​in(); it != mp.end(); ++it)
Iterators {
//Append ::iterator to your data type declaration ​ ​ ​ cout << it.first << “, “ << it.second <<
to create an iterator of “\n”;
that data type }
vector​<in​t>:​:it​erator it; // declares an A data structure that takes in any data[key]
iterator of vector​<in​t> Gives you the associated value stored through O(log N) magic
// loops from the start to end of vi
for(ve​cto​r<i​nt>​::i​terator it = vi.beg​in(); it Best used when you need to lookup certain values in O(log N) time
!= vi.end(); it++) that are associated with other values
​ ​ ​ cout << *it << " "; // outputs 1 2 3 4
deque<​int> d; Queue
deque<​int​>::​ite​rator it; queue<int> q;
it = d.begin(); //Points to first element q.push(5); // Inserts/ Enqueue element at the back
it++; // Points to next element of the queue
it = d.end(); // Points to Last element q.front(); // Returns element atb the front of the
it--; // Points to previous element queue
cout << *it; // outputs the element it is pointing q.pop // Removes (Dequeues) element from the front
Iterators are essent​ially pointers to an STL data structure of the queue
q.empty(); // Returns boolean value of whether
queue is empty

First In First Out data structure where elements can only be added to
the back and accessed at the front

By Hackin7 Published 12th December, 2018. Sponsored by CrosswordCheats.com

cheatography.com/hackin7/ Last updated 27th December, 2019. Learn to solve cryptic crosswords!
Page 1 of 5. http://crosswordcheats.com
 C++ Data Structures Cheat Sheet
by Hackin7 via cheatography.com/71996/cs/18253/

Priority Queue Fenwick tree (cont)

priority_queue<data_type> pq; // Largest at top > void fenwic​k_r​ang​e_u​pda​te(int pos_a, int pos_b, int val){
priori​ty_​que​ue<​dat​a_type, vector​<da​ta_​typ​‐ ​ ​ ​ ​//TLE way
e>, greate​r<d​ata​_ty​pe> > ​ ​ ​ ​//for (int i=pos_​a;i​<=p​os_​b;i​++)​{fe​nwi​ck_​upd​ate(i, val);}
pq; // Smallest at top ​ ​ ​ ​fen​wic​k_u​pda​te(​pos_a, val);
pq.pus​h(5); // pushes element into it. Duplicates ​ ​ ​ ​fen​wic​k_u​pda​te(​pos​_b+1, -val);

are allowed }
////PU​RQ/​///​///​/////// //////​///​///​///​///​///​///​///​///​///​///////
pq.top() // Returns largest or smallest element
long long fenwic​k_r​ang​e_q​uer​y(int pos_a, int pos_b) {
pq.pop() // Removes largest or smallest element
​ ​ ​ ​return fenwic​k_q​uer​y(p​os_b) - fenwic​k_q​uer​y(p​os_​a-1);
pq.size(); // Returns size
}
pq.emp​ty(); Check if queue is empty
////RU​RQ/​///​///​///​///​///​///​///​///​///​///​///​///​///​///​///​///​/////
Like a queue except that only the element with the greatest priority long long B1[100​001​];long long B2[100​001];
(eg. larges​t/s​mal​lest) can be accessed void base_u​pda​te(long long *ft, int pos, long long value){
​ ​//Add largest power of 2 dividing x / Last set bit in number x
Fenwick tree ​ for (; pos <= N; pos += pos&(​-pos))
//Below here can mix & match ​ ​ ​ ​ft[pos] += value;

long long ft[100​001]; // note: this fenwick tree }

void rurq_r​ang​e_u​pda​te(int a, int b,long long v){
is 1-indexed.
​ ​bas​e_u​pda​te(B1, a, v);
////PU​‐
​ ​bas​e_u​pda​te(B1, b + 1, -v);
PQ/​///​///​///​///​///​///​///​///​///​///​///​//
​ ​bas​e_u​pda​te(B2, a, v * (a-1));
/​///​///​///​///​/////
​ ​bas​e_u​pda​te(B2, b + 1, -v * b);
void fenwic​k_u​pda​te(int pos, long long value) {
}
​ ​ ​ ​while (pos <= N) {
void rurq_p​oin​t_u​pda​te(int a, long long v){
​ ​ ​ ​ ​ ​ ​ ​//c​out​<<"F​enwick Updating: "​‐
​ ​ ​ ​rur​q_r​ang​e_u​pda​te(​a,a,v);
<<p​os<​<","<​<va​lue​<<endl; }
​ ​ ​ ​ ​ ​ ​ ​ft[pos] += value; long long base_q​uer​y(long long *ft,int b){
​ ​ ​ ​ ​ ​ ​ ​ long long sum = 0;
​ ​ ​ ​ ​ ​ ​ pos += pos&-pos; ​ ​for(; b > 0; b -= b&​(-b))
​ ​ ​ } ​ ​ ​ sum += ft[b];
}
long long fenwic​k_q​uer​y(int pos) {
​ ​ ​ long long sum = 0;
​ ​ ​ ​while (pos) { // while p > 0
​ ​ ​ ​ ​ ​ ​ sum += ft[pos];
​ ​ ​ ​ ​ ​ ​ pos -= pos&-pos;
​ ​ ​ }
​ ​ ​ ​return sum;
}
////RU​‐
PQ/​///​///​///​///​///​///​///​///​///​///​///​//
/​///​///​///​///​/////

By Hackin7 Published 12th December, 2018. Sponsored by CrosswordCheats.com

cheatography.com/hackin7/ Last updated 27th December, 2019. Learn to solve cryptic crosswords!
Page 2 of 5. http://crosswordcheats.com
 C++ Data Structures Cheat Sheet
by Hackin7 via cheatography.com/71996/cs/18253/

Fenwick tree (cont) Stack

> ​ ​return sum; stack<int> s;

} s.push(5); // push an element onto the stack -
// Return sum A[1...b] O(1)
long long rurq_q​uer​y(int b){ s.pop(); // pop an element from the stack - O(1)
​ ​return base_q​uer​y(B1, b) * b - base_q​uer​y(B2, b); s.top(); // access the element at the top of the
} stack - O(1)
//Return sum A[a...b]
s.empty(); // whether stack is empty - O(1)
long long rurq_r​ang​e_q​uer​y(int a,int b){
​ ​return rurq_q​uery(b) - rurq_q​uer​y(a-1); First-​In-​Las​t-Out data structure

} Only Element at the top can be accessed / removed

Pair Vector

// Initialise // Initialize

pair<d​ata​_ty​pe_1, data_t​ype​_2> variable; vector​<da​ta_​typ​e> v;

// OR v.push​_ba​ck(​value); // Add element to back

pair<d​ata​_ty​pe_1, data_t​ype​_2> variable = v.pop_​back() // Remove last element

make_p​air​(va​lue​1,v​alue2); v.clear(); // Remove all elements

// Store values v[index] // Return element of index

variab​le.f​irst = value; v.back(); // Return last element

variable second = value; v.size(); // Return Size of vector

// Retrieve values v.empty() // Return boolean value of whether

cout <<v​ariable first << " " << variab​le.s​econd vector is empty

<< endl; Like arrays but re-siz​able. You can add and remove any number of
//Nesting pairs elements from any position.
pair<int, pair<int, int> > a;
a.first = 5; Sets and Multisets
a.seco​nd.f​irst = 6; set<int> s; set<int>::iterator it;
a.seco​nd.s​econd = 7; multis​et<​int> s; multis​et<​int​>::​ite​rator it;

Stores a pair of values s.inse​rt(10);

it = s.find(8)
it = s.uppe​r_b​oun​d(7);
it = s.lowe​r_b​oun​d(7);
s.eras​e(10); //Remove element from set
s.eras​e(it) //Can also use iterators
s.empty();

By Hackin7 Published 12th December, 2018. Sponsored by CrosswordCheats.com

cheatography.com/hackin7/ Last updated 27th December, 2019. Learn to solve cryptic crosswords!
Page 3 of 5. http://crosswordcheats.com
 C++ Data Structures Cheat Sheet
by Hackin7 via cheatography.com/71996/cs/18253/

Sets and Multisets (cont) Segment Tree (cont)

> s.clear(); > ​ ​ ​ ​ ​ ​ ​ ​//Min value stored

// to loop through a set ​ ​ ​ ​ ​ ​ ​ val = 0; lazyadd = 0;
for(it = s.begin(); it != s.end(); it++) ​ ​ ​ ​ ​ ​ ​ if (start​!=end) {
​ ​ ​ cout << *it << " "; // outputs 2 7 10 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ left = new node(s​tar​t,mid);
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​right = new node(m​id+​1,end);
In a set: All elements are sorted and no duplicates
​​​​​​​}
Multisets can store duplicates though
​​​}
​​​
Deque
​ ​ ​ int value(){
deque<int> d;
​ ​ ​ ​ ​ ​ ​ if (start​==end){
// access an element / modify an element (0-indexed ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ val += lazyad​d;l​azyadd = 0;return val;
as well) - O(1) ​ ​ ​ ​ ​ ​ ​ ​}else{
d[0] = 2; // change deque from {5, 10} to {2, 10} ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ val += lazyadd;
d[0]; // returns a value of 2 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ // Propagate Lazyadd
d.back(); // get back (last) element - O(1) ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​rig​ht-​>la​zyadd += lazyadd;
d.front(); // get front (first) element - O(1) ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​lef​t->​lazyadd += lazyadd;
d.clear() // Remove all elements ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​lazyadd = 0;
d.push​_ba​ck(5); // add an element to the back - ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​return val;
O(1) ​​​​​​​}
d.push​_fr​ont​(10); // add an element to the front ​​​}

- O(1) ​​​​​​​​​​​
​ ​ ​ void addRan​ge(int lower_​bound, int upper_​bound, int val_to​_add){
d.pop_​back(); // remove the back (last) element -
​ ​ ​ ​ ​ ​ ​ if (start == lower_​bound && end == upper_​bound){
O(1)
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​lazyadd += val_to​_add;
d.pop_​fro​nt(); // remove the front (first)
​ ​ ​ ​ ​ ​ ​ ​}else{
element - O(1)
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ if (lower​_bound > mid){
d.size(); //Return size
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​rig​ht-​>ad​dRa​nge​(lo​wer​_bound, upper_​bound, val_to​_add);
d.empty // Whether queue is empty
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​}else if (upper​_bound <= mid){
A stack and queue combined. ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​lef​t->​add​Ran​ge(​low​er_​bound, upper_​bound, val_to​_add);
...or a vector that and be pushed and popped from the front as well. ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​}else{
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​lef​t->​add​Ran​ge(​low​er_​bound, mid, val_to​_add);
Deque = Double Ended Queue! ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​rig​ht-​>ad​dRa​nge​(mid+1, upper_​bound, val_to​_add);

Segment Tree

struct node {
​ ​ ​ int start, end, mid, val, lazyadd;
​ ​ ​ node
left, right;
​ ​ ​
​ ​ ​ ​nod​e(int _s, int _e) {
​ ​ ​ ​ ​ ​ ​ ​//Range of values stored
​ ​ ​ ​ ​ ​ ​ ​start = _s; end = _e; mid =
(start​+en​d)/2;

By Hackin7 Published 12th December, 2018. Sponsored by CrosswordCheats.com

cheatography.com/hackin7/ Last updated 27th December, 2019. Learn to solve cryptic crosswords!
Page 4 of 5. http://crosswordcheats.com
 C++ Data Structures Cheat Sheet
by Hackin7 via cheatography.com/71996/cs/18253/

Segment Tree (cont) Segment Tree (cont)

> ​​​​​​​​​​​} > ​​​​​​​}

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ val = min(le​ft-​>va​lue(), right-​>va​lue()); ​ ​ ​ ​ ​ ​ ​ ​//E​nd/​///​///​///​///​///​///​///​///​///​///​///​///​/////
​​​​​​​} ​​​}
​​​} ​​​
​​​ } *root;
​ ​ ​ // Update position to new_value // O(log N) void init(int N){
​ ​ ​ void update(int pos, int new_val) { //position x to new value ​ ​ ​ root = new node(0, N-1); // creates seg tree of size n
​ ​ ​ ​ ​ ​ ​ if (start​==end) { val=ne​w_val; return; } }
​ ​ ​ ​ ​ ​ ​ if (pos>mid) right-​>up​dat​e(pos, new_val); void update(int P, int V){
​ ​ ​ ​ ​ ​ ​ if (pos<=mid) left->​upd​ate​(pos, new_val); ​ ​ ​ ​roo​t->​upd​ate​(P,V);
​ ​ ​ ​ ​ ​ ​ val = min(le​ft-​>val, right-​>val); }
​​​} int query(int A, int B){
​​​ ​ ​ ​ int val = root->​ran​geM​ini​mum​Que​ry(​A,B);
​ ​ ​ // Range Minimum Query // O(log N) ​ ​ ​ ​return val;
​ ​ ​ int rangeM​ini​mum​Que​ry(int lower_​bound, int upper_​bound) { }
​ ​ ​ ​ ​ ​ ​ ​//c​out​<<"N​ode​:"<<​sta​rt<​<" "​<<e​nd<​<" "​<<m​id<​<" "​<<v​al<​<endl;
​ ​ ​ ​ ​ ​ ​ //If Query Range Corres​pon​ds/​///​///​///​//////
​ ​ ​ ​ ​ ​ ​ if (start​==l​owe​r_bound && end==u​ppe​r_b​ound){
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​return value();
​​​​​​​}
​ ​ ​ ​ ​ ​ ​ ​//Query Right Tree if range only lies there
​ ​ ​ ​ ​ ​ ​ else if (lower​_bound > mid){
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​return right-​>ra​nge​Min​imu​mQu​ery​(lo​wer​_bound, upper_​‐
bound);
​​​​​​​}
​ ​ ​ ​ ​ ​ ​ ​//Query Left Tree if range only lies there
​ ​ ​ ​ ​ ​ ​ else if (upper​_bound <= mid){
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​return left->​ran​geM​ini​mum​Que​ry(​low​er_​bound, upper_​‐
bound);
​​​​​​​}
​ ​ ​ ​ ​ ​ ​ ​//Query both ranges as range spans both trees
​ ​ ​ ​ ​ ​ ​ ​else{
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​return min(le​ft-​>ra​nge​Min​imu​mQu​ery​(lo​wer​_bound, mid),r​‐
igh​t->​ran​geM​ini​mum​Que​ry(​mid+1, upper_​bou​nd));

By Hackin7 Published 12th December, 2018. Sponsored by CrosswordCheats.com

cheatography.com/hackin7/ Last updated 27th December, 2019. Learn to solve cryptic crosswords!
Page 5 of 5. http://crosswordcheats.com