All Cpp STL Data Structures in One Go!

datastructures.cpp

#include <iostream> // cout

#include <vector> // Dynamic Array 
#include <list> // Doubly Linked List
#include <deque> // Double Ended Queue (Circular Buffer)
#include <queue> // FIFO Queue, and Max Heap (Priority Queue)
#include <stack> // LIFO Stack                               
#include <set> // Ordered Set (BST - Red/Black)              
#include <map> // Ordered Map (BST - Red/Black)              
#include <unordered_set> // Hash Set                         
#include <unordered_map> // Hash Map                         
#include <multiset> // Ordered Set allow duplicate keys (BST)
#include <multimap> // Ordered map allow duplicate keys (BST)
#include <unordered_multiset> // UnOrdered Set allow duplicate keys (BST)
#include <unordered_multimap> // UnOrdered map allow duplicate keys (BST)

#include <utility> // pair, make_pair

#include <algorithm> // Sort, Binary Search, Shuffle
#include <random>                                   

using namespace std;

auto r = default_random_engine {};

int main ()
{          
  /////////////
  // Array ////
  /////////////
  vector<int> A(5,0); // 5 elements, all 0  

  vector<int> B = {1,3,5,7,9}; // 5 elements, initialized here

  vector<int> array; // Empty

  // Update A to be all Even numbers (0,2,4,6,8)
  for (int a=0;a<A.size();++a)                  
    A[a] = 2*a; // O(1) access                  

  // Merge A and B into array
  for (int a=0,b=0,i=0;i<10;++i)
    if (i % 2)                  
      array.push_back(B[b++]); // O(1) insertion at tail
    else                                                
      array.push_back(A[a++]);                          

  
  for (auto& el : array) cout << el << " "; cout << endl; // Print array

  shuffle(array.begin(),array.end(),r); // Randomize elements

  for (auto& el : array) cout << el << " "; cout << endl; // Print array

  sort(array.begin(),array.end()); // Sort array from smallest to biggest

  for (auto& el : array) cout << el << " "; cout << endl; // Print array

  bool z = binary_search(array.begin(),array.end(),4); // Does array contain 4?

  ///////////////////
  // Linked List ////
  ///////////////////
  list<int> linkedList;

  for (int i=0;i<array.size();++i)
    if (i % 2)                    
      linkedList.push_back(array[i]); // O(1) insertion at tail
    else                                                       
      linkedList.push_front(array[i]); // O(1) insertion at head

  for (auto& el : linkedList) cout << el << " "; cout << endl; // Print linkedList

  linkedList.pop_front(); // O(1) deletion at head
  linkedList.pop_back(); // O(1) deletion at tail 

  for (auto& el : linkedList) cout << el << " "; cout << endl; // Print linkedList

  // Key drawback is that you don't have random access to any offset
                                                                    
  //////////////////////////                                        
  // Double Ended Queue ////                                        
  //////////////////////////                                        
  deque<int> dequeue;                                               

  // Get remaining elements from LinkedList
  while (!linkedList.empty())              
  {                                        
    dequeue.push_back(linkedList.front()); // O(1) insertion at tail
    dequeue.push_front(linkedList.back()); // O(1) insertion at tail
    linkedList.pop_front();                                         
    linkedList.pop_back();                                          
  }                                                                 

  for (auto& el : dequeue) cout << el << " "; cout << endl; // Print dequeue

  cout << dequeue[3] << endl; // Random access to dequeue, because its an array underneath

  cout << dequeue.front() << endl; // Access front
  cout << dequeue.back() << endl; // Access back  

  sort(dequeue.begin(),dequeue.end());

  /////////////
  // Queue ////
  /////////////
  queue<int> fifo;

  while (!dequeue.empty())
  {                       
    fifo.push(dequeue.front());
    dequeue.pop_front();       
  }                            

  while (!fifo.empty())
  {                    
    cout << "Popping: " << fifo.front() << endl;
    fifo.pop();                                 
  }                                             

  ////////////////
  // Max Heap ////
  ////////////////
  priority_queue<int> maxHeap;
                              
  for (int i=0;i<10;++i)      
  {                           
    maxHeap.push(i); // O(log(n)) insertion, such that max element is always at top
    cout << "Max Element: " << maxHeap.top() << endl;                              
  }                                                                                
                                                                                   
  //while (!maxHeap.empty())                                                       
  //{                                                                              
  //  cout << "Max Element: " << maxHeap.top() << endl; // O(1) access to max element
  //  maxHeap.pop(); // O(log(n)) deletion (re-heapify)                              
  //}                                                                                

  /////////////
  // Stack ////
  /////////////
  stack<int> lifo;

  while (!maxHeap.empty())
  {                       
    lifo.push(maxHeap.top());
    maxHeap.pop();           
  }                          
                             
  while (!lifo.empty())      
  {                          
    cout << "Popping: " << lifo.top() << endl;
    lifo.pop();                               
  }                                           

  ///////////
  // Set ////
  ///////////
  set<int> bst;
               
  // Make BST contain only even numbers
  for (int i=0;i<5;++i)                
    bst.insert(2*i); // O(log(n)) insertion

  for (auto it=bst.begin();it!=bst.end();++it)
    cout << *it << " ";                       
  cout << endl;                               

  if (bst.find(4) != bst.end()) // O(log(n)) search
    cout << "Found 4!" << endl;                    

  if (bst.find(3) == bst.end()) // O(log(n)) search
    cout << "Can't find 3!" << endl;               

  ///////////
  // Map ////
  ///////////
  map<int,char> bstMap {{1,'a'},{3,'b'},{5,'c'}};

  bstMap[5] = 'z'; // O(log(n)) access
                                      
  for (auto it=bstMap.begin();it!=bstMap.end();++it)
    cout << "Key: " << it->first << " Val: " << it->second << endl;

  bstMap.erase(5); // O(log(n)) delete // Delete by key

  bstMap.erase(bstMap.begin()); // Delete via iterator

  for (auto it=bstMap.begin();it!=bstMap.end();++it)
    cout << "Key: " << it->first << " Val: " << it->second << endl;

  ////////////////
  // Hash Set ////
  ////////////////
  unordered_set<int> hashSet;
                             
  // Make hashSet contain only even numbers
  for (int i=0;i<5;++i)                    
    hashSet.insert(2*i); // O(1) insertion 

  for (auto it=hashSet.begin();it!=hashSet.end();++it)
    cout << *it << " ";                               
  cout << endl;                                       

  if (hashSet.find(4) != hashSet.end()) // O(1) search
    cout << "Found 4!" << endl;                       

  if (hashSet.find(3) == hashSet.end()) // O(1) search
    cout << "Can't find 3!" << endl;                  

  ////////////////
  // Hash Map ////
  ////////////////
  map<int,char> hashMap {{1,'a'},{3,'b'},{5,'c'}};

  hashMap[5] = 'z'; // O(1) access

  hashMap[100] = 'k'; // O(1) insertion

  hashMap.insert(make_pair(55,'h')); // O(1) insertion

  for (auto it=hashMap.begin();it!=hashMap.end();++it)
    cout << "Key: " << it->first << " Val: " << it->second << endl;

  hashMap.erase(5); // O(1) delete // Delete by key

  hashMap.erase(hashMap.begin()); // Delete via iterator

  for (auto it=hashMap.begin();it!=hashMap.end();++it)
    cout << "Key: " << it->first << " Val: " << it->second << endl;

  if (hashMap.find(55) != hashMap.end()) // O(1) search
    cout << "Found key 55: " << hashMap[55] << endl;

  // TODO
  // - multiset
  // - multimap
  // - unordered_multiset
  // - unordered_multimap
  return 0;
  
}