# 資料結構
---
### 什麼是資料結構（Data Structure）?
----
資料結構是「組織資料的方式」，讓我們能更有效率地「儲存、查詢、修改、刪除」資料。
陣列就是其中一種。
---
## STL標準函式庫
### (Standard Template Library)
----
C++ 內建 (std 內) 的模板庫
有很多好用的資料結構
沒有的就需要手刻
----
#### 需要手刻 ：
1. BIT
2. Treap
3. Segment Tree
4. Sparse Table
...
----
不過這些都不在APCS的考試範圍所以不會教
今天只會教最基礎的
---
## 迭代器(iterator)
事先說明，詳細介紹在後面
----
### 甚麼是迭代(iteration)
「迭代」的核心概念是：
重複逐個存取資料結構中的每個元素，直到全部處理完畢
其實就是跑迴圈的意思
如下是一個最基本的迭代行為：
```cpp=
int a[] = {1, 2, 3, 4};
for (int i = 0; i < 4; i++) {
cout << a[i] << "\n";
}
```
----
而迭代器簡單來說就是指標的概念
用來指定某個元素(位址)
要取迭代器指的內容就加上取值運算子( * )
---
## pair
----
### 宣告
```cpp=
#include<utilit>
//std::pair<型別1, 型別2> 名稱;
std::pair<int, int> p;
std::pair<int, int> p(1, 2);
std::pair<int, int> p = {1, 2};
auto p = std::make_pair(1, 2);
```
一次存兩個元素的資料結構
----
### 操作
```cpp=
std::pair<int, int> p;
p.first = 1;
p.second = 2;
int a, b;
std::tie(a, b) = p;
// auto[a, b] = p;
// a=1, b=2
std::pair<int,int> q = {30,40};
std::swap(p, q); // 交換內容
```
----
### 比較大小
依字典序比較
也就是先比first，再比second
```cpp=
pair<int, int> p1(2, 3), p2(2, 4);
bool a = p1 < p2; // a = true
```
----
### 特殊用法
```cpp=
pair<pair<int, int>, int> p;
p.frist.first = 1;
p.first.second = 2;
p.second = 3;
```
----
## 補充
----
## tuple
(pair的多元素版本)
----
### 宣告
```cpp=
#include <tuple>
std::tuple<型別1, 型別2, ..., 型別N> 變數名稱;
std::tuple<int, int, int> t;
std::tuple<int, int, int> t(1, 2, 3);
std::tuple<int, int, int> t = {1, 2, 3};
auto t = std::make_tuple(4, 5, 6);
```
----
### 操作
```cpp=
std::tuple<int, int, int> t;
std::get<0> (t) = 4;
std::get<1> (t) = 5;
std::get<2> (t) = 6;
int a, b, c;
tie(a, b, c) = t;
// auto [a, b , c] = t;
// a = 4, b = 5, c = 6
```
更進階的用法請見chatGPT
----
### 比較
| | pair | tuple | struct |
|:-------- |:----:|:--------:|:--------:|
| 元素數量 | 2 | 任意數量 | 任意數量 |
| 成員名稱 | first, second | get<> | 自訂 |
---
## vector
動態陣列
----
### 宣告
```cpp=
#include<vector>
// std::vector<型別> 名稱;
vector<int> v;
vector<int> v(n); // 長度為n，元素初始值為0
vector<int> v(n, x); // 長度為n，所有元素初始值為x
vector<int> v2(v1); // 用v1複製一個新的vector
vector<int> v = {1, 2, 3, 4};
vector<vector<int>> v(n, vector<int>(m)); // 建立一個n*m的陣列
```
----
### 操作
```cpp=
vector<int> v;
v.push_back(x); // 將x加入尾端
v.insert(v.begin()+i, x); // 在第i個位置前插入x
v.insert(v.begin()+i, n, x); // 在第i個位置前插入n個x
v.pop_back(); // 刪除最後一個元
int val = v[i]; // 取出第i個元素
v[i] = x; // 修改第i個值為x
size_t n = v.size(); // 取得目前元素個數(v的大小)
bool a = v.empty(); // 是否為空(回傳true/flase)
v.clear(); // 清空
v.resize(n, x); // 改變長度為n，所有元素為x
int val = v.front() // 回傳遞一個元素
int val = v.back() // 回傳最後一個元素
v.erase(v.begin()+i); // 刪除第i個元素
v.erase(v.begin()+l, v.begin()+r); // 刪除[l, r)區間
reverse(v.begin(), v.end()); // 反轉順序
find(v.begin(), v.end(), x); // 查找x出現的第一個位置
v1.swap(v2); // 交換兩個vector的內容
```
----
### vector的迭代器
1. begin()
2. end()
3. rbegin()
4. rend()
----
----
----
### 迭代器宣告
```cpp=
vector<資料型態>::iterator 名稱; //begin(), end()
vector<資料型態>::reserve_iterator 名稱; //rbegin, rend()
```
通常都用auto
----
#### 示範
```cpp=
vector<int> v = {1, 2, 3, 4, 5};
auto it=v.begin();
auto rit=v.rbegin();
cout<<*it<<"\n"; //1
cout<<*rit<<"\n"; //5
//輸出v的全部元素
for (auto i=v.begin();i!=v.end();i++) cout<<*i<<" ";//法一
for (auto k:v) cout<<k<<" "; //法二
for (size_t i=0;i<v.size();i++) cout<<v[i]<<" "; //法三
```
---
## stack
堆疊
----
後進先出 (Last-In-First-Out, LIFO)
----
----
### 宣告
```cpp=
#include<stack>
// std::stack<型別> 名稱;
stack<int> stk;
```
----
### 操作
```cpp=
stack<int> stk;
stk.push(x); // 把元素 x 放入 stk
stk.pop(); // 移除最上層元素
int x = stk.top(); // 取最上層元素（不刪除）
bool a = stk.empty(); // stk 是否為空
size_t n = s.size(); // 回傳 stack 大小
```
(stack不支援迭代器)
----
~~沒用的資料型態~~
~~完全可以被vector取代~~
---
### list / forward_list
鏈結串列
----
list ： 雙向鏈結串列（doubly linked list）
forward_list ： 單向鏈結串（singly linked list）
----
### 宣告
```cpp=
#include <list>
std::list<型別> 名稱; // 空 list
std::list<型別> 名稱 = {a, b, c}; // 初始化 list
#include <forward_list>
std::forward_list<型別> 名稱; // 空 forward_list
std::forward_list<型別> 名稱 = {a, b, c}; // 初始化
```
----
### 操作
```cpp=
//共有操作
lis.push_front(x); // 在頭端插入元素
lis.pop_front(); // 刪除頭端元素
lis.sort(); // 排序
lis.reverse(); // 反轉
lis.unique(); // 刪除相鄰重複元素
lis.remove(x); // 刪除所有等於指定值的元素
lis.remove_if(); // 刪除所有符合條件的元素
// list獨有
list<int> lis;
lis.push_back(x); // 尾端插入元素
lst.pop_back(); // 刪除尾端元素
lst.insert(it, x); // 在指定迭代器位置前插入元素x
lst.erase(it); // 刪除指定迭代器元素
lst.merge(lst2); // 合併兩個已排序 list
int n = lst.size();// 取得元素個數
lst.splice(pos, list& other);
//將other整個list的元素搬到pos位置之前，other變成空的
lst.splice(pos, list& other, it);
//將other中的迭代器it指向的單個元素搬到pos前，other只減少這個元素
lst.splice(pos, list& other, first, last);
//將other中[first, last)範圍的元素搬到pos前，other中這些元素被移走
// forward_list獨有
forward_list<int> fl;
fl.insert_after(it, x); // 在指定迭代器"後方"插入元素x
fl.erase_after(it); // 刪除指定迭代器"後方"元素
fl.splice_after(pos, forward_list& other);
//將other的所有元素搬到pos"後面"，other變成空的
fl.splice_after(pos, forward_list& other, it);
//將other的單個元素搬到pos"後面"，other只減少這個元素
fl.splice_after(pos, forward_list& other, first, last);
//將other的[first, last)範圍元素搬到pos"後面"，other中這些元素被移走
```
(list支援迭代器)
---
## queue
單向佇列
----
單向佇列
先進先出 (First-In-First-Out, FIFO)
----
----
### 宣告
```cpp=
#include<queue>
//std::queue<型別> 名稱;
queue<int> q;
```
----
### 操作
```cpp=
queue<int> q;
q.push(x); // 將元素x加到q尾端
q.pop(); // 移除q頭端的元素
q.front(); // 取得q頭端元素（不移除）
q.back(); // 取得q尾端元素（不移除）
bool a = q.empty(); // q是否為空
size_t n = q.size(); // 回傳q內元素個數
```
(不支援迭代器)
---
## deque
雙向佇列
----
----
### 宣告
```cpp=
#include<deque>
//std::deque<型別> 名稱;
deque<int> dq;
```
----
### 操作
```cpp=
deque<int> dq;
dq.push_back(x);
dp.push_front(x);
dq.pop_back();
dq.pop_front();
int val = dq.back();
int val = dq.front();
size_t = dq.size();
bool a = dq.empty();
dq.insert(dq.begin()+i, x);
dq.erase(dq.begin()+i);
dq.clear();
```
----
### deque的迭代器
1. begin()
2. end()
3. rbegin()
4. rend()
---
## priority_queue
----
優先佇列
和queue很像
但會排序！
預設是取大的
通常用 __堆積(Heap)__ 來實作
----
----
### 宣告
```cpp=
//std::priority_queue<型別, 底層容器, 比較函式> 名稱;
#include<queue>
#include<vector>
#include<functional>
//預設(最大堆)
//std::priority_queue<型別, std::vector<型別>, std::less<型別>> 名稱;
pirority_queue<int> pq;
//最小堆
priority_queue<int, vector<int>, greater<int>> pq;
```
底層容器只能是支援隨機存取的序列容器
e.g. vector, deque
----
### 操作
```cpp=
priority_queue<int> pq;
pq.push(x);
pq.pop();
int val = pq.top();
bool a = pq.empty();
size_t = pq.size();
pq.swap(pq2);
```
----
## 補充
手刻比較函示
----
### 方法1
struct
```cpp=
include<bits/stdc++.h>
using namespace std;
struct cmp {
bool operator()(int a, int b) {
return a > b; // 表示 a 應該排在 b 後面(最小堆)
}
}
int main() {
priority_queue<int, vector<int>, cmp> pq;
pq.push(10);
pq.push(5);
pq.push(20);
while(!pq.empty()) {
cout << pq.top() << " "; // 5 10 20
pq.pop();
}
}
```
----
### 方法2
lambda
```cpp=
#include<bits/stdc++.h>
using namspace std;
int main() {
auto cmp = [](int a, int b) {return a > b; };
priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
pq.push(10);
pq.push(5);
pq.push(20);
while(!pq.empty()) {
cout << pq.top() << " "; // 5 10 20
pq.pop();
}
}
```
※ decltype (declare type)是用來
取得一個變數或表達式的｢型別」
---
## set / multiset / unordered_set
----
| 特性 | `set` | `multiset` | `unordered_set` |
|:--------------------:|:----------------:|:----------------:|:---------------:|
| 底層資料結構 | RB-tree | RB-tree | Hash table |
| 元素順序 | 自動排序 | 自動排序 | 無序 |
| 是否允許重複 | 否 | 是 | 否 |
| 插入、查找、刪除效率 | O(log n) | O(log n) | 平均 O(1) |
----
### 宣告
```cpp=
#include<set>
#include <unordered_set>
//std::set<型別, 比較函式(預設std::less<型別>)> 名稱;
//std::multiset<型別, 比較函式(預設std::less<型別>)> 名稱;
//std::unordered_set<型別, hash函式(預設std::hash<型別>), key_equal函式(預設std::equal_to<型別>)> 名稱;
set<int> s;
//大到小
set<int, greater<int>> s;
```
※ unordered_set 裡面的型別別亂放
std::hash和只支援一些基礎的型別
今天教的資料型態除了pair都不支援
如果你依舊想放的話就要自己寫hash函式
----
### 操作
```cpp=
set<int> s;
s.insert(x);
s.erase(x);
s.earse(s.begin()+i);
s.find(x);
s.size();
s.empty();
s.clear();
s.count(x);
unordered_set<int> set;
set.reserve(n); // 預留空間
```
(支援迭代器)
---
## map / multimap / unordered_map
----
set的pair版
跟函數很像$(x, f(x))$
就是鍵與值的概念
----
### 宣告
```cpp=
#include <map>
#include <unordered_map>
//std::map<鍵的型別, 值的型別, 比較函式(預設std::less<鍵的型別>)> 名稱;
//std::multimap<鍵的型別, 值的型別, 比較函式(預設std::less<鍵的型別>)> 名稱;
//std::unordered_map<鍵的型別, 值的型別, 哈希函式(預設std::hash<鍵型別>), 相等函式(預設std::equal_to<鍵型別>> 名稱;
map<int, int> mp;
map<int, int, greater<int>> mp;
```
----
### 操作
```cpp=
map<int, int> mp;
mp.insert({key, value}); // 插入元素(若key已存在則不覆蓋)
mp[key] = value; // 若key不存在則建立（multimap沒有這個）
mp.erase(key); // 刪除鍵為 key 的元素
mp.find(key); // 回傳指向該key的iterator
mp.count(key); // 傳該key出現次數
mp.clear(); // 清空整個容器
mp.empty(); // 檢查是否為空
mp.size(); // 目前元素數量
insert_or_assign(key, value); // 若存在就更新，不存在就插入(map專屬)
unordered_map<int, int> m;
m.reserve(N); // 預留空間
```
BTW
取出 key 需要用.first
取出 value 需要用.second
---
## 迭代器
----
### 宣告
```cpp=
container_type<資料型態>::iterator 變數名稱;
container_type<資料型態>::const_iterator 變數名稱;
container_type<資料型態>::reverse_iterator 變數名稱;
container_type<資料型態>::const_reverse_iterator 變數名稱;
```
----
### 迭代器函式
* begin() , cbegin()
* end(), cend()
* rbegin() , crbegin()
* rend() , crend()
迭代器加上了 c，表示 const 的意思
也就是這些迭代器不能修改，只能讀取
----
### 基本操作（所有迭代器都有）
| 操作 | 說明 |
|:-----------:|:--------------------------:|
| `*it` | 取得迭代器指向的元素值 |
| `it->` | 取得迭代器指向的元素的成員 |
| `++it` | 移動到下一個元素 |
| `it == it2` | 比較迭代器是否相等 |
----
### 實用函數
* `advance(it, n)` --
讓迭代器 it 向前移動 n (可負)個位置
* `distance(first, last)` --
計算兩個迭代器之間的距離（即元素個數）
* `next(it, n = 1)` --
不改變原迭代器，回傳「向後 n 個」的新迭代器。
* `prev(it, n = 1)` --
不改變原迭代器，回傳「向前 n 個」的新迭代器。
※ 往前的話不能是單向的迭代器
----
### 迭代器種類
分五種：
（能力是遞增的，越下面的能做的事越多）
1. Input Iterator（輸入迭代器）
2. Output Iterator（輸出迭代器）
3. Forward Iterators（前向迭代器）
4. Bidirectional Iterators（雙向迭代器）
5. Random Access Iterators（隨機存取迭代器）
----
｢輸入/輸出迭代器」最基本，分別只能讀或寫
支援的容器有 istream_iterator, ostream_iterator
----
｢前向迭代器」是輸入輸出迭代器的升級版，可多次遍歷
支援的容器有 unordered_map, unordered_set
----
｢雙向迭代器」在多了反向移動（–）能力
支援的容器有 list, map, set, multimap, multiset
----
｢隨機存取迭代器」可支援像陣列一樣的隨機存取，操作與指標最為相似，效率最高
支援的容器有 vector, deque, array, string
----
## 補充
~~這個我只是從GPT抄來的~~
~~所以不要問我 問了我也不會~~
----
### 迭代器適配器（Iterator Adaptors）
迭代器適配器是用來「包裝容器」，讓原本不能用迭代器輸入/輸出的操作變得可行。
它們是特殊的迭代器物件，用起來像一般迭代器，但行為不同（例如自動插入元素、從輸入流讀資料等）。
----
#### 一、輸入輸出流迭代器（Stream Iterators）
常與 std::copy 一起使用
```cpp=
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
/*
語法：
std::istream_iterator<T> it(輸入流);
std::ostream_iterator<T> it(輸出流, "分隔符");
*/
vector<int> v;
// 從輸入讀到 EOF
copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(v));
cout << "你輸入的數字是：";
copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
}
```
----
#### 二、插入迭代器（Insert Iterators）
這組讓 STL 演算法在執行「寫入」時
自動使用容器的 insert()、push_back() 或 push_front()
```cpp=
#include <vector>
#include <iterator>
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
/*
1. std::back_inserter(container)
適用：vector, deque, list
*/
vector<int> a = {1, 2, 3};
vector<int> b = {4, 5, 6};
// 自動 push_back
copy(b.begin(), b.end(), back_inserter(a));
for (int x : a) cout << x << " "; // 輸出：1 2 3 4 5 6
/*
2. std::front_inserter(container)
適用：list, deque
*/
list<int> c = {1, 2, 3};
list<int> d = {4, 5, 6};
// 插入前端
copy(c.begin(), c.end(), front_inserter(d));
for (int x : c) cout << x << " "; // 輸出：6 5 4 1 2 3
/*
3. std::inserter(container, pos)
適用：list, vector, set, map 等有 insert 函數的容器
*/
vector<int> e = {1, 2, 3};
vector<int> f = {9, 8, 7};
// 在第二個元素前插入
copy(f.begin(), f.end(), inserter(e, e.begin() + 1));
for (int x : e) cout << x << " "; // 輸出：1 9 8 7 2 3
}
```
---
## 題目
----
### pair
#### [Zerojudge n368](https://zerojudge.tw/ShowProblem?problemid=n368)
----
### vector
#### [MDCPP T014](http://mdcpp.mingdao.edu.tw/problem/T014)
#### [MDCPP B015](http://mdcpp.mingdao.edu.tw/problem/B015)
#### [Leetcode 1929](https://leetcode.com/problems/concatenation-of-array/description/)
----
### stack
#### [MDCPP B005](http://mdcpp.mingdao.edu.tw/problem/B005)
#### [MDCPP D055](http://mdcpp.mingdao.edu.tw/problem/D055)
#### [Zerojudge c123](https://zerojudge.tw/ShowProblem?problemid=c123)
#### [Zerojudge f698](https://zerojudge.tw/ShowProblem?problemid=f698)
#### [~~CSES Round Trip II~~](https://cses.fi/problemset/task/1678)
#### [~~Zerojudge 真假子圖 (回滾併查集)~~](https://zerojudge.tw/ShowProblem?problemid=g598)
----
### list
#### [Zerojudge b586](https://zerojudge.tw/ShowProblem?problemid=b586)
#### [Zerojudge i426](https://zerojudge.tw/ShowProblem?problemid=i426)
#### [Zerrojudge n371. 5](https://zerojudge.tw/ShowProblem?problemid=n371)
----
### queue
#### [MDCPP B002](http://mdcpp.mingdao.edu.tw/problem/B002)
#### [Leetcode 225](https://leetcode.com/problems/implement-stack-using-queues/description/)
----
### deque
#### [Zerojudge i400](https://zerojudge.tw/ShowProblem?problemid=i400)
#### [TIOJ 1618 . 城市景觀問題](https://tioj.ck.tp.edu.tw/problems/1618)
#### [TIOJ 1566 . 簡單易懂的現代都市](https://tioj.ck.tp.edu.tw/problems/1566)
#### [~~Leetcode Jump Game II(01BFS)~~](https://leetcode.com/problems/jump-game-ii/description/)
----
### priority_queue
#### [MDCPP AP013](http://mdcpp.mingdao.edu.tw/problem/AP013)
#### [Zerojudge d221](https://zerojudge.tw/ShowProblem?problemid=d221)
#### [CSES Stick Divisions (霍夫曼編碼)](https://cses.fi/problemset/task/1161/)
#### [~~CSES Investigation(dijkstra)~~](https://cses.fi/problemset/task/1202)
----
### set
#### [Zerojudge n369](https://zerojudge.tw/ShowProblem?problemid=n369)
#### [MDCPP T016](http://mdcpp.mingdao.edu.tw/problem/T016)
#### [CSES Movie Festival II (貪心)](https://cses.fi/problemset/task/1632)
----
### map
#### [Zerojudge b050](https://zerojudge.tw/ShowProblem?problemid=b050)
#### [Zerojudge d244](https://zerojudge.tw/ShowProblem?problemid=d244)
#### [CF Least Cost Bracket Sequence (反悔貪心)](https://codeforces.com/contest/3/problem/D)
#### [~~CSES Meet in the Middle~~](https://cses.fi/problemset/task/1628)
---
## 補充
---
## std::ranges
----
C++ 20 開始用來改進和取代舊的 STL 演算法
( 現在Zerojudge不能用:< )
----
### 一、改良版的STL演算法
**特色：**
不必寫 .begin() / .end()
----
### 常用演算法
* ranges::sort — 排序
* ranges::find — 找尋元素
* ranges::for_each — 對每個元素執行操作
* ranges::copy — 複製範圍
* ranges::min_element / ranges::max_element — 找最小或最大值
----
### 範例
```cpp=
#include <bits/stdc++.h>
#include <ranges> //建議
using namespace std;
int main() {
vector<int> v = {5, 3, 1, 4, 2, 6, 7, 8};
// sort
ranges::sort(v); // 直接排序
cout << "排序後: ";
for (int x : v) cout << x << " ";
cout << "\n";
// find
auto it_find = ranges::find(v, 4); // 找到 4
if (it_find != v.end()) cout << "找到元素 4\n";
// for_each
cout << "每個元素加 1: ";
ranges::for_each(v, [](int &x){ x += 1; });
for (int x : v) cout << x << " ";
cout << "\n";
// 4. min_element / max_element
auto it_min = ranges::min_element(v);
auto it_max = ranges::max_element(v);
cout << "最小值: " << *it_min << ", 最大值: " << *it_max << "\n";
// 5. copy
vector<int> copy_v;
ranges::copy(v, back_inserter(copy_v));
cout << "複製後的資料: ";
for (int x : copy_v) cout << x << " ";
cout << "\n";
}
```
----
### 二、延遲運算的「視圖」
``std::views`` 是 ranges 系統最強大的部分，
它提供「不複製資料」的操作，稱作 lazy evaluation（延遲求值）。
**特色：**
* 懶惰求值：不會產生新容器，只在迭代時才計算。
* 管線操作：用 | 把多個 view 串起來，類似 Unix 管線。
* 支援多種轉換與篩選。
----
### 常用 `views`
* views::filter - 篩選符合條件的元素
* views::transform - 對元素做轉換
* views::take - 取前 n 個元素
* views::drop - 忽略前 n 個元素
* views::iota - 生成連續數列
----
### 範例
```cpp=
#include <bits/stdc++.h>
#include <ranges> //建議
using namespace std;
int main() {
vector<int> v = {5, 3, 1, 4, 2, 6, 7, 8};
// 篩選偶數
auto evens = v | views::filter([](int x){ return x % 2 == 0; }); // {4, 2, 6, 8}
// 平方
auto squares = evens | views::transform([](int x){ return x*x; }); // {16, 4, 36, 64}
// 取前 3 個
auto first_three = squares | views::take(3);
cout << "偶數平方取前三: ";
for (int x : first_three) cout << x << " ";
cout << "\n";
// iota 生成數列
cout << "iota 1~9: ";
for (int x : views::iota(1, 10)) cout << x << " ";
cout << "\n";
// drop 前兩個
cout << "drop 前兩個元素: ";
for (int x : v | views::drop(2)) cout << x << " ";
cout << "\n";
}
```
----
### concept — 範圍型別檢查
* C++20 引入了 concepts，可以在編譯期檢查型別是否符合某種需求
* 範圍的定義：可以用 begin() 和 end() 遍歷。
* ``std::ranges::range<T>``：檢查型別 T 是否是一個「range」（可遍歷的物件）。
* ``std::ranges::range<T>`` 本身是一個 編譯期常數 (constexpr bool)
----
### 範例
```cpp=
#include<bits/stdc++.h>
#include <ranges> // 建議
using namespace std;
int main() {
vector<int> v = {1,2,3};
if constexpr (ranges::range<decltype(v)>) {
cout << "v is a range!" << endl;
}
int x = 42;
if constexpr (!ranges::range<decltype(x)>) {
cout << "x is NOT a range!" << endl;
}
}
```
---
## rope / pbds::tree
----
### rope
`rope` 是 GNU 的擴充資料結構，底層以平衡樹實作
對於大量字串的插入、刪除操作，比 `std::string` 更有效率
----
| 操作 | `std::string` | `rope` |
|:---------------:|:-------------:|:----------------:|
| 取得第 i 個字元 | $O(1)$ | $O(log n)$ |
| 插入字串 | $O(n)$ | $O(log n)$ |
| 刪除字串 | $O(n)$ | $O(log n)$ |
| 拼接字串 | $O(n)$ | $O(log n)$ |
| 儲存空間 | 緊密陣列 | 稍微浪費指標空間 |
----
### 宣告
```cpp
#include <ext/rope> //<bits/extc++.h>
using namespace __gnu_cxx;
crope r;
// rope<char> r;
```
----
### 用法
```cpp
crope r, a, b;
a += "u";
b += "vw";
r = a + b; // "uvw"
r.push_back('d'); // "uvwd"
r.append("e"); // "uvwde"
cout << r[0]; // 'u'
cout << r.size(); // 5
cout << r.empty(); // false
r.erase(0, 1); // "vwde" erase(位置, 長度)
r.insert(0, "k"); // "kvwde" insert(位置, 字串)
r[0] = 'c'; // "cvwde"
r.replace(0, 3, "abc"); // "abcde" replace(位置, 長度, 字串)
crope s = r.substr(1,3);// "bcd" substr(位置, 長度)
string s = r.c_str(); // 轉成 std::string
```
注意：單引號識字元，雙引號是字串
有些不能混用
----
### pbds::tree
其實就是強化版的`set`
他多了兩個操作
操作的時間複雜度跟 `set` 一樣都是$O(logn)$
但常數比較大
----
### 宣告
```cpp
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #include <bits/extc++.h>
using namespace __gnu_pbds;
tree<
int, // key type
null_type, // mapped type (set 類型)
less<int>, // comparator
rb_tree_tag, // 紅黑樹
tree_order_statistics_node_update // 支援 order statistics
> tr;
```
----
### 基本操作
| 操作 | 說明 | 範例 |
| ----------- | -------------- | ------------------------------ |
| `insert(x)` | 插入元素 x | `s.insert(5);` |
| `erase(x)` | 刪除元素 x | `s.erase(5);` |
| `find(x)` | 查找元素 x | `if(s.find(5) != s.end()) ...` |
| `count(x)` | 是否存在元素 x (0/1) | `s.count(5);` |
| `size()` | 元素數量 | `s.size();` |
| `empty()` | 是否為空 | `s.empty();` |
----
### 特有操作
| 操作 | 說明 |
| ------------------ | ------------------------------------------ |
| `order_of_key(x)` | 返回 **小於 x 的元素個數** |
| `find_by_order(k)` | 返回 **第 k 小元素** 的迭代器（從 0 開始數） |
{"title":"資料結構","description":"資料結構是「組織資料的方式」，讓我們能更有效率地「儲存、查詢、修改、刪除」資料。陣列就是其中一種。","contributors":"[{\"id\":\"0fedbf87-2d4f-488d-a09d-9555c0b2844c\",\"add\":23257,\"del\":2153,\"latestUpdatedAt\":1768217016572}]"}