{%hackmd @hipp0\Hippotumuxthem %}
<style>
.text-center{
text-align: center; //文字置中
}
.text-left{
text-align: left; //文字靠左
}
.text-right{
text-align: right; //文字靠右
}
</style>
<style>
.reveal .slides {
text-align: left;
font-size:30px;
}
</style>
# 基礎資料結構
---
## STL
----
STL(Standard Template Library)是C++的一個標準函式庫，用來提供許多常用得資料結構。他提供了許多類似陣列和鏈結串列的容器
- vector
- list
- deque(雙端佇列)
以及用於操作這些容器的算法
- sort
- find
- remove
---
- pair
- vector
- stack
- queue
- set
- map
---
# Pair
----
簡單來說就是將整個物件包起來形成一個pair
Ex:
- 若一個函式想要回傳兩個物件也可以用pair
----
```cpp=
#include<iostream>
using namespace std;
int main(){
pair<int, string> tp;
tp = {1, "aaaa"};
cout << tp.first << " " << tp.second;
}
```
----
```cpp=
#include<iostream>
using namespace std;
int main(){
pair<int, string> tp1(1, "aaaaa");
pair<int, string> tp2;
tp2 = tp1;
cout << tp2.first << " " << tp2.second;
}
```
----
## make_pair(a,b)
```cpp=
#include<iostream>
using namespace std;
pair<int, string> test(int a, string b){
return make_pair(a, b);
// return {a,b};
}
int main(){
pair<int, string> tp1 = test(1, "aaaaa");
cout<< tp1.first << " " << tp1.second;
}
```
----
## auto
```cpp=
#include<iostream>
using namespace std;
pair<int, string> test(int a, string b){
return make_pair(a, b);
}
int main(){
auto tp1 = test(1, "aaaaa");
cout<< tp1.first << " " << tp1.second;
}
```
----
```cpp=
#include<iostream>
#include<vectort>
using namespace std;
int main(){
vector<int> v = {1, 2, 3, 5, 8, 9};
for(auto n : v) cout << n << "\n"
}
```
---
# Vector
----
vector是STL的一種容器
- 以陣列的方式來存儲一系列的物件
- 支持動態的元素增加和刪除操作
- 可以在執行期間改變他的大小
- 傳統的陣列，一旦宣告就不能改變大小
- 是一種模板類別，可以使用任何類型的物件來創建vector實例。
----
下面是一個vector的使用範例:
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main(){
//宣告
vector<int> numbers;
//在vector末尾添加元素
numbers.push_back(1);
numbers.push_back(2);
numbers.push_back(3);
numbers.push_back(4);
numbers.pop_back();
//遍歷vector中的元素
for(int i = 0; i < numbers.size(); i ++){
cout << numbers[i] << " ";
}
cout << endl;
}
```
----
- push_back()
- 是vector中的一個函式，可以將元素加到vector的末端
- 類似Python的list.append()
- pop_back()
- 清除vector末端的元素
- insert()
- 在指定位置插入元素
- vec.begin()
- vec.end()
----
取得長度的用法
- **vec.empty()** -若vector內部為空，則傳回true
- **vec.size()** -取得目前vector持有的元素個數
- **vec.resize()** -改變vector目前持有的元素個數
- **vec.clear()** -清除vector裡面的元素
----
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> numbers(3);
numbers[0] = 1;
numbers[1] = 2;
numbers[2] = 3;
for(int i = 0; i < numbers.size(); i++){
cout << numbers[i] << " ";
}
cout << endl;
}
```
----
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> v = {1, 3, 5, 6, 8, 4, 2};
while(!v.empty()){
int x = v.back();
v.pop_back();
cout << x << '\n';
}
}
```
----
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> v = {1, 2, 3, 4, 5, 6, 7};
v.insert(v.begin(), 10);
v.insert(v.end(), 88);
v.insert(v.begin() + 3, 50);
for(int i = 0; i < v.size(); i++) cout << ' ' << v[i];
cout << '\n';
}
```
----
```cpp=
vector<int> numbers1(20, 3); //建構一20個大的陣列，每個元素都是3
vector<int> numbers2 = {1, 2, 3, 4, 5}; //建構一個5個大的陣列，元素分別是1, 2, 3, 4, 5
```
----
```cpp=
vector<int> numbers1 = {1, 2, 3};
vector<int> numbers2 = numbers1;
```
----
```cpp=
numbers1.resize(10) //將number1的大小重新設為10
```
----
## sort
可以將陣列裡的元素由大到小或由小到大進行排序
```cpp=
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
vector<int> v = {2, 3, 6, 1, 5, 7, 2};
sort(v.begin(), v.end()); //由小到大
for(int i = 0; i < v.size(); i++){
cout << v[i] << "\n";
}
sort(v.begin(), v.end(), greater<int>()); //由大到小
for(int i = 0; i < v.size(); i++){
cout << v[i] << "\n";
}
sort(v.begin(), v.end(), less<int>()); //由小到大
for(int i = 0; i < v.size(); i++){
cout << v[i] << "\n";
}
}
```
----
## iterator
可以對容器中的元素進行遍歷(vector, map...)
```cpp=
#include <iostream>
#include<vector>
using namespace std;
int main(){
vector<int> v = {1, 2, 3, 4, 5};
for(vector<int>::iterator it = v.begin(); it != v.end(); it++) cout << *it << '\n';
```
----
```cpp=
#include<vector>
#include<iostream>
#include<string>
using namespace std;
pair<string, int> test(string a, int b){
return make_pair(a, b);
}
int main(){
vector<pair<string, int>> vp;
vp.push_back(test("aa", 1111));
vp.push_back(test("ab", 2222));
for(auto it = vp.begin(); it != vp.end(); it++){
cout << it->first << " " << it->second << '\n';
}
}
```
----
## D001
## D002
---
# stack
----
Stack是一種後進先出的資料結構(LIFO, Last In First Out)
$\quad\quad\quad\quad\quad\quad$
----
```cpp=
#include <iostream>
#include <stack> // 引入堆疊
int main() {
std::stack<int> myStack;
for (int i = 0; i < 5; ++i) {
myStack.push(i);
}
std::cout << "Top: " << myStack.top() << std::endl;
myStack.pop();
std::cout << "Top: " << myStack.top() << std::endl;
return 0;
}
```
----
## 取得堆疊內元素個數
```cpp=
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> myStack;
for (int i = 0; i < 5; ++i) {
myStack.push(i);
}
cout << "Count: " << myStack.size() << "\n";
}
```
----
## 檢查堆疊內是否有元素(是否為空)
```cpp=
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> sage;
for (int i = 0; i < 5; ++i) {
sage.push(i);
}
if (sage.empty()) {
cout << "色即是空" << endl;
}
else{
cout << "不知道有什麼諧音反正不是空的" << endl;
}
}
```
---
# Queue
----
queue是一種先進先出的資料結構(FIFO, First In First Out)
$\quad\quad\quad\quad\quad\quad$
----
```cpp=
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<int> q;
for(int i = 0; i < 3; i++){
q.push(i);
}
cout << q.front() << endl;
cout << q.back() << endl;
cout << q.size() << endl;
int size = q.size();
for (int i = 0; i < size; i++) {
cout << q.front() << " ";
q.pop();
}
cout << "\n";
}
```
----
```cpp=
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<int> q;
for(int i = 0; i < 3; i++){
q.push(i);
}
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
}
cout << "\n";
}
```
----
## D003
## D004
---
# Tree
$\quad\quad\quad\quad\quad\quad$
----
#### Tree結構
- 每個節點會接0~多個其他節點
- Root會指向第一個節點
- 花額外空間紀錄子節點的位置
- 沒有接其他節點的稱作descendant
- Descendant指向nullptr
- 最多兩個節點的稱作二元樹
- 樹裡面沒有環路(cycle)
----
----
#### Tree性質
- 不重複經過節點
- 樹的高度 :
- 不重複經過節點的路徑中最長的稱作為高度
- 二元搜尋樹
- 左邊子節點小於父節點
- 右邊子節點大於父節點
---
# Set
----
### set
- 屬於tree結構
- 只有內容值沒有鍵值
- 不會出現相同的元素
----
```cpp=
#include <iostream>
#include <set>
using namespace std;
int main(){
set<int> s = {2, 2, 3, 3, 5, 7, 6, 5, 9, 7, 6};
for(int n : s){
cout << n << '\n';
}
}
```
----
也可以使用vector來初始化
```cpp=
#include<set>
#include<vector>
#include<iostream>
using namespace std;
int main(){
vector<int> v = {1, 2, 3, 4, 5, 5};
set<int> s = {v.begin(), v.end()};
for(auto n : s){
cout << n << '\n';
}
}
```
----
```cpp=
#include<set>
#include<vector>
#include<iostream>
using namespace std;
int main(){
set<int> s;
s.insert(1);
s.insert(6);
s.insert(7);
s.insert(4);
s.insert(7);
s.insert(5);
for(auto n : s){
cout << n << '\n';
}
}
```
----
```cpp=
#include<bits/stdc++.h>
using namespace std;
pair<int, string> mp(int a, string b){
return make_pair(a, b);
}
int main(){
set<pair<int, string>> s;
s.insert(mp(2, "a"));
s.insert(mp(3, "b"));
s.insert(mp(1, "c"));
s.insert(mp(5, "w"));
for(auto n : s){
cout << n.first << " " << n.second << "\n";
}
}
```
---
# Map
----
### map
- 屬於tree結構
- 有鍵值跟內容值
- map的鍵值可以不是數字
- 鍵值跟內容值成對，用pair儲存
- 鍵值不能更改
----
```cpp=
#include <iostream>
#include <map>
using namespace std;
int main(){
map<int, string> mp;
mp[0] = 'a';
mp[1] = 'b';
mp[2] = 'c';
for(int i = 0; i < 3; i++){
cout << mp[i] << '\n';
}
}
```
----
```cpp=
#include<iostream>
#include<map>
using namespace std;
int main(){
map<string, double> mp;
mp["Gojo"] = 2.5;
mp["Tsukumo"] = 49.5;
for(auto it = mp.begin(); it != mp.end(); it++){
cout << (*it).first << " " << (*it).second << '\n';
}
}
```
----
也可以使用pair
```cpp=
#include <iostream>
#include <map>
using namespace std;
int main(){
map<string, double> mp;
mp["Gojo"] = 2.5;
mp["Tsukumo"] = 49.5;
for(pair<string, double> p : mp){
cout << p.first << " " << p.second << '\n';
}
}
```
----
```cpp=
#include<iostream>
#include<map>
using namespace std;
int main(){
map<string, double> mp = {{"Gojo", 2.5},
{"Tsukumo", 49.5},
{"A", 10},
{"b", 23}};
mp.erase("Tsukumo");
mp.insert(pari<string, double>("Cc", 44));
for(auto u : mp){
cout << u.first << " " << u.second << "\n";
}
}
```
----
```cpp=
#include <iostream>
#include <map>
using namespace std;
int main ()
{
map<char,int> mymap;
map<char,int>::iterator it;
mymap['a']=50;
mymap['b']=100;
mymap['c']=150;
mymap['d']=200;
it = mymap.find('b');
if (it != mymap.end())
mymap.erase(it);
// print content:
cout << "elements in mymap:" << '\n';
cout << "a => " << mymap.find('a')->second << '\n';
cout << "c => " << mymap.find('c')->second << '\n';
cout << "d => " << mymap.find('d')->second << '\n';
}
```
----
## D005
## D006
{"title":"基礎資料結構STL","description":"#基礎資料結構","contributors":"[{\"id\":\"d5b90de4-9b8e-4a36-a782-226db16cf725\",\"add\":14403,\"del\":4161},{\"id\":\"b4bc52a4-04a8-4c6d-920a-32b9ab31a7f9\",\"add\":20,\"del\":0}]"}