---
# System prepended metadata

title: C++ Learning
tags: [C++]

---

# 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()``` 刪除特定位置

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

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

    ```cpp
    b.insert(b.begin(),element); //在開頭加入element
    ```
## **Vector傳參**
```cpp
void function ( vector <int> &vector_name ) { //& → 更動匯入參數的內容
    //do something
}
```
## **Map**
>作為hash table的容器  
>key和value可以是任何一種資料型態
```cpp
//初始化
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()```也是用來判斷元素是存在,但回傳的是指向其儲存位址的指標









&nbsp;

# Algorithms 

## LIS基礎演算法

1. 時間複雜度:O(n<sup>2</sup>)
2. Code:

```cpp
#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:

```cpp
#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

```cpp
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. 求最大公因數

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