owned this note   changed 10 months ago  
Published Linked with GitHub

基礎資料結構

STL

STL(Standard Template Library)是C++的一個標準函式庫，用來提供許多常用得資料結構。他提供了許多類似陣列和鏈結串列的容器

  • vector
  • list
  • deque(雙端佇列)

以及用於操作這些容器的算法

  • sort
  • find
  • remove
  • pair
  • vector
  • stack
  • queue
  • set
  • map

Pair

簡單來說就是將整個物件包起來形成一個pair
Ex:

  • 若一個函式想要回傳兩個物件也可以用pair









#include<iostream>

using namespace std;

int main(){
    pair<int, string> tp;
    tp = {1, "aaaa"};
    cout << tp.first << " " << tp.second;
}











#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)














#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













#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;
}









#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的使用範例:





















#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裡面的元素

















#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;
}














#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';
	}
}














#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';
}



vector<int> numbers1(20, 3); //建構一20個大的陣列，每個元素都是3
vector<int> numbers2 = {1, 2, 3, 4, 5}; //建構一個5個大的陣列，元素分別是1, 2, 3, 4, 5



vector<int> numbers1 = {1, 2, 3};
vector<int> numbers2 = numbers1;

numbers1.resize(10) //將number1的大小重新設為10

sort

可以將陣列裡的元素由大到小或由小到大進行排序
























#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…)









#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';



















#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\)



















#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;
}

取得堆疊內元素個數














#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";

}

檢查堆疊內是否有元素(是否為空)


















#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\)























#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";
}

















#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結構
  • 只有內容值沒有鍵值
  • 不會出現相同的元素










#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來初始化













#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';
    }
}



















#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';
    }
}



















#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儲存
    • 鍵值不能更改














#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';
    }
}















#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
















#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';
    }
}

















#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";
    }
}

























#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

Select a repo