摘要訊息 : 向量是資料結構中最基礎的結構, 也是程式設計中運用最多的資料結構.

0. 前言

在線性代數中, 向量是一個一維矩陣, 我們通常表示為 \boldsymbol {\alpha} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \}. \boldsymbol {\alpha} 在線性代數中的全稱應該是 n 維向量. 在程式設計中, 特別是在 C/C++ 中, 我們通常使用陣列來表示向量. 但是, C++ 提供的陣列是固定維度的, 而且是不可擴展的. 在資料結構中, 我們所說的向量是一個可變長度的陣列.

更新紀錄 :

• 2022 年 3 月 20 日進行第一次更新和修正.

1. 定義

定義 1. 設有 n 個元素 \alpha_{1}, \alpha_{2}, ..., \alpha_{n}, 稱由這 n 個元素組成的線性列表 \boldsymbol {\alpha} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \} 為向量 (vector).

由向量的定義我們可以看到, 向量中的元素是允許重複的, 它和集合不一樣. 另外, 從定義我們可以看出, 向量中的元素是有序的. 任取 i, 第 i 個元素必定是 \alpha_{i}.其中, 1 \leq i \leq n.

但是一般來說, 在程式設計語言中, 陣列注標是從 0 開始的, 對於定義 1 中的 \boldsymbol {\alpha} 來說, 陣列注標的範圍是 [0, n - 1]. 不過, 在資料結構中, 我們通常使用數學中的表示方法, 並不採用程式設計的從 0 開始的表示方法.

在 C/C++, 甚至其它一些程式設計語言中, 向量有一個非常重要的特性, 就是它裡面的所有元素都是連續儲存的. 也就是說, 我們在向量中存取元素的效能是非常高的. 因此, 如果某些元素經常被存取, 或者某些位置中的元素經常被改動, 我們可以使用向量作為儲存的資料結構. 另外, 在資料結構中, 我們一般不限制向量的長度.

2. 插入

在第一節中, 我們提到過向量中的元素是連續儲存的, 這就導致在向量非尾部插入元素是比較麻煩的. 設我們在 \boldsymbol {\alpha} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \} 的第 i 個位置插入 m 個元素 (1 \leq i \leq n + 1), 具體需要這樣做 :

1. 將第 i 個位置開始的剩餘元素向後移動 m 個位置;
2. 分別將新元素插入這 m 個位置.

在程式設計中, 並沒有那麼簡單. 我們需要檢查向量是否可以再容納多 m 個元素, 否則就要重新配置空間; 在 C++ 中, 我們還可以考慮元素的複製與移動以提高程式效能; 如果向量本身是空的, 那麼我們便可以省略向後移動元素這個步驟; 如果是在最後插入, 也可以省略掉移動元素這個步驟...

另外, 儘管資料結構中的向量在理論上可以無限擴充, 但是實際上向量的大小是受限於可配置的空間的. 例如, 如果我們是在記憶體中儲存向量, 那麼向量的大小就受限於記憶體的容量大小.

很顯然, 插入元素的時候, 我們需要向後移動的元素最少為 0 個, 最多為 n 個. 那麼移動元素的平均時間複雜度是 \Theta(n). 而插入元素的操作我們可以視為 \Theta(1) 的. 總體來說, 插入操作的時間複雜度為 \Theta(n). 有一種情況很特殊, 就是只在尾部插入元素, 這個時候的時間複雜度應該是 \Theta(1) 的. 然而事實上, 如果向量的空間不能夠容納那麼多元素, 需要配置新的空間的話, 這個時候我們需要把原空間下的所有元素移動到新的空間中, 這個時候的時間複雜度仍然為 \Theta(n).

對於只在尾部插入元素的時間複雜度, 我們認為其為平攤 \Theta(1) 的. 這個涉及到平攤分析, 此處我們不講解.

在不需要重新為向量配置空間的時候, 插入元素操作需要的額外輔助空間和插入元素的數量以及向量中本身具有的元素數量都無關, 因此空間複雜度為 \Theta(1). 但是如果需要為向量配置新的空間, 那麼原始向量使用的空間就作為了輔助空間, 此時的空間複雜度為 \Theta(n).

3. 移除

在向量中移除某個元素或者移除某個區間的元素也是比較麻煩的. 假設我們需要移除 \boldsymbol {\alpha} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \} 從第 i 個位置開始的 m 個元素 (1 \leq i \leq n, i + m \leq n), 我們需要這樣做 :

1. 將第 i 個位置開始的 m 個元素移除掉;
2. 將第 i + m + 1 個位置開始的剩餘元素向前移動 m 個位置.

在程式設計中, 特別是在 C++ 中, 我們通常不進行第一步移除操作, 而是直接將剩餘元素往前移動 m 個位置即可 (通常是直接複製). 但是, 我們還需要處理尾部的 m 個元素, 因為移除之後這 m 個元素應該是被遺棄的. 也就是說, Figure 2 中描述的情況只是理想情況下的, 實際應該是這樣的 :

在移除元素的情況下, 我們一般不會像插入那樣去考慮空間的重新配置問題. 在這個大條件下, 我們需要考慮的是刪除元素的位置, 刪除的數量, 向量是否本身為空....

移除元素的時間複雜度很顯然是 \Theta(n), 空間複雜度是 \Theta(1).

4. 搜尋

在一個向量中搜尋一個元素的方法很簡單, 我們只要從向量中的第一個元素開始一個一個搜尋即可. 當然, 對於有序的向量, 我們可以參考《【演算法】二分搜尋法 (Binary Search)》來提高搜尋效率.

顯然, 搜尋元素的數量至多為 n 個, 至少為 1 個, 平均情況下的時間複雜度為 \Theta(n). 而搜尋需要的輔助空間和向量中的元素數量無關, 因此空間複雜度為 \Theta(1).

5. 字典比較

我們採用字典比較的方式來比較兩個向量. 設有兩個向量 \boldsymbol {\alpha} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \} 和 \boldsymbol {\beta} = \left \{ \beta_{1}, \beta_{2}, ..., \beta_{m} \right \}. 不失一般性, 我們不妨設 n \leq m. 對於 n > m 的情況只需要令 \boldsymbol {\alpha} = \left \{ \beta_{1}, \beta_{2}, ..., \beta_{m} \right \}, \boldsymbol {\beta} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \} 便類似可得 :

1. 首先比較 \alpha_{1} 和 \beta_{1} :
   • 如果 \alpha_{1} < \beta_{1}, 則比較結束, 我們稱 \boldsymbol {\alpha} < \boldsymbol {\beta};
   • 如果 \alpha_{1} > \beta_{1}, 則比較結束, 我們稱 \boldsymbol {\alpha} > \boldsymbol {\beta};
   • \alpha_{1} = \beta_{1}, 則繼續比較;
2. 然後比較 \alpha_{2} 和 \beta_{2} :
   • 如果 \alpha_{1} < \beta_{1}, 則比較結束, 我們稱 \boldsymbol {\alpha} < \boldsymbol {\beta};
   • 如果 \alpha_{1} > \beta_{1}, 則比較結束, 我們稱 \boldsymbol {\alpha} > \boldsymbol {\beta};
   • \alpha_{1} = \beta_{1}, 則繼續比較;
3. 將比較重複, 直到 \alpha_{1} = \alpha_{1}, \alpha_{2} = \beta_{2}, ..., \alpha_{n - 1} = \beta_{n - 1}, \alpha_{n} = \beta_{n} 成立, 此時比較結束 :
   • 如果 n = m, 則比較結束, 我們稱 \boldsymbol {\alpha} = \boldsymbol {\beta};
   • 如果 n < m, 則比較結束, 我們稱 \boldsymbol {\alpha} < \boldsymbol {\beta} (因為 \boldsymbol {\alpha} 中的元素比較少).

假如兩個元素之間比較的時間複雜度是 \Theta(1) 的, 那麼字典比較的時間複雜度為 \Theta(n) (這裡仍然假設 n \leq m 成立). 字典比較需要的輔助空間和元素數量無關, 假設比較操作需要的輔助空間也和元素數量無關, 那麼字典比較的空間複雜度為 \Theta(1).

6. 旋轉

設有向量 \boldsymbol {\alpha} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \}, 以 \alpha_{1} 為基準, 將 \boldsymbol {\alpha} 向左旋轉 k 個元素 (0 < k < n) 是指將前 k 個元素放置在序列尾部, 剩餘 n - k 個元素放置在序列頭部. 最終得到新的向量 \boldsymbol {\alpha}_{\mathrm {L}} = \left \{ \alpha_{k + 1}, \alpha_{k + 2}, ..., \alpha_{n}, \alpha_{1}, \alpha_{2}, ..., \alpha_{k} \right \}. 以 \alpha_{1} 為基準, 將 \boldsymbol {\alpha} 向右旋轉 k 個元素 (0 < k < n) 是指將後 k 個元素放置在序列頭部, 剩餘 n - k 個元素放置在序列尾部. 最終得到新的向量 \boldsymbol {\alpha}_{\mathrm {R}} = \left \{ \alpha_{n - k + 1}, \alpha_{n - k + 2}, ..., \alpha_{n}, \alpha_{1}, \alpha_{2}, ..., \alpha_{k} \right \}.

從 Figure 4 中, 我們很容易發現, 所謂的旋轉就是循環移位. 例如向左旋轉 k 個元素實際上就是把元素 \alpha_{k + 1}, \alpha_{k + 2}, ..., \alpha_{n} 一個一個向前移動. 另外, 向左旋轉和向右旋轉實際上是相互可以轉化的. 向右旋轉 k 個位置實際上也是向左旋轉 n - k 個元素.

由於對向量的左右旋轉是互通的, 因此接下來我們主要討論向左旋轉的情況.

事實上, 我們已經有了一個對旋轉演算法的初步構想. 每次把第一個元素提取出來, 然後把剩下的元素向前移動一個位置, 然後把提取出來的元素放在向量的最後. 如果要向左旋轉 k 個元素, 那麼我們只要把上面這個步驟運作 k 次即可. 但是這樣的演算法時間複雜度是很高的. 首先, 移動 n - 1 個元素需要消耗 \Theta(n) 的時間. 移動至多進行 n - 1 次, 至少進行 1 次. 那麼, 平均情況下的時間複雜度就是 \Theta(kn) = O(n^{2}). 另外, 我們需要額外一個位置儲存提取出來的元素, 剩下的操作需要的輔助空間和元素數量無關, 因此空間複雜度為 \Theta(1).

6.1 使用額外的空間

對於向量 \boldsymbol {\alpha} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \}, 如果要向左旋轉 k 個元素, 我們只需要利用一個大小為 k 的輔助空間, 將前 k 個元素移動到輔助空間中, 然後將向量中後 n - k 個元素向前移動 k 個位置, 然後再將輔助空間中的元素移動回到原向量中即可.

Algorithm 6 中對這個演算法進行了優化. 旋轉元素的數量將向量 \boldsymbol {\alpha} 分隔為了兩個部分 : \boldsymbol {\alpha}_{\mathrm {L}} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{k} \right \} 和 \boldsymbol {\alpha}_{\mathrm {R}} = \left \{ \alpha_{k + 1}, \alpha_{k + 2}, ..., \alpha_{n} \right \}. 若子向量 \boldsymbol {\alpha}_{\mathrm {L}} 中的元素比較少, 那麼就會將這些元素移動到輔助空間中; 否則, 會將 \boldsymbol {\alpha}_{\mathrm {R}} 中的元素移動到輔助空間中.

使用了額外空間的旋轉演算法的時間複雜度為 \Theta(n), 空間複雜度是 \Theta(k) = O(n).

6.2 借助最大公因數

設有函數 \mathop {\mathrm {gcd}}(x, y) 能夠回傳參數 x 和 y 的最大公因數, 我們的目標是將向量 \boldsymbol {\alpha} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \} 向左旋轉 k 個元素 (1 < k < n).

現在我們來觀察向量的旋轉. 首先將第一個元素提取出來, 接下來放置在這個位置上的元素應該是 \alpha_{1 + k}; 而對於第 1 + k 個位置, 接替 \alpha_{1 + k} 的應該是 \alpha_{1 + 2k} (只要 1 + 2k \leq n); ... 設上面的步驟重複了 r 次, 有 1 + rk \leq n 且 1 + (r + 1)k > n, 那麼第 \alpha_{1 + rk} 這個位置就空出來了. 至於提取出來的元素是不是放在第 1 + rk 個位置, 這個並不一定 (記住這個不一定, 這個要在稍後進行詳細探討). 但是我們對第二個元素, 第三個元素, ..., 一直到第 \mathop {\mathrm {gcd}}(k, n) 個元素一直這樣做的話, 最終我們也將後面 n - k 個元素安排到了正確的位置上 : {\boldsymbol {\alpha}}' = \left \{ \alpha_{k + 1}, \alpha_{k + 2}, ..., \alpha_{n}, ... \right \} :

根據上一段的演算法步驟描述, 我們就有了 Figure 5 中的實例. 但是 Figure 5 給出的結果是不正確的. 因為對於 \left \{ 1, 2, 3, 4, 5 \right \} 向左旋轉兩個元素的結果應該是 \left \{ 3, 4, 5, 1, 2 \right \}. Figure 5 不正確的原因就在於我們還沒有分析第 1 + rk 個位置應不應該放置提取出來的元素.

其實有一個很簡單的方法用來判定第 1 + rk 個位置應該放置哪一個元素. 我們知道, 第 1 + rk 個位置仍然在向量的範圍之內, 但是繼續往後移動 k 個位置, 也就是 1 + (r + 1)k 這個位置就在向量的範圍之外了. 此時, 我們需要把這個位置調整到向量之內. 有一種方法, 就是將向量想像成一個環 :\displaystyle {\boldsymbol {\alpha} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n}, \alpha_{1}, \alpha_{2}, ..., \alpha_{n}, ... \right \}} 此時, 1 + (r + 1)k 這個位置就必定落在 \alpha_{1 + (r + 1)k - n} 上. 此時, 我們只需要判斷一下剛剛被提取的元素是否也位於這個位置 : 如果剛剛被提取的元素也位於這個位置, 我們將提取的這個元素指派給 \alpha_{1 + rk} 即可; 否則, 從 1 + (r + 1)k - n 這個位置開始, 繼續將後面的元素移動到前面即可.

例題 1. 設 \boldsymbol {\alpha} = \left \{ 1, 2, 3, 4, 5 \right \}, 嘗試將其向左旋轉兩個元素.

解 :

在這個例題中, k = 2. 首先, 我們讓指標 p 指向第一個位置, q 指向 p + k 這個位置, 即第三個位置 :

提取 p 中的元素另外儲存, 將 q 中的元素移動至 p, 令 p = q, 再將 q 向後移動 k 個元素 :

將 q 中的元素移動至 p, 令 p = q. 將 q 向後移動 k 個元素的過程中, 我們發現 q 越界. 因此, 令 q 減去 n, 則現在 q 在第二個位置 :

將 q 中的元素移動至 p, 令 p = q, 再將 q 向後移動 k 個元素 :

將 q 中的元素移動至 p, 令 p = q. 將 q 向後移動 k 個元素後發現 q 越界. 令 q 減去 n, 則 q 在第一個位置. 這和演算法起始的位置是一樣的. 此時, 將最初提取的元素放在 p 中, 演算法終結.

將 q 中的元素移動至 p, 令 p = q, 再將 q 向後移動 k 個元素 :

\blacksquare

例題 2. 設 \boldsymbol {\alpha} = \left \{ 1, 2, 3, 4, 5, 6 \right \}, 嘗試將其向左旋轉兩個元素.

解 :

在這個例題中, k = 2. 首先, 我們讓指標 p 指向第一個位置, q 指向 p + k 這個位置, 即第三個位置 :

提取 p 中的元素另外儲存, 將 q 中的元素移動至 p, 令 p = q, 再將 q 向後移動 k 個元素 :

將 q 中的元素移動至 p, 令 p = q. 將 q 向後移動 k 個元素的過程中, 我們發現 q 越界. 因此, 令 q 減去 n, 則現在 q 在起始位置. 那麼我們將提取出來的元素放入 p 中, 便可以結束本輪的移動 :

現在將 p 指向第二個位置, 提取 p 中的元素另外儲存, 將 q 指向 p + k 這個位置. 重複上面相同的步驟, 我們便可以得到最終的移動結果 :

\blacksquare

我們發現, 例題 1 中, 我們經過一輪之後旋轉便完成, 這在例題 2 中經歷了兩輪. 具體需要經過幾輪才能完成演算法, 取決於 k 和 n 的最大公因數 \mathop {\mathrm {gcd}}(k, n). 這樣, 我們就可以將演算法描述出來 :

值得注意的是, C++ 標準樣板程式庫 libc++ 中針對隨機訪問疊代器的 std::rotate 就使用了這個演算法. 很顯然, 這個演算法的空間複雜度為 \Theta(1). 而演算法尋訪的元素數量是 n 個, 因此演算法總體的時間複雜度應該是 \Theta(n).

6.3 分而治之

使用《【演算法】分而治之》中分而治之的思想, 同樣也可以解決向量的旋轉問題.

例題 3. 設 \boldsymbol {\alpha} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{k}, \alpha_{k + 1}, \alpha_{k + 2}, ..., \alpha_{n - k}, \alpha_{n - k + 1}, \alpha_{n - k + 2}, ..., \alpha_{n} \right \}, 嘗試將其相左旋轉 k 個元素.

解 :

我們首先將 \boldsymbol {\alpha} 分成兩個部分 :

再將 B 分為兩個部分, 右側的長度和 A 相同 :

交換 A 和 B_{\mathrm {R}} 可以得到 :

現在 A 的位置已經正確了. 令 {\boldsymbol {\alpha}}' = \left \{ \alpha_{n - k + 1}, \alpha_{n - k + 2}, ..., \alpha_{n}, \alpha_{k + 1}, \alpha_{k + 2}, ..., \alpha_{n - k} \right \}. 接下來只需要讓 {\boldsymbol {\alpha}}' 中的元素向左旋轉 k 個位置, 並且將結果和 \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{k} \right \} 合併即可.

\blacksquare

分而治之的思想就體現在於我們首先解決了 A 這一部分的元素, 接下來就是讓向量中剩下一部分再進行旋轉就可以了. 在例題 3 中, 我們沒有給出接下來的演算法過程. 接下來是將 {\boldsymbol {\alpha}}' = \left \{ \alpha_{n - k + 1}, \alpha_{n - k + 2}, …, \alpha_{n}, \alpha_{k + 1}, \alpha_{k + 2}, …, \alpha_{n - k} \right \} 向左旋轉 k 個元素. 現在再用 B_{\mathrm {R}} 和 B_{\mathrm {L}} 來標記就不合適了. 對照 Figure 8.3, 我們令 C = \left \{ \alpha_{n - k + 1}, \alpha_{n - k + 2}, …, \alpha_{n} \right \}, D = \left \{ \alpha_{k + 1}, \alpha_{k + 2}, …, \alpha_{n - k} \right \} :

• 如果 C 的長度比 D 小, 那麼我們將 D 分為兩個部分 D_{\mathrm {L}} 和 D_{\mathrm {R}}, D_{\mathrm {R}} 的長度和 C 的長度相等, 然後交換 D_{\mathrm {R}} 和 C. 最後將問題縮小為 D_{\mathrm {L}} 和 C;
• 如果 C 的長度比 D 大, 那麼我們將 C 分為兩個部分 C_{\mathrm {L}} 和 C_{\mathrm {R}}, C_{\mathrm {L}} 的長度和 D 相同, 然後交換 C_{\mathrm {L}} 和 D. 最後將問題縮小為 D 和 C_{\mathrm {R}};
• 如果 C 的長度和 D 相等, 那麼直接交換這兩個部分, 旋轉便完成.

基於上面的思想, 我們可以將演算法描述出來 :

由於使用了遞迴, 準確地來說, Algorithm 8 的空間複雜度不再是 \Theta(1) 而是 O(n). 但是, 遞迴是可以改為迴圈的, 那麼從這個角度來說, 我們又可以說使用了分而治之思想的旋轉演算法的空間複雜度為 \Theta(1). 而使用了分而治之思想的旋轉演算法的時間複雜度分析比較困難. 設 T(n) 是使用了分而治之思想的旋轉演算法的時間複雜度, 它可以被分為三個部分 :

• 交換某個範圍之內的時間複雜度 : \Theta(\min \left \{ k, n - k \right \});
• 遞迴部分的時間複雜度 : T(n - \min \left \{ k, n - k \right \});
• 合併子結果的時間複雜度 : \Theta(1).

那麼, 我們可以將 T(n) 表示為 \displaystyle {T(n) = \Theta(\min \left \{ k, n - k \right \}) + T(n - \min \left \{ k, n - k \right \}) + \Theta(1)}. 為了方便分析, 我們假設 n = mk, 其中 m 為整數且 m > 1. 此時採用《遞迴方程式 – 替代法與歸納法》中的替代法解這個遞迴方程式, 有 \displaystyle {\begin {aligned} T(n) &= \Theta(k) + T(n - k) + \Theta(1) \\ &= 2\Theta(k) + T(n - 2k) + 2\Theta(1) \\ &= ... \\ &= m\Theta(k) + T(n - mk) + m\Theta(1) \\ &= \Theta(mk) + \Theta(m) = \Theta(n). \end {aligned}} 因此, 使用了分而治之思想的旋轉演算法的時間複雜度為 \Theta(n).

6.4 反轉

反轉是一個很有趣的方法, 它只需要兩步便可以得到旋轉結果. 設有向量 \boldsymbol {\alpha} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \}, 現在要將向量 \boldsymbol {\alpha} 向左旋轉 k 個元素. 首先以 k 為界線, 將向量分成兩個部分 : \boldsymbol {\alpha}_{\mathrm {L}} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{k} \right \} 和 \boldsymbol {\alpha}_{\mathrm {R}} = \left \{ \alpha_{k + 1}, \alpha_{k + 2}, ..., \alpha_{n} \right \}. 然後將 \boldsymbol {\alpha}_{\mathrm {L}} 和 \boldsymbol {\alpha}_{\mathrm {R}} 反轉過來, 變成 {\boldsymbol {\alpha}_{\mathrm {L}}}' = \left \{ \alpha_{k}, \alpha_{k - 1}, ..., \alpha_{2}, \alpha_{1} \right \} 和 {\boldsymbol {\alpha}_{\mathrm {R}}}' = \left \{ \alpha_{n}, \alpha_{n - 1}, ...., \alpha_{k + 2}, \alpha_{k + 1} \right \}. 將 {\boldsymbol {\alpha}_{\mathrm {L}}}' 和 {\boldsymbol {\alpha}_{\mathrm {R}}}' 合併之後得到 {\boldsymbol {\alpha}}' = \left \{ \alpha_{k}, \alpha_{k - 1}, ..., \alpha_{2}, \alpha_{1}, \alpha_{n}, \alpha_{n - 1}, ..., \alpha_{k + 2}, \alpha_{k + 1} \right \}. 然後我們再將 {\boldsymbol {\alpha}}' 反轉過來, 便可以得到旋轉結果 {\boldsymbol {\alpha}}'' = \left \{ \alpha_{k + 1}, \alpha_{k + 2}, ..., \alpha_{n}, \alpha_{1}, \alpha_{2}, ..., \alpha_{k} \right \}.

很顯然, 使用了反轉的旋轉演算法的空間複雜度為 \Theta(1), 它所使用的空間和元素數量無關. 而反轉尋訪了兩次向量, 因此時間複雜度也是 \Theta(n). C++ 標準樣板程式庫 libc++ 採用借助最大公因數的旋轉演算法, 而不採用這種有趣的旋轉演算法的原因就在於, 借助最大公因數的旋轉演算法只需要尋訪向量一次.

7. 實作

我自己用 C++ 實作了向量 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/vector.hpp, 大家可以參考後自行實作.