# C++ Learning

###### tags: `C++`

## **STL container**

- Vector
> .push_back(element)
> .begin()
> .back()
- Queue
> FIFO(先進先出, 排隊)
> .push(element)
> .pop()
> .front()
> .back()
- Stack
> FILO(後進先出, 疊盤子)
> .push(element)
> .pop()
> .top()
- Set
> .insert(element)
> .erase(element)
> .count(element)

## **Vector更動元素**

+ ```.erase()``` 刪除特定位置

    b.erase(b.begin()+3); //刪除第三個元素(b[2])
    b.erase(b.begin()+3,b.begin()+6); //刪除第三到第六個元素

+ ```.insert()``` 新增至特定位置

    b.insert(b.begin(),element); //在開頭加入element

## **Vector傳參**

void function ( vector <int> &vector_name ) { //& → 更動匯入參數的內容
    //do something
}

## **Map**
>作為hash table的容器
>key和value可以是任何一種資料型態

//初始化
map<string , int > map_name //以string為key 以int為value

//遍歷
for (const auto &element : map_name)
{
    cout<<map_name.second<<"\n"; 
    //map_name.first → key
    //map_name.second → value
}

## **set , multiset**

1. STL容器
2. ```.insert()```插入元素
3. ```set```會自動消除重複元素, ```multiset```會保留
4. 元素插入後會自動排序
5. ```.clear()```初始化
6. ```.earse()```刪除指定元素
7. ```.count()```判斷元素是否存在,回傳 0 or 1
8. ```.find()```也是用來判斷元素是存在,但回傳的是指向其儲存位址的指標

 

# Algorithms

## LIS基礎演算法

1. 時間複雜度:O(n²)
2. Code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int i, j, k;
    vector<pair<int, int>> a;
    map<int, int> b;
    while (cin >> k)
    {
        a.push_back(make_pair(k, 1));
        for (i = 0; i < a.size(); i++)
        {
            for (j = 0; j <= i; j++)
            {
                if (a[i] > a[j])
                {
                    a[i].second = max(a[i].second, a[j].second + 1);
                }
            }
            b[a[i].second] = a[i].first;
        }
    }
    cout << b.size() << "\n"
         << "-"
         << "\n";
    for (auto l : b)
    {
        cout << l.second << "\n";
    }
}

## LIS進階演算法(只求長度)

1. 時間複雜度:O(n_log_n)
2. DP, Greedy, Binary search
3. Code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,d,i;
    vector<long int>b,c;
    while(cin>>a){b.push_back(a);}
    for(i=1;i<b.size();i++)
    {
        if(c.empty() or b[i]>c.back())  c.push_back(b[i]);      //置入
        else {  *lower_bound(c.begin(),c.end(),b[i])=b[i];    } //取代
    }
    cout<<c.size()<<"\n"<<"-"<<"\n";
}

## Binary Search

int binary_search(vector<int>v,int target) //find the position 
{
    int left=0;
    int right=v.size()-1;
    while(right=>left)
    {
        int mid=(right+left)/2;
        if(target==v[mid])  return left; //最後的解 left下界 right上界
        if(target>v[mid])   left=mid+1;
        else    // target<v[mid] 
            right=mid-1;
    }
    return -1;//fail
}

## 輾轉相除法

1. 求最大公因數

    while(b!=0 and c!=0)
    {
        if(b>=c)
            b=b%c;
        else
            c=c%b;
    }
    //最大公因數為max(b,c)