介紹
1. 本質與存儲結構
- 動態數組實現：vector 本質是動態分配的數組，采用連續內存空間存儲元素，支持下標訪問（如?
vec[i]），訪問效率與普通數組一致（時間復雜度 O (1)）。 - 動態擴容機制：當元素數量超過當前容量時，vector 會重新分配更大的內存空間，將原元素復制到新空間。為避免頻繁擴容，其擴容策略通常為對數增長（如每次容量翻倍），確保末尾插入元素的均攤時間復雜度為 O (1)。
2. 空間分配策略
- 預分配額外空間：vector 會分配比實際需求更大的存儲空間，以減少擴容次數。例如，初始容量為 n 時，插入新元素可能直接擴容至 2n，而非每次只增加 1 個元素的空間。
- 空間與效率的權衡：預分配策略雖增加了初始存儲空間占用，但避免了頻繁內存重分配的開銷（如復制元素的耗時），在動態增長場景下更高效。
?3. 與其他序列容器的差異
- 與 deque 的對比：
- deque 兩端插入 / 刪除效率更高（vector 僅末尾高效），且支持動態擴容（但內存非連續，需維護分段數組）。
- 與 list/forward_list 的對比：
- list/forward_list 為雙向鏈表 / 單向鏈表，內存不連續，不支持下標訪問，但任意位置插入 / 刪除效率更高（無需移動元素）。
- vector 的迭代器和引用更穩定（連續內存保證迭代器不會因中間元素刪除而失效，除非操作涉及擴容）。
?4. 適用場景與注意事項
- 適用場景：
- 需要頻繁通過下標訪問元素（如數組場景）。
- 主要在末尾進行插入 / 刪除操作（如棧、隊列場景）。
- 注意事項：
- 非末尾插入 / 刪除操作（如中間位置插入）會導致元素移動，效率較低，此時優先選擇 list。
- 若已知數據量大小，可使用?
reserve(n)?預分配空間，避免多次擴容。 - 擴容會導致原有迭代器、指針、引用失效（因內存地址變更），需重新獲取。
實現?
基本結構
在我們的vector的實現中，迭代器部分不需要特殊處理，它只是一個普通的指針，只是typedef的結果。
template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};?這就是vector的基本結構，有三個指針，分別指向vecotr的開始位置，元素最后的插入位置以及該空間結束位置。
迭代器
因為vector的迭代器很質樸，就是一個指針，所以他的實現也非常簡單，不需要進行++、--運算符重載操作，只需要寫出const迭代器和普通迭代器，其實就是用const對指針修飾一下，代碼如下：
typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;} T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}
?
?size與capacity
實現size與capacity就是用指針進行相減
size_t capacity() const{return _endofstorage - _start;}size_t size() const{return _finish - _start;}
reserve?
reserve是預先分配指定大小的內存空間，以避免后續插入元素時頻繁觸發動態擴容，從而提高性能。
- 注意：
reserve?僅改變容量，不改變容器的大小（size()），也不初始化元素。
實現：若?n?大于當前容器的容量（capacity()），則重新分配內存，使容量至少為?n，然后將原來的數據拷貝到新開的空間中，完成操作后，再將_start指向新開的空間；否則不做任何操作。?
void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];size_t sz = size();if (_start){//memcpy(tmp, _start, sizeof(T) * sz);for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}}resize?
- 若?
n > size()，容器擴容并插入新元素。 - 若?
n < size()，容器收縮并刪除尾部元素。 - 若?
n == size()，不做任何操作。
下面將<=合并起來。
void resize(size_t n, const T& val = T()){if (n <= size()){_finish = _start + n;}else{reserve(n);while (_finish < _start + n){*_finish = val;++_finish;}}}insert
首先先用assert判斷傳入的迭代器位置是否合理，不合理直接報錯，若合理，看_finsh和_endofstorage是否相等，若相等則說明需要擴容。擴容時，需要重新更新一下傳入迭代器的位置，因為擴容后位置發生了變化。
之后進行從后往前挪動數據，切記，一定是從后往前！！！
void insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;}從實現我們也可以看出，insert是比較消耗時間的。
push_back
有了insert，那么push_back的實現就非常簡單了，直接復用就可以了。
void push_back(const T& x){/*if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;*/insert(end(), x);}erase
類似于insert，就不多解釋。
iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;++it;}--_finish;return pos;}構造函數
vector的構造方法是很多的，我直接分享給大家，原理都很簡單
vector(){}template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}vector(int n, const T& val = T()){reserve(n);for (int i = 0; i < n; i++){push_back(val);}}// v2(v1)vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}?
入門項目推薦)
