類陣列容器

本文提到的資料結構在 STL 裡都有實作，詳細用法請自己看 cppreference。

動態陣列

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

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

它改變長度的方式是，一開始它會先開一段連續記憶體來用，如果陣列長度增長到超出這個空間，那麼會再開一段更長的連續記憶體，然後把所有元素搬移到新的空間去，雖然乍聽之下每次加入東西最慘會花到 ，總共就 了，但事實上每次搬東西的量會是 ，加起來只有 而已。

不過常數還是有點大，建議兩種作法，有元素的部分稱為「陣列大小」，目前有的空間稱為「空間大小」： - 一開始就把陣列開大，也就是一開始就讓它有很多個元素，也就是說，這麼做之後你完全可以把它當普通陣列來用，這用在不需要 push_back 的狀況。 - 用 reserve 來把空間大小開大，這個作法是用在需要 push_back 的狀況。

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

在 C++11 中，push_back 有了個替代品叫 emplace_back，它們的時間複雜度同為 ，但 emplace_back 常數比較小。

一些複雜度： - 存取：可隨機存取，。 - 插入：在最後面是 （均攤）、其他地方是 ，所以不要隨便用 insert。 - 刪除：在最後面是 、其他地方是 。 - resize、clear：。

deque

deque 的全稱是 double-ended queue，也就是雙向佇列的意思，不過我不喜歡把它當成一種 queue。它也算是一種動態陣列，和 vector 不同的是，它可以在前後 插入刪除。

deque 的實作原理是，它的元素會被分成很多段放在記憶體上，不像 vector，變太大還要搬走，但實際上 deque 的常數是比 vector 大的，所以非必要最好別用 deque。

deque 的操作和 vector 幾乎一樣，而且可以用 [] 存中間的元素。

堆疊（stack）

stack 是一種先進後出的結構，像是疊盤子一樣，先放下去的會最慢被拿出來。可以把 stack 想成是一疊元素，最上面的元素就是堆頂。

stack 的功能是 vector 功能的子集，以 vector 來說，堆頂就是 back()、放東西到堆頂是 push_back()、把堆頂丟掉是 pop_back()，同理 deque 也可以拿來實作 stack，至於 STL 中的 stack 預設是用 deque 實作的，所以它其實是 deque 劣化版 (?)，不過寫成 stack 的可讀性比較高一點。

STL 的 stack 只能問堆頂是什麼，有時候會需要用到 stack 裡除了堆頂以外的元素，例如凸包，這個時候可以改用 vector。

佇列（queue）

queue 是一種先進先出的結構，也就是先放進去的元素，會先被取出來，跟排隊一樣，先排隊的人會先離開隊伍。

queue 的功能是 deque 的功能的子集，實際上 STL 裡的 queue 也是用 deque 實作的，而且和 stack 一樣，queue 只能問最前面和最後面的元素，所以在需要知道其他元素的狀況，可以改用 deque。