STL Cheatsheet for Competitive Programming

I've prepared a C++ cheatsheet that covers most of the data structures and STL functionalities you'll ever use for programming competitions or interview tests for tech companies. Think about the rest of this post as a quick refresher to the most commonly used parts of STL. Without further ado, here it is!

/*
This a header file that includes every standard library. 
You can use it to save time.

NOTE: This header file may only be recognized by the GCC compiler.

*/
#include <bits/stdc++.h>

/*
//Use this if the above header file doesn't work.

#include <iostream>

#include <algorithm>
#include <list>
#include <map>
#include <priority_queue>
#include <stack>
#include <string>
#include <vector>
*/

using namespace std;


// These will be used later
struct Person {
  string name;
  int age;
} p1, p2, p3;

struct is_older {
  bool operator()(struct Person p1, struct Person p2) {
    	return p1.age > p2.age;
    }
};

bool compare_names(struct Person p1, struct Person p2) {
    	return p1.name < p2.name;
}

bool way_to_sort(int i, int j) { return i > j; }


int main() {

  /*
  ========
   STACK
  ========
  */

  stack <string> distros; //Create a stack of strings.

  distros.push("Ubuntu");  //Pushes elements into the stack.
  distros.push("Mint");

  cout << "Number of distros in the stack are " << distros.size() << endl;
  cout << "Distro on the top is " << distros.top() << endl;

  distros.pop();
  cout << "The top of the stack is now " << distros.top() << endl;

  /*
  ========
   VECTOR
  ========
  */

  vector <int> numbers;

  if (numbers.empty()){ //check if the vector is empty?
    cout << "The vector is empty :(" << endl;
  }

  for(int i=0; i<100; i+=10){ //Add some values to the vector
    numbers.push_back(i);
  }

  cout << "Size of the vector is " << numbers.size() << endl;

  // iterating over the vector, declaring the iterator
  vector <int>::iterator it;

  cout << "The vector contains: ";
  for (it=numbers.begin(); it!=numbers.end(); it++) {
    cout << "  " << *it;
  }

  // getting value at a particular position
  int position = 5;
  cout<<"\nVector at position "<<position<<" contains "<<numbers.at(position)<<endl;

  // deleting an element at a position
  numbers.erase(numbers.begin() + position);
  cout<<"Vector at position "<<position<<" contains "<<numbers.at(position)<<endl;

  // deleting a range of elements, first two elements
  // NOTE: You may expect elements at 0, 1, and 2 to be deleted
  // but index 2 is not inclusive.
  numbers.erase(numbers.begin(), numbers.begin()+2);
  cout << "The vector contains: ";
  for (it=numbers.begin(); it!=numbers.end(); it++) {
    cout << "  " << *it;
  }

  // Clearing the vector
  numbers.clear();
  if (numbers.empty()){
    cout << "\nThe vector is now empty again :(";
  }


  /*
  =========
   HASHMAP
  =========
  */

  // Declaration <key type, value type>
  map <string, string> companies;

  companies["Google"] = "Larry Page";
  companies["Facebook"] = "Mark Zuckerberg";

  // insertion can also be done as
  companies.insert(pair<string, string> ("Xarvis Tech", "xarvis"));
  // or
  companies.insert(map<string,string>::value_type("Quora", "Adam D'Angelo"));
  // or even
  companies.insert(make_pair(string("Uber"), string("Travis Kalanick")));

  // Iterating the map
  map<string, string>::iterator itz;
  cout << "\n\nCompanies and founders" << endl;
  for (itz=companies.begin(); itz!=companies.end(); itz++){
    cout << "Company: " << (*itz).first << "\t Founder: " << itz->second <<endl;
  }

  itz = companies.find("Google");
  cout << itz->second;

  /*
  ==============
   LINKED LISTS
  ==============
  */
  list<int> mylist;
    list<int>::iterator it1,it2,itx;

    // set some values:
    for (int i=1; i<10; ++i) mylist.push_back(10*i);

    // 10 20 30 40 50 60 70 80 90
    it1 = it2 = mylist.begin(); // ^^
    advance (it2,6);            // ^                 ^
    ++it1;                      //    ^              ^

    it1 = mylist.erase (it1);   // 10 30 40 50 60 70 80 90
    //    ^           ^

    it2 = mylist.erase (it2);   // 10 30 40 50 60 80 90
    //    ^           ^

    ++it1;                      //       ^        ^
    --it2;                      //       ^     ^

    mylist.erase (it1,it2);     // 10 30 60 80 90

    cout << "\nmylist contains:";
    for (itx=mylist.begin(); itx!=mylist.end(); ++itx)
        cout << ' ' << *itx;
    cout << '\n';

    // NOTE: it1 still points to 40, and 60 is not deleted
    cout << endl << *it1 << "\t" << *it2 <<endl;

    // This will print an unexpected value
    it1++;
    cout << *it1;

    cout << "\nmylist now contains:";
    for (it1=mylist.begin(); it1!=mylist.end(); ++it1)
        cout << ' ' << *it1;
    cout << '\n';

    /*
  =======
   HEAPS
  =======
  */

  // Creates a max heap
    priority_queue <int> pq;

    // To create a min heap instead, just uncomment the below line
    // priority_queue <int, vector<int>, greater<int> > pq;

    pq.push(5);
    pq.push(1);
    pq.push(10);
    pq.push(30);
    pq.push(20);

    // Extracting items from the heap
    while (!pq.empty())
    {
        cout << pq.top() << " ";
        pq.pop();
    }


    // creating heap from user defined objects
    // Let's initialize the properties of `Person` object first
    p1.name = "Linus Torvalds";
    p1.age = 47;

    p2.name = "Elon Musk";
    p2.age = 46;

    p3.name = "Me!";
    p3.age = 19;

    // Initialize a min heap
    
    // Note: We defined a comparator is_older in the beginning to
    // compare the ages of two people.
    
    priority_queue <struct Person, vector<struct Person>, is_older> mh;
    mh.push(p1);
    mh.push(p2);
    mh.push(p3);

    // Extracting items from the heap
    while (!mh.empty())
    {
    	struct Person p = mh.top();
        cout << p.name << " ";
        mh.pop();
    }

    /*
  =========
   SORTING
  =========
  */

    // The following list type initialization is only supported in versions after C++11
    //vector<int> int_vec = {56, 32, -43, 23, 12, 93, 132, -154};

    // If the above style of initialization doesn't work, use the following one
    static int arr[] = {56, 32, -43, 23, 12, 93, 132, -154};
    int arr_len = sizeof(arr) / sizeof(arr[0]);
    vector <int> int_vec(arr, arr + arr_len);

    cout << endl;
    // Default: sort ascending
    // sort(int_vec.begin(), int_vec.end());
    // To sort in descending order:
    // Do not include the () when you call wayToSort
    // It must be passed as a function pointer or function object
  sort(int_vec.begin(), int_vec.end(), way_to_sort);
    for (vector <int>::iterator i = int_vec.begin(); i!=int_vec.end(); i++)
        cout << *i << " ";
    cout << endl;

    // sorting the array
    sort(arr, arr + arr_len);
    for (int i=0; i < arr_len; i++) {
    	cout << arr[i] << " ";
    }

    // Sorting user-defined objects
    static struct Person persons[] = {p1, p2, p3};
    sort(persons, persons+3, compare_names);

    // This will print out the names in alphabetical order
    for (int i=0; i < 3; i++) {
    	cout << persons[i].name << " ";
    }

  return 0;
}

Hope you found this helpful

I've also created a gist for the above cheatsheet. Feel free to fork, suggest changes, or point out bugs!