Structures

//*****************DATA STRUCTURES***************//

//***Vector
//
//**Popular methods
//
//push_back()               0(1) = constant
//[] brackets operator      0(1) = constant
//size()                    0(1) = constant

void Vector()
{
    vector<int> v;                  //v{}
    cout << v.size() << "\n";       //output 0
    v.push_back(20);            //v = {20}
    v.push_back(10);            //v = {20,10}
    v.push_back(10);            //v = {20,10, 10}
    cout << v[1];                   //output 10
    cout << v.size();               //output 3
};


//***Set
//
//**Popular methods
//
//insert()              0(logn)
//find()                0(logn)
//size()                0(1) = constant

#include <set>
using std::set;
void Set()
{
    set<int> s;                                 //s{}
    cout << s.size();                           //outputs 0
    s.insert(20);                               //s = {20}
    s.insert(10);                               //s = {10, 20}
    s.insert(10);                               //s = {10, 20}
    auto it = s.find(10);                       //it is an iterator that points to 10
    cout << (it != s.end() ? " FOUND" : " ");   //outputs FOUND
    cout << s.size();                           //output 2
}


//***Unordered Set
//
//**Popular methods
//
//insert()              0(1)
//find()                0(1)
//size()                0(1) = constant


#include <unordered_set>
using std::unordered_set;
void UnorderedSet()
{
    unordered_set<int> s;                           //s{}
    cout << s.size();                               //outputs 0
    s.insert(20);                               //s = {20}
    s.insert(10);                               //s = {10, 20}  //Could be in any order//
    s.insert(10);                               //s = {10, 20}
    auto it = s.find(10);                       //it is an iterator that points to 10
    cout << (it != s.end() ? " FOUND" : " ");       //outputs FOUND
    cout << s.size();                               //output 2
}


//***Map
//
//**Popular methods
//
//insert()                  0(logn) insert using make_pair
//find()                    0(logn) returns pair
//[] brackets operations    0(logn) returns ref to value
//size()                    0(1)

using std::map;
using std::make_pair;

void Map()
{
    map<int, int> m;                            //m={}
    cout << m.size();                           //outputs 0
    m.insert(make_pair(20, 1));                 //m={(20,1)}
    m.insert(make_pair(10, 1));                 //m={(10,1), (20,1)}
    m[10]++;                                    //m={(10,2), (20,1)}
    auto it = m.find(10);                   //it is an iterator that points to (10, 2)
    cout << (it != m.end() ? it->second : 0);   //outputs 2
    auto it2 = m.find(20);              //it is an iterator that points to (20, 1)
    cout << (it2 != m.end() ? it2->first : 0);  //outputs 20
    cout << m.size();                           //outputs 2
}


//***Unordered Map
//
//**Popular methods
//
//insert()                  0(1)    insert using make_pair
//find()                    0(1)    returns pair
//[] brackets operations    0(1)    returns ref to value
//size()                    0(1)

#include<unordered_map>
using std::unordered_map;
void UnorderedMap()
{
    unordered_map<int, int> m;                  //m={}
    cout << m.size();                           //outputs 0
    m.insert(make_pair(20, 1));                 //m={(20,1)}
    m.insert(make_pair(10, 1));                 //m={(10,1), (20,1)}    //Could in any order
    m[10]++;                                    //m={(10,2), (20,1)}
    auto it = m.find(10);                   //it is an iterator that points to (10, 2)
    cout << (it != m.end() ? it->second : 0);   //outputs 2
    auto it2 = m.find(20);              //it is an iterator that points to (20, 1)
    cout << (it2 != m.end() ? it2->first : 0);  //outputs 20
    cout << m.size();                           //outputs 2
}

//**************STACK
//          LIFO data structure
//**Popular methods
//
//push()            0(1)*  the star is because push complexity is acctually equivalent to the push_back on the line container
//pop()             0(1)
//top()             0(1)
//size()            0(1)

#include<stack>

using std::stack;

void Stack()
{
    stack<int> s;
    cout << s.size(); //Outputs 0
    s.push(1);
    s.push(2);
    cout << s.top(); //outputs 2
    s.pop();
    cout << s.top(); //outputs 1
    cout << s.size();//outputs 1
};

//**************QUEUE
//          FIFO data structure
//**Popular methods
//
//push()            0(1)*
//pop()             0(1)
//front()           0(1)
//size()            0(1)

#include <queue>
using std::queue;

void Queue()
{
    queue<int>q;
    cout << q.size();//0
    q.push(1);
    q.push(2);
    cout << q.front();//1
    q.pop();
    cout << q.front();//2
    cout << q.size();//1
};

//**************PRIORITY QUEUE
//Excentially a Heap
//
//**Popular methods
//
//push()            0(logn) When you call push you make 1 call to push_back(), 1 call to push_heap()
//pop()             0(logn) 1 call to pop_heap(), 1 call to pop_back()
//top()             0(1)
//size()            0(1)

#include <concurrent_priority_queue.h>
using std::priority_queue;

void PriorityQueue()
{
    priority_queue<int> pq;
    cout << pq.size();  //0
    pq.push(3);
    pq.push(1);
    pq.push(2);
    cout << pq.top();   //3
    pq.pop();
    cout << pq.top();   //2 - It shows the number by priority greater to lower.
    cout << pq.size();  //2
};


//***Multi Set
//
//**Popular methods
//
//insert()              0(logn)
//find()                0(logn)
//size()                0(1)

using std::multiset;

void MultiSet()
{
    multiset<int> ms;                               //s{}
    cout << ms.size();                              //outputs 0
    ms.insert(1);                               //s = {1}
    ms.insert(2);                               //s = {1, 2}
    ms.insert(1);                               //s = {1, 1, 2} //Auto sort order
    auto it = ms.find(1);
    cout << (it != ms.end() ? " FOUND" : " ");      //outputs FOUND
    cout << ms.size();                              //output 3
};

//***MultiMap
//
//**Popular methods
//
//insert()                  0(logn) insert using make_pair
//find()                    0(logn) returns pair
//size()                    0(1)
using std::multimap;
void MultiMap()
{
    multimap<int, int> mm;                  //m={}
    cout << mm.size();                      //outputs 0
    mm.insert({ 1,2 });                     //mm={(1,2)}
    mm.insert({ 2,4 });                     //mm={(1,2), (2,4)}
    mm.insert({ 1,3 });                     //mm={(1,2), (1,3), (2,4)}  //Auto sort order
    auto it = mm.find(2);
    cout << (it != mm.end() ? it->second : 0);  //outputs 4
    cout << mm.size();                          //outputs 3
}