owned this note
owned this note
Published
Linked with GitHub
# STL Containers
[**學長講義**](/HOKVWduUTAebgFDHA6ggCw)
---
## 容器
### Construct
```cpp=
//vector
vector<int> vec1;
vector<int> vec2(10);
vector<int> vec3 = {1, 2, 3};
vector<int> vec4(5, 1); //1 1 1 1 1
vector<int> vec5(vec3);
vector<int> vec6(vec3.begin(), vec3.end());
```
```cpp=
//deque一樣
deque<int> dq1;
deque<int> dq2(10);
deque<int> dq3 = {1, 2, 3};
deque<int> dq4(5, 1); //1 1 1 1 1
deque<int> dq5(dq3);
deque<int> dq6(dq3.begin(), dq3.end());
```
```cpp=
//stack
stack<int> stk1;
stack<int> stk2(stk1);
//queue
queue<int> qu1;
queue<int> qu2(qu1);
```
---
## set實作
### 初始化
```cpp=
set<int> s1;
set<int> s2 = {1, 2, 3, 4, 5};
```
```cpp=
set<int> s = {1. 3};
s.insert(2);
s.insert(5);
s.insert(4);
s.insert(3);
s.insert(4);
```
礙於 `set` 內鍵值不重複，且會自動排序
所以 `set` 內的值會是 `1, 2, 3, 4 ,5`
---
## map實作
### Construct
雖然本身 `key-value` 是用 `pair` 構成
但在建構時不須打 `pair`
ex:
```cpp=
map<string, int> mp;
```
### 插入與初始化
#### 初始化
```cpp=
map<string, int> mp = {
{"apple", 10},
{"egg", 1000},
{"banana", 1},
{"cherry", 5}
};
```
#### 插入
`map` 的 `key` 在插入時不需要已經存在
並且修改不存在 `key` 的 `value` 也會使他被插入 `map` 中
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main() {
map<string, int> mp;
mp["apple"] += 10;
mp["egg"] = 1000;
mp.insert(pair<string, int>("banana", 1));
mp.insert(make_pair("cherry", 5));
}
```
:::info
:::spoiler map的遍歷輸出
因為 `map` 並不像其他容器有流水號般的下標
所以有兩種簡單的方式可以輸出 `map`
1. 使用迭代器並加入指標概念
```cpp=
int main () {
map<int, int> mp = {
{1, 7},
{0, 2},
{3, 3},
{5, 0}
};
for(auto i = mp.begin(); i < mp.end(); i++)
cout << i -> first << ' ' << i -> second << '\n';
}
```
2. 使用下方補充的範圍型for
```cpp=
int main () {
map<int, int> mp = {
{1, 7},
{0, 2},
{3, 3},
{5, 0}
};
for(auto i : mp)
cout << i.first << ' ' << i.second << '\n';
}
```
:::
---
## vector複製map
```cpp=
map<int, int> mp;
vector<pair<int, int>> vec(mp.begin(), mp.end());
```
---
## .empty()
判斷是否為空
常見用法:
```cpp=
while(!stk.empty()) {
//code
sk.pop();
}
```
或是
```cpp=
if(stk.empty()) {
//code
break;
}
```
---
## 其他
1. STL 容器的理論上限容量與系統位元數有關
例如 32 位元系統即是 $32^2 - 1$
但有些編譯器或操作系統會限制容器的 `max_size`
就需要透過某些方式改變
2. `map` 的 `key` 與 `value` 不必受限於都存取 `int`
可以讓 `key` 值變成 `pair` ，就可以搜索類似直角坐標系等等
ex:
```cpp=
map<pair<int, int>, int> mp;
mp[{1, 0}]++;
mp[{5, 1}]++;
mp[{3, 2}]++;
```
---
## 補充：容器基底
某些容器是其他容器為基底包裝而成的
像是
* `stack` 是由 `deque` 製作
* `queue` 是由 `deque` 製作
* `priority_queue` 是由 `vector` 製作
這樣就可以理解為甚麼用 `stack` 直接複製 `vector` 會爛
而用 `deque` 卻不會
而要改變容器基底也很簡單
ex:
```cpp=
stack<int, vector<int>> stk(vec3);
```
但有兩點要注意
1. 改變容器會影響使用時的效率與時間複雜度
2. 如果基底不能使用原本容器的功能
在用的話會爛
例如: `queue<int, vector<int>> q;`
在使用 `pop` 的時候會出現錯誤
因為 `vector` 沒有 `pop_front` 功能
---
## 補充：range-base for loop
一般我們要遍歷一個容器，比如 `vector` ，我們會這樣寫
```cpp=
vector<int> vec = {1, 2, 3, 4, 5};
for(int i = 0; i < vec.size(); i++)
cout << vec[i] << ' ';
```
但當我們有迭代器的概念後，可以變成這樣
```cpp=
vector<int> vec = {1, 2, 3, 4, 5};
for(auto i = vec.begin(); i < vec.end(); i++)
cout << *i << ' ';
```
但今天介紹的範圍型 `for` 是基於被迭代容器的更進階寫法 <span style=color:rgb(190,190,190)>((懶人寫法</span>
**上 code**
```cpp=
vector<int> vec = {1, 2, 3, 4, 5};
for(auto i : vec)
cout << i << ' ';
```
其中的 `i` 並不是迭代器，他會根據 `vec` 所含元素的型態做改變
並且 `i` 是全新的變數，對 `i` 值做改變不會影響 `vec`
`auto` 完全只是方便 <span style=color:rgb(190,190,190)>(懶)</span>
若有需要可以這樣寫
```cpp=
//確定被迭代容器內的型態
for(int i : vec)
cout << i << ' ';
//想直接改變 vec
for(auto &i : vec)
i++;
//完全不想改動
for(const auto i : vec)
cout << i << ' ';
```
:::spoiler 二維vector輸出
```cpp=
vector<vector<int>> vec = {
{1, 3, 5},
{2, 6, 4, 9},
{3, 4, 1, 2}
};
for(auto &row : vec) {
for(auto &i : row)
cout << i << ' ';
cout << '\n';
}
```
:::
Google Drive
Gist
Clipboard
Sign in with Wallet
