Full C++ STL #1

#include <bits/stdc++.h>

using namespace std;

int main(){

    // pairs: for maintaing relation b/w two values.

    // a class in stl helps in storing two data type at same time.

    pair<int,string> p;

    p = {2, "tejas"};

    p = make_pair(2,"udit");

    p.first = 100;

    p.second = "srivastava";

    // array of PAIRS:

    pair<int,int> p_array[3];

    p_array[0] = {1,2};

    p_array[1] = {3,4};

    p_array[2] = {5,6};

    // VECTORS: dynamic sized arrays.

    vector<int> v;

    for(int i=0;i<4;i++) v.push_back(i);

    for(int i=0;i<4;i++){

        int x;

        cin >> x;

        v.push_back(x);         //O(1)

    }

    v.pop_back();           //O(1)

    vector<int> v2 = v;     //copy O(N)

    // NOTE: always use & for vectors for reducing TC.

    // in case of arrays, a1 = a gives a reference pointer. i.e. changes in a1 reflects in a but in vectors this makes a copy of v.

    // T.C. of push_back(x), pop_back(), v.size() = O(1)

    // array of vectors

    vector<int> v[10];      //make 10 vectors of zero size.

    v = {{1,2}, {3,4,5}, {9,6,4,3}};

    // to make dynamic size of array of vectors we use vector of vectors.

    // v[10] incdicates rows = fixed = 10, cols = vary. rows = vary = vector<vector>.

    

    

    // ITERATORS:

    /* An iterator is an object (like a pointer) 

    that points to an element inside the container. */

    // in some containers like maps, they are not index based so we have to use iterators to perform functions on it.

    vector<int> v;

    vector<int> :: iterator it;

    //(*it) --> value

    vectro<pair<int,int>> :: iterator itp;

    // (*it) --> a pair. access .first or .second

    // it->first or it->second for a pair.

    

    // (*it).first <=> it->first

    it = v.begin() => points first element.

    it = v.end() => points next to last element.

    value of it = (*it) --> v[0];

    value of it = (*(it+1)) --> v[1];

    value of it = (*(it+2)) --> v[2];

    // for loop with iterator:

    for(it=v.begin();it!=v.end();++it) cout << (*it) ;

    // diff between ++it/it++ and it+=1:

    // it++ or ++it moves the iterator to next iterator 

    // it+1 moves to next location.

    // so in case of containers like vectors i.e. continious both works fine.

    // but for non continious like maps next location can be null hence we should use it++/++it.

    // range based loops iterators:

    vector<int> v = {2,3,5,8,1,9};

    for(auto value:v) cout << value << " ";

    // here auto: data type of v

    // auto = int, pair<int,int> etc.

    // copied values.

    // MAPS:

    // stores pairs ({key value}) joined with some links. it++.

    // stores in sorted ordered based on KEYS. 

    // lexiographical for strings.

    map<int,string> mpp;

    mpp[key] = value;

    mpp[2] = "two";     // O(logN)

    mpp[9] = "nine";

    mpp.insert({5, "five"});

    mpp[6];     // O(logN) --> default value = 0

    //operations:

    size = m.size();

    m[key] = value;     //updation + insertion

    auto it = m.find(key);

    // O(logN): returns m.end() if not found 

    // else returns value.

    m.erase(it); // O(logN)

    // erases the pair corresponding to it

    if(it!=m.end()) m.erase(it); --> good way

    m.clear() --> clear all

    for(auto &mVal: mpp){

        cout << mVal.first << mVal.second;

        // O(N) 

        /*why not O(N*logN) because with the 

        address through iterator accesing values

        is O(1) whereas normally it is logN.*/   

    }

    

    //string case in maps:

    m["abcds"] = "efhfottk"; // O(s.size()* logN)

    1. updation/insertion: m[key] = value --> O(logN)

    2. find: auto it = m.find(key) --> O(logN)

    3. erase: m.erase(it) -->O(logN)

    4. forloop: val.first --> O(N)

    5. strings: m[str] = str --> O(s.size * logN)

    // unordered maps:

    // normal maps use trees for their internal implementation, whereas this unMaps use hashtables.

    // difference:

    // 1. Time complexity: O(1) -- avg case

    // 2. Valid datatypes: datatypes whose hash are defined. all primitive datatypes. But not complex and abstract.

    // 3. Inbuilt implementation: Hash table based.

    // 4. they give non sorted order.

    unordered_map<int,int> m;

    1. updation/insertion: m[key] = value --> O(1)

    2. find: auto it = m.find(key) --> O(1)

    3. erase: m.erase(it) -->O(1)

    4. forloop: val.first --> O(N)

    5. strings: m[str] = str --> O(s.size * 1)

    // ** for multimaps: use map<int, vector<value>> instead. It will store multiple values for a single key in on go.

    map<int,vector<int>> m;

    m[0] = {1,2,3,4,5};

    for(auto x:m){

        for(auto z:x.second) cout << z;

    }

     map<int,vector<int>> m;

    // m[2] = {1,2,3,4,5,6};

    

    for(int i=0;i<2;i++){

        vector<int> temp;

        for(int i=0;i<4;i++){

            int x;

            cout << "Value daal: ";

            cin >> x;

            temp.push_back(x);

        }

        m[i] = temp;

    }

    

    

      for(auto x:m){

        vector<int> temp = x.second;

        cout << "Value for " << x.first << endl;

        for(auto z:temp) cout << z << " ";

        cout << endl;

        temp.clear();

    }

    return 0;

}