###### tags: `社團事務`
# 🗝 進階 C++ STL 迭代器
我們在之前的課程中介紹了基本功。
但是在實際上，若想要繼續走程式這條路，基本功實在遠遠不夠，接下來的學習大多是靠著自學方式進行，下的努力越多，收穫就會越多，加油！
**STL ( Standard Template Library ) 迭代器** 主要由 3 種東西構成：
1. **迭代器** ( Iterator )
使用者可以利用其逐一存取、宣告、使用 Container 中元素，常見的有 **begin()**、**end()** 等等
| index | 0 | 1 | 2 | 3 |
| -------- | -------- | -------- |-------- | -------- |
| interator | begin()+0 | begin()+1| begin()+2 | begin()+size()|
| interator | end()-size() | end()-3| end()-2 | end()-1|
2. **容器** ( Container )
這個講義裡面的超級重點，配合迭代器及演算法讓你搖身一變變電神。
:::info
**應該注意**：大部分的容器都具有**通性**( common methods )，需要特別注意喔
:::
1. **演算法** ( Algorithm )
在團戰裡面的超強輔助的概念，有很多小功能用得好的話可以省下一堆時間，這裡面的功能有很多都是以前需要思考很久才寫出來的。
學習起來困難重重ㄏ，但是學起來就可以用的得心應手。
覺得**英文很難不想看資料？** 覺得**學不會想放棄？** 你們已經撐到這裡了，**半途而廢絕對不是一個好選擇**，認真、努力、勤練才是學習的捷徑喔！
## 🧬 前置處理器
以下介紹的東西，都是在編譯的預處理階段完成的，這部分的東西不會被編譯成機械語言，通常只會涉及代換的內容。
+ **#define**
定義，它可以將之後程式出現之變數全部帶換成某值
格式為：
```cpp
#define 識別名稱 字串
```
例如：
```cpp
#define PI 3.14159
```
+ **include**
除了 include 內建的標頭檔外，也可以 include 自己撰寫的標頭檔，例如：
```cpp
#include "test.h"
#include <iostream>
```
則會在main.cpp下的目錄找到 test.h 並將它 include 進去。
## 🥏 algorithm 函式庫
**[參考網站](http://www.cplusplus.com/reference/algorithm/)**
**algorithm 函式庫** 是現代化 C++ 的代表之一，這裡扮演一個銜接初階與進階的一個踏板，裡面包含一些很厲害的功能，這裡來舉例一些很好用的函式ㄅ
+ **max** / **min** 最大最小值
在 **參數_1** 和 **參數_2** 選最大最小值
在 **參數_1** 和 **參數_2 前一個位址** 之範圍內選最大最小值
```cpp
max(1,2); // 回傳 2
min('a','z'); // 回傳 a
int num[] = {3,7,2,5,6,4,9};
*max_element(num,num + 7); // 回傳 9
*min_element(num,num + 7); // 回傳 2
// 這 2 個函式的參數和回傳值都是位址，所以需要配合指標使用
```
+ **swap** 置換 2 數
置換 **參數_1** 和 **參數_2**
```cpp
int arr[] = { 3,7,2,5,6,4,9 };
swap(arr[0],arr[1]); // 3,7 -> 7,3
float a = 0.314;
float b = 3.14;
swap(a,b); // 0.314,3.14 -> 3.14,0.314
```
+ **sort** 整理數列
從 **參數_1** 到 **參數_2前一個位址** 作排序
```cpp
int arr[] = { 3,7,2,5,6,4,9 };
sort( begin(arr), begin(arr)+3);
// (2 3 7) 5 6 4 9
sort( begin(arr)+4, end(arr));
// 2 3 7 5 (4 6 9)
sort( arr, arr+7);
// 2 3 4 5 6 7 9
```
+ **copy** 複製數列
從 **參數_1** 到 **參數_2前一個位址** 作複製
```cpp
int arr[] = { 3,7,2,5,6,4,9 };
vector<int> a(7) ;
copy(begin(arr)+4, end(arr),a.begin());
// n = {6 4 9 0 0 0 0}
copy(begin(arr), end(arr),a.begin());
// n = {3 7 2 5 6 4 9}
```
+ **reverse** 翻轉數列
從 **參數_1** 到 **參數_2前一個位址** 作翻轉
```cpp
int arr[] = { 3,7,2,5,6,4,9 };
reverse(begin(arr)+4, end(arr));
// arr[] = {3 7 2 5 9 4 6}
reverse(begin(arr), end(arr))
// arr[] = {6 4 9 5 2 7 3}
```
+ **find** 尋找某值
從 **參數_1** 到 **參數_2前一個位址** 作尋找
```cpp
int myints[] = { 10, 20, 30, 40 };
int * p;
p = find (myints, myints+4, 30);
if (p != myints+4) // 注意這裡的判斷句
cout << "Element found in myints: " << *p << '\n';
else
cout << "Element not found in myints\n";
vector<int> myvector (myints,myints+4);
vector<int>::iterator it;
it = find (myvector.begin(), myvector.end(), 30);
if (it != myvector.end())
cout << "Element found in myvector: " << *it << '\n';
else
cout << "Element not found in myvector\n";
```
+ **count** 計算次數
從 **參數_1** 到 **參數_2前一個位址** 作計算出現次數
```cpp
int myints[] = {10,20,30,30,20,10,10,20};
int mycount = count (myints, myints+8, 10); // 計算出現次數
cout << "10 appears " << mycount << " times.\n";
```
## 🥥 Container 容器
### 種類
STL容器的類型大致上可以分為這幾類，應用上可以簡略區分彼此
+ **序列式容器** ( Sequence containers )
- 陣列 **Array**
- 向量 **Vector**
- 串列 **List**
- 雙端佇列 **Deque**
+ **容器配接器** ( Sequence containers )
- 堆疊 **Stack**
- 佇列 **Queue**
+ **關聯性容器** ( Associative containers )
- 集合 **Set**
- 可重複集合 **Multiset**
- 映射 **Map**
- 可重複映射 **Multimap**
+ **無排序關聯性容器** (Unordered associative containers)
- 無排序集合 **Unordered_set**
- 無排序可重複集合 **Unordered_multiset**
- 無排序映射 **Unordered_map**
- 無排序可重複映射 **Unordered_multimap**
### 通性
在 STL 中容器大多具有下列函式之功能，在這邊先說，後面就不一一贅述ㄌ
+ **迭代器 Iterator**
1. **begin()**：指向首端之 iterator
2. **end()**：指向尾端之 iterator 的**下一個位置**
3. 其他
- 反向迭代器：**rbegin**、**rend**
- 常數迭代器：**cbegin**、**cend**
- 常數反向迭代器：**crbegin**、**crend**
*註： **rbegin** 是 指向尾端元素*，***rend** 是 指向首端元素的前一個位置*
+ **大小 Capacity**
1. **size()**：容器內有多少元素
2. **empty()**：是否已經清空所有元素
+ **接口 Access**
1. **front()**：回傳開口端元素值
2. **back()**：回傳最尾端元素值
+ **功能 Modifier**
1. **clear()**：清空容器
2. **insert()**：插入元素到指定位置，其餘位置順延
3. **erase()**：消除指定位置的元素
### 介面
## 🎠 stack 堆疊
**stack** 是一種先進後出 ( **FILO** ) 的容器。
就像將書疊起來，**先放下** 的書要將 **後放下** 的書 **移走後才能拿**。
+ 圖示
### 函式
+ empty
+ size
+ top
+ push
+ pop
+ swap
## 🎭 queue 佇列
**queue** 是一種先進先出 ( **FIFO** ) 的容器。
就像排隊，**先排入** 的人可以比 **後排入** 的人 **先離開**。
+ 圖示
### 函式
+ empty
+ size
+ front
+ push
+ pop
+ swap
## 🎏 vector 向量
**vector** 是一種可以動態使用的陣列，相較於 C-style Array 更為常用。基本上寫 c++ 很建議使用 vector 取代低階的 array 和 pointer，比較易維護、容易除錯、活動度很高等等
**這些是使用 vector 的特點**：
:::info
1. 支援隨機存取
1. 尾端增刪元素很快 : O(1)
1. 中間增刪元素比較費時 : O(n)
:::
### 宣告
+ 一般宣告
```cpp
#include <vector> ;
// vector<資料型態> <陣列名稱>;
vector<int> a;
// vector<float> <陣列名稱> = {初始值_1, 初始值_2, ...};
vector<float> b = {1.14, 2.14, 3.14};
vector<int> c(5);
// 建立大小為 5 的 vector，且預設值為 0
vector<int> c(5,1);
// 建立大小為 5 的 vector，且預設值為 1
```
*註：``vector<int> a[10]`` 是指宣告出 10 個 int 型態的 vector*
+ 引數型宣告
```cpp
#include <vector> ;
vector<int> a = {1,2,3,4,5,6};
// 完全複製 a 之內容到 b
vector<int> b = a;
vector<int> b(a);
// 特定範圍
vector<int> vec( v1.begin(), v1.end() ) // vec = {1,2,3,4,5,6}
vector<int> vec( v1.begin()+1, v1.end()-1 ) // vec = {2,3,4,5}
```
*註：vec 中特定範圍宣告之第二參數為該參數**前一位置***
+ 二維宣告：
```cpp
vector<vector<int>> a;
// 建立空的二維 vector ： a
vector<vector<int>> b(10,vector<int>(10));
// 建立 10 * 10 之二維 vector ： b
a.resize(10, vector<int>(10));
// 將 a 變成 10*10 方陣，且原本的值不會被取代，但超過範圍的值會被抹去
```
+ 鏈結型二維宣告
```cpp
vector<int> ivec[10];
```
這行就會像這張圖顯示的一樣宣告，因為 vector 的 templete 特性，所以可以當作一個動態鏈結串列使用。
若是在之後加上這幾行：
```cpp
vector<int> ivec[10];
ivec[0].push_back(10);
ivec[0].push_back(20);
.
.
.
```
就會像這張圖顯示的一樣，可以變成一組**長短不一**的二維鏈結串列
這裡附上[參考資料](https://ramihaha.tw/c-program-container-vector-array-linklist/)，可以試著理解看看，這實在非常好用。
### 遍歷
**遍歷**( travel )，聽起來很難的名詞，其實就是全部順一次的意思，這邊介紹幾種方法以供選擇。
- **索引遍歷**
```cpp
vector<int> v = {0, 1, 2, 3, 4};
for (int i = 0; i < v.size(); i++)
cout << v[i] << '\n';
```
- **迭代器遍歷**
```cpp
vector<int> v = {0, 1, 2, 3, 4};
// auto == vector<int>::iterator;
for (auto itr = v.begin(); itr < v.end(); itr++)
cout << *itr << '\n';
```
- **auto + Range-based loop 遍歷**
詳情可以參閱[這裡](https://docs.microsoft.com/zh-tw/cpp/cpp/range-based-for-statement-cpp?view=vs-2019)
總之這裡的用法是真的很重要，大家要特別注意
```cpp
vector<int> v = {0, 1, 2, 3, 4};
// int 不推薦
for(int i : v)
cout << i << ' ';
// auto 不受歡迎，無法改變 i 值
for (auto i : v)
cout << i << ' ';
// auto& 較推薦
for (auto &i : v) // 非萬能像是遇到 bool 會掛掉
cout << i << ' ';
for (auto &&i : v) // 這樣就可以解決了
cout << i << ' ';
// const auto&，只能讀值，同樣不能改值
for (const auto &i : v)
cout << i << ' ';
```
### 函式
+ **增加元素**
我不知道怎麼形容這裡的重要，總之這邊絕對要會，這邊學會後學其他的就會很得心應手
- **push_back()**
```cpp
vector<int> a ;
a.push_back(1); // a = {1}
a.push_back(2); // a = {1,2}
a.push_back(3); // a = {1,2,3}
int i = 0;
a.push_back(i); // a = {1,2,3,0}
int b[]={1,2,3};
a.push_back(b[0]); // a= {1,2,3,0,1}
```
- **insert()**
```cpp
vector<int> a={0,2,4,6};
a.insert(a.begin()+1,1); // 0,1,2,4,6
a.insert(a.begin()+3,3); // 0,1,2,3,4,6
a.insert(a.begin()+5,5); // 0,1,2,3,4,5,6
// 特定範圍
// insert(目的地,複製地首位址,複製地尾位址後一格)
int num[]={7,8,9};
a.insert(a.end(),num.begin(),num.end()); // 0,1,2,3,4,5,6,7,8,9
```
:::warning
**特別注意**：另外有 ***emplace()*** 和 ***emplace_back()*** 的用法，有興趣可以了解一下。
:::
+ **刪除元素**
有增加就有刪除，兩個同等重要，加油 o(〃＾▽＾〃)o
- **pop_back()**
```cpp
vector<int> a = {1,2,3};
a.pop_back(); // a = {1,2}
a.pop_back(); // a = {1}
```
- **erase()**
```cpp
vector<int> a = {1,2,3,4,5,6,7,8,9};
a.erase(a.begin()+1); // a = {1,3,4,5,6,7,8,9}
a.erase(a.begin()+2); // a = {1,3,5,6,7,8,9}
a.erase(a.begin()+3); // a = {1,3,5,7,8,9}
// 特定範圍
a.erase( a.end()-3 , a.end() ); // a = {1,3,5}
```
+ **其他**
- **assign()**
```cpp
vector<int> a = { 0,2,4,6 };
int num[] = { 7,8,9 };
a.assign(begin(num), end(num)); // a = 7,8,9
```
*註：使用 **assign()** 將會取代原有元素，需特別注意*
- **swap()**
```cpp
vector<int> a(3,100);
vector<int> b(5,200);
swap(a,b);
// a = 200 200 200 200 200
// b = 100 100 100
```
### 函式間傳遞
其實很多人即使對 vector 有初步的認知，卻會不知道 vector 在自己寫的函式中傳遞應該怎麼寫，這邊來為各位解惑。
大致分成這幾種：
1. 傳值型
這麼做會讓整個 vec 的構造重新拷貝一次，不符合效益，**完全不建議使用**。
> 宣告：void 函式名( vector< int> a )
> 呼叫：deal( vec )
2. **傳遞引用型**
老實說，傳引用的函式不僅不會重新拷貝，函式寫的方式跟上面一模一樣。
因此，**絕對推薦大家使用引用傳遞**
> void 函式名( vector< int>& a )
> deal( vec )
> void 函式名( const vector< int>& a )
> deal( vec )
3. **傳遞指標型**
其實這個講起來挺複雜，應用起來不會那麼直觀，可以看完 map 之後再來了解
> void 函式名( vector< int>* a )
> void 函式名( const vector< int>* a )
> deal( &vec )
> deal( &vec )
範例：
```cpp=
#include <iostream>
#include <vector>
using namespace std;
void func(vector<int> &vect)
{
vect.push_back(30);
}
int main()
{
vector<int> vect;
vect.push_back(10);
vect.push_back(20);
func(vect);
for (int i=0; i<vect.size(); i++)
cout << vect[i] << " ";
return 0;
}
```
## 🛒 set 集合
**set** 是數學意義上的集合，你可以按照數學邏輯與程式相互搭配。
而 **set** 分成下列幾種，這些的應用各不相同，在上方 **容器** 那篇已經介紹過了，這邊就大概簡略使用與搭配：
1. **set**：有排序、不含重複元素之集合
3. **multiset** ：有排序、含重複元素之集合
3. **unordered set**：無排序、不含重複元素之集合
5. **unordered multiset**：無排序、含重複元素之集合
可是 set 的使用上需注意效率問題，一般會搭配演算法使用。
### 宣告
+ 一般宣告
**set** 系列
```cpp
#include <set>
set<int> a;
multiset<int> b;
// multiset 包括在 set 函式庫中
```
**unordered_set** 系列
```cpp
#include <unordered_set>
unordered_set<int> c;
unordered_multiset<int> d;
// unordered_multiset 包括在 unordered_set 函式庫中
```
+ 引數宣告
```cpp
int myints[] = {75,23,65,42,13};
// 特定範圍
set<int> myset (myints,myints+5);
```
*註：set 中特定範圍為宣告之第二參數為該參數前一位置*
### 遍歷
遍歷在 set 之中非常重要，畢竟身為一個集合，應用上就會需要去遍歷過所有元素。
而且與 vector 相比，較為不直觀，總之大家加油！
+ **迭代器遍歷**
大眾上比較常使用的版本，因為判斷條件較明顯
```cpp
for (auto it=myset.begin(); it != myset.end(); ++it)
cout << ' ' << *it;
// std::set<int>::iterator it = auto it
```
+ **auto + Range-based loop 遍歷**
```cpp
for(auto i : a)
cout<< i << ' ';
for(auto& i : a)
cout<< i << ' ';
// set 裡都是不允許改值的，必竟性質不同
// 所以這 2 種基本上在 set 的遍歷上代表意義一樣，只要遍歷即可
```
### 函式
+ 增加、刪除元素
- **insert()** 插入元素
```cpp
set<int> myset;
// 定值插入
myset.insert(10); // 10
int num = 10;
myset.insert(num*10); // 10 100
// 範圍插入
int a[]={5269,64,1978};
myset.insert(myints, myints + 3); // 10 64 100 1978 5269
// 引數插入
pair< set<int>::iterator, bool> ret;
// pair(迭代器 ,是否存在 )
ret = myset.insert(20); // no new element inserted
if (ret.second == false)
it = ret.first; // "it" now points to element 20
myset.insert(it, 25); // max efficiency inserting
myset.insert(it, 24); // max efficiency inserting
myset.insert(it, 26); // no max efficiency inserting
```
*註：其中 **特定範圍** 之範圍為 第一參數 到 插入的第二個該參數**前一位置***
*註：**引數插入** 為最高效率之方法，會使用到 pair 的觀念，mpa 那邊會有介紹*
:::warning
**特別注意**：另外有 ***emplace()*** 和 ***emplace_hint()*** 的用法，有興趣可以了解一下。
:::
- **erase()** 刪除元素
```cpp
set<int> myset;
for (int i=1; i<10; i++)
myset.insert(i*10); // 10 20 30 40 50 60 70 80 90
// 定值刪除
myset.erase (40);
// 引數刪除
it = myset.begin();
++it; // "it" points now to 20
myset.erase (it);
// 範圍刪除
it = myset.find (60);
myset.erase (it, myset.end());
```
*註：其中 **特定範圍** 之範圍為 第一參數 到 插入的第二個該參數**前一位置***
+ 查找、計算元素
- **count()** 計算元素出現次數
```cpp
int a[]={10,73,12,22,73,73,12};
multiset<int> num (a, a+7);
cout << a.count(73); // 輸出：3，因為 73 出現 3 次
```
**值得注意**：在 **set** 中使用 **count()** 不是 1 就是 0，可以利用此性質檢查是否含有某元素
- **find()** 尋找某值
```cpp
int a[]={10,20,30,40,50,60,70,80,90};
set<int> num(begin(a), end(a));
auot it = find(20); // 回傳 20 之所在迭代器
// it 之後也可以應用
num.erase(it);
```
**值得注意**：假如是 multi系列的只會回傳第一個找到的位址喔
+ 其他
- **swap** 交換元素
寫法是 ``a.swap(b)`` 而不是 ``swap(a,b)`` 喔
```cpp
int num_1[] = { 1,2,3,4 };
int num_2[] = { 5,6,7,8 };
set<int> a(num_1, num_1+size(num_1));
set<int> b(begin(num_2),end(num_2));
a.swap(b);
// a = 5 6 7 8
// b = 1 2 3 4
```
- **upper_bound**、**lower_bound** 值的上下限
***lower_bound*** 會回傳第一個 **不小於** 某值之迭代器，
***upper_bound*** 則會回傳第一個 **大於** 某值之迭代器
```cpp
int num[]={1,2,5,8,11};
set<int> a(num, num + 5);
auto itlow = a.lower_bound(6); // itlow 指向 8
itlow = a.lower_bound(5) // itlow 指向 5
auto itup = a.upper_bound(9); // itup 指向 11
itup = a.upper_bound(8) // itup 指向 11
```
- **equal_range** 值的範圍
可以把他想成是 lower_bound 跟 upper_bound 的組合
而回傳值為 **pair** 型態，
**pair.first** = lower_bound 回傳值
**pair.second** = upper_bound 回傳值
```cpp
int num[] = { 10,20,30,30,30,40,50,60 };
multiset<int> a(num, end(num));
auto itrange = a.equal_range(30);
cout << *itrange.first << ' ' << *itrange.second << endl;
// 輸出 30 40
a.erase(itrange.first, itrange.second);
for (auto i : a)
cout << i<<' ';
// 輸出 10 20 40 50 60
```
+ 數學上集合應用( **algorithm** )
這邊是集合在數學上的主要功能，但是是寫在 **algotithm** 函式庫裡，參數也有點多，又會用到 **iterator** 函式庫的 **inserter** 函式。所以記得加上標頭檔喲。
總之也點麻煩 o(TヘTo)
``set_集合運算(a.a.begin(),a.end(),
b.begin(),b.end(),
inserter(c,c.begin()))``
也就相當於 c = a 集合運算 b
- **set_union** 聯集
```cpp
#include <algorithm>
#include <iterator>
set<int> a;
set<int> b;
.
// a = 5 10 15 20 25
// b = 10 20 30 40 50
set<int> result;
set_union(a.begin(),a.end(),
b.begin(),b.end(),
inserter(result,rusult.begin()))
// result = 5 10 15 20 25 30 40 50
```
- **set_intersection** 交集
```cpp
#include <algorithm>
#include <iterator>
set<int> a;
set<int> b;
.
// a = 5 10 15 20 25
// b = 10 20 30 40 50
set<int> result;
set_intersection(a.begin(),a.end(),
b.begin(),b.end(),
inserter(result,rusult.begin()))
// result = 10 20
```
- **set_difference()** 差集
```cpp
#include <algorithm>
#include <iterator>
set<int> a;
set<int> b;
.
// a = 5 10 15 20 25
// b = 10 20 30 40 50
set<int> result;
set_difference(a.begin(),a.end(),
b.begin(),b.end(),
inserter(result,rusult.begin()))
// result = 5 15 25
```
- **set_symmetric_difference** 聯集 - 差集
```cpp
#include <algorithm>
#include <iterator>
set<int> a;
set<int> b;
.
// a = 5 10 15 20 25
// b = 10 20 30 40 50
set<int> result;
set_symmetric_difference(a.begin(),a.end(),
b.begin(),b.end(),
inserter(result,rusult.begin()))
// result = 5 15 25 30 40 50
```
*註：其實以上介紹之功能也能運用在 **vector** 或 **tree** 上，但是要先 **sort** 喔*
:::warning
**iterator函式庫**
這裡面也是充滿了怪物函示呢 (笑
其中 **prev**、**next**、 **inserer** 都是較常使用的函式喔，詳請參考[這邊](http://www.cplusplus.com/reference/iterator/)
:::
### 函式間傳遞
## 💥 map 映射
Sign in with Wallet
Connect another wallet