動態陣列

本文已停止更新，新版請至 WiwiHo 的競程筆記

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

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

它改變長度的方式是，一開始它會先開一段連續記憶體來用，如果陣列長度增長到超出這個空間，那麼會再開一段更長的連續記憶體，然後把所有元素搬移到新的空間去，這個動作會是 \(O(n)\)，所以我建議兩種作法，我把有元素的部分稱為「陣列大小」，目前有的空間稱為「空間大小」：

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 可以這樣宣告：


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