# 動態陣列
###### tags: `Competitive Programming Note`

本文已停止更新，新版請至 [WiwiHo 的競程筆記](https://cp.wiwiho.me/)

原始的陣列是開一塊連續記憶體來放資料，這段空間一開始就要決定，且不能改變。那麼有沒有可以改變長度的陣列呢？

STL 中，有一個容器叫 `vector`，它就是一個動態陣列，可以改變長度。

它改變長度的方式是，一開始它會先開一段連續記憶體來用，如果陣列長度增長到超出這個空間，那麼會再開一段更長的連續記憶體，然後把所有元素搬移到新的空間去，這個動作會是 $O(n)$，所以我建議兩種作法，我把有元素的部分稱為「陣列大小」，目前有的空間稱為「空間大小」：
- 一開始就把陣列開大，也就是一開始就讓它有很多個元素，也就是說，這麼做之後你完全可以把它當普通陣列來用，這用在不需要 `push_back` 的狀況。
- 用 `reserve` 來把空間大小開大，這個作法是用在你需要 `push_back` 的狀況。

`vector` 除了有長度可變的優點外，也有很多附加功能，比原始的陣列好用很多，所以即使長度不會改變，大多數的時候我也都會用 `vector` 來代替陣列，這種時候我會使用第一種方式。

但如果我想做的事情是把不知道幾個東西放進 `vector` 裡，那我就會用第二種方式，像是在記錄圖上一個節點的相鄰節點，我不確定有幾個相鄰節點，所以我會想要一個一個放進去。

在 C++11 中，`push_back` 有了個替代品叫 `emplace_back`，它們的時間複雜度同為 $O(1)$，但 `emplace_back` 常數比較小，所以我會比較建議使用它。

`vector` 的迭代器是隨機存取迭代器，它和普通陣列一樣可以隨機存取。

`vector` 可以做的動作大致有：
- `size()` - 取得陣列大小，$O(1)$。
- `resize(size, T value)` - 變更陣列大小為 `size`，多出的地方會填上 `value`，`value` 不填預設是 `T()`，也就是 `T` 以無參數建構出來的東西，例如 `int()` 就是 `0`、`vector()` 是空的 `vector`。
- `empty()` - 判斷是否為空，$O(1)$。
- `reserve(size)` - 變更空間大小為 `size`，如果陣列裡有東西，$O(n)$，否則 $O(1)$。
- `operator[]` - 取得指定位置的元素參照，$O(1)$。
- `front()` - 取得第一個元素參照，$O(1)$。
- `back()` - 取得最後一個元素參照，$O(1)$。
- `push_back(T value)` - 在尾端加入新元素，$O(1)$。
- `pop_back(T)` - 移除尾端元素，$O(1)$。
- `insert(iterator pos, T value)` - 在 `pos` 插入元素，本來在該位置和之後的元素會後移，`pos` 會失效，回傳一個指向被插入元素的 iterator，$O(n)$。
- `erase(iterator pos)` - 將該位置的元素移除，後面的元素會向前移，回傳指向被刪除元素的下一個元素的 iterator，$O(n)$。
- `clear()` - 清除全部元素。
- `operator=` - 複製 `vector`。

建構子：
- `vector(size, T value)` - 讓 `vector` 中有 `size` 個 `value`，`value` 沒填則是 `T()`。
- `vector(vector a)` - 複製 `a`。

另外，`vector` 可以這樣宣告：

vector<int> a = {1, 2, 3, 4, 5}。