- 110 交大資演 (20)


（B） A container such as std::vector (typically) **doesn't grow one place at a time**, but instead allocates some extra, for example doubling or quadrupling the reserved memory space when it needs to grow.
> 引自 stackoverflow

（C） 用 shrink_to_fit()
（D） 如果剛好需要 reallocate 即 O(n)

---

### Vector特性
- Vector 就像是 dynamic 的 array（vector 用 dynamic table 來 implement），在 insert / delete element 的時候會自動 resize
- 如果 insert 到 full table 時 vector size double
- 存放在連續的記憶體空間（因此 support direct access）
- data insert at the end
> 因為有時候 insert 需要擴充，所以 insert 的 time 是不固定的
> 如果是 delete 則是 O(1)，因為 delete 不會有 resize 的問題


> 我們並不會每次 insert 都直接 reallocate 一整個 array，再把所有的 element 都移過去（too expensive）

> 所以對於 insert 時可能需要更多空間的問題，解決方法：
>>用 container 直接每次多配一點空間，使得只有在 array 大小呈對數成長時我們才需要 reallocate。


> 相較 array 是固定大小，vector 用 container 多配一點空間當然會比較浪費空間
> → 用空間去換 dynamic resize

> 跟 deques, lists, forward lists 相比，vector
> - **more efficient<font color = "red"> O(1)</font>**: access element
> *(像 array 一樣放在連續的記憶體空間，所以可用 pointer + offset 去 access element)*
> - **相對 efficient <font color = "red">amortized O(1)</font>**: 從尾端 insert / remove element
> - **worse <font color = "red">O(n)</font>**: insert / remove 非尾端的 element
>> O(n) → 和尾端的距離

- a suquence of n insertion 會花 linear time 因為 single insertion 的 amortized time 是 O(1)

### Function

#### push_back() <font color = "red">amortized O(1)</font>
Add element at the end

#### capacity() <font color = "red"> O(1)</font>
Return 目前 allocated 給 vector 的 storage space 大小(用 element 數表示）

#### size() <font color = "red"> O(1)</font>
Return 目前 vector 中的 element 個數

#### shrink_to_fit() <font color = "red">O(n)</font>
把 container 大小縮小到目前 vector 中的元素個數
> → reduce capacity() to size()

---

### Reference
[geekforgeeks_Vector in C++ STL](https://www.geeksforgeeks.org/vector-in-cpp-stl/)
[Cplusplus_Vectors](https://cplusplus.com/reference/vector/vector/)
[Washington University Lecture Notes](https://courses.cs.washington.edu/courses/cse333/18su/lectures/14-c++-STL.pdf)
[Stackoverflow](https://stackoverflow.com/questions/21847421/vector-reallocation-c)