資料結構：電腦儲存資料的方式，例如陣列。
Vector 向量
- 可以動態改變大小的陣列。
- 【筆記】C++ Vector
vector<int> v = {1, 2, 3};
v.push_back(4);
v.pop_back();
vector<int> v2 = v; //複製整份
vector<int> v3(v.begin()+1, v.end()-1); //複製指定範圍{2}
int a[3] = {1, 2, 3};
vector<int> v5(a, a+3); //陣列轉vector
vector<int> v6(a+1, a+2); //也可以複製指定範圍{2}Stack 堆疊
- 疊盤子，後進先出。
Queue 佇列
- 排隊，先進先出。
Deque 雙端佇列
- 念作 “deck”。
- stack+queue=deque.
Linked List 連接串列
- 對每個資料紀錄前後資料的位置。
- 可以 O(1) 加入、刪除特定資料。
- 不能 O(1) 存取指定 index 的資料。
pair
pair：只有兩個參數的 struct。
#include <utility>
pair<int, int> p;
p = make_pair(5, 3);
p = {5, 3};
cout << p.first << ' ' << p.second;Heap 堆積
- 一個能維護極值(最大值)的資料結構。
- 功能：存取、刪除 heap 最頂端(極值)的資料。
- 複雜度：O(log N)
- STL提供的 heap 叫做 priority_queue。
- Binary Heap Tree
#include <queue>
priority_queue<int> heap;Set 集合
- Set = 集合 = 元素不重複
- 有排序的。
- 可以插入(insert)、刪除(erase)、尋找(find)資料。
- set.count(87) 回傳該元素是否存在。
- 可以利用 prev() , next() 得到前後的 iterator。
- 尋找值大於等於自己的第一個 iterator：set.lower_bound(87);
- 尋找值大於自己的第一個 iterator：set.upper_bound(87);
- Disjoint Set 併查集：詢問兩元素是否在同一集合、合併兩個元素所在的集合。
for(set<int>::iterator i=s.begin(); i!=s.end(); i++){
cout << *i << endl;
}Map
- 一個 key 對到一個 value，key 不可重複，value 可以重複。
- Map 會自動按照 key 排序。
// 宣告
map<string, int> m;
// 插入
m.insert(make_pair("Apple", 3));
m["Banana"] = 5;
// 遍歷
for(auto pair : m){
cout << pair.first << ' ' << pair.second << endl;
}
// 刪除
m.erase("Banana");
// 尋找
auto it = m.find("Banana");
if(it != m.end()){
cout << it->second << endl;
}else{
cout << "Not found.\n";
}