C++：STL中vector的使用和模擬實現

在上一篇中講到了string類，string并不屬于STL中因為string出現的比STL早，但是在使用方法上兩者有相似之處，學習完string后再來看vector會容易的多，接著往下閱讀，一定會有收獲滴！

vector的介紹

vector的使用

?vector的構造函數

?vector的拷貝構造

?vector iterator 的使用

?vector的空間

vector增刪改?

vector的介紹

1.string是存儲字符串的類，vector是表示可變大小數組的序列容器。

2. 就像數組一樣，vector也采用的連續存儲空間來存儲元素。也就是意味著可以采用下標對vector的元素進行訪問，和數組一樣高效。但是又不像數組，它的大小是可以動態改變的，而且它的大小會被容器自動處理。

3. 本質講，vector使用動態分配數組來存儲它的元素。當新元素插入時候，這個數組需要被重新分配大小為了增加存儲空間。其做法是，分配一個新的數組，然后將全部元素移到這個數組。就時間而言，這是一個相對代價高的任務，因為每當一個新的元素加入到容器的時候，vector并不會每次都重新分配大小。

4. vector分配空間策略：vector會分配一些額外的空間以適應可能的增長，因為存儲空間比實際需要的存儲空間更大。不同的庫采用不同的策略權衡空間的使用和重新分配。但是無論如何，重新分配都應該是對數增長的間隔大小，以至于在末尾插入一個元素的時候是在常數時間的復雜度完成的。

5. 因此，vector占用了更多的存儲空間，為了獲得管理存儲空間的能力，并且以一種有效的方式動態增長。

6. 與其它動態序列容器相比（deque, list and forward_list）， vector在訪問元素的時候更加高效，在末尾添加和刪除元素相對高效。對于其它不在末尾的刪除和插入操作，效率更低。比起list和forward_list 統一的迭代器和引用更好。

vector的使用

對于vector的接口有很多，想要更仔細的看這里：https://legacy.cplusplus.com/reference/vector/vector/?kw=vector

?vector的構造函數

vector的構造函數重載了好幾種，所以初始化的方法也有多種。

vector() //無參構造vector(size_t n,const value_type& val = value_type()) //構造并初始化n個valvector(InputIterator ?rst, InputIterator last) //使用迭代器來初始化

?對于第二種的構造函數中value_type()會去調用該類型的構造函數，第三種使用迭代器來構造，對于vector的迭代器就是原生指針，區間是左閉右開。

示例：

int a[5] = { 1,2,3,4,5 };vector<int> v(a, a + 4);for (auto e : v){cout << e << " ";}cout << endl;vector<int>::iterator it = v.begin();vector<int> v1(v.begin(), v.end());for (auto e : v1){cout << e << " ";}cout << endl;

運行結果：

模擬實現：
成員變量：

typedef T* iterator;
typedef const T* const_iterator;iterator _start = nullptr;// 指向數據塊的開始
iterator _finish = nullptr;// 指向有效數據的尾
iterator _end_Of_Storage = nullptr;// 指向存儲容量的尾

        vector(){}vector(size_t n, const T& value = T()){resize(n,value);}vector(int n, const T& value = T()){resize(n, value);}template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}

?vector的拷貝構造

vector的拷貝構造是指創建一個新的vector對象，其內容與原vector對象完全相同。

vector (const vector& x);

?模擬實現：

vector(const vector<T>& v){_start = new T[v.capacity()];for (size_t i = 0; i < v.size(); i++){_start[i] = v. _start[i];}_finish = _start + v.size();_end_Of_Storage = _start + v.capacity();}

在模擬實現時需要注意，拷貝分為淺拷貝和深拷貝，如果在vector的實現中使用淺拷貝就會出問題，會出現析構兩次以及野指針的問題，所以需要深拷貝。?

?vector iterator 的使用

查看vector文檔可以看到vector的迭代器

?begin()和end()：獲取第一個數據位置的iterator/const_iterator，獲取最后一個數據的下一個位置的iterator/const_iterator。

模擬實現：

iterator begin(){return _start;}iterator end() {return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}

?vector的空間

size() 返回 vector 當前存儲的元素數量，是實際已使用的空間大小。
示例：

std::vector<int> vec = {1, 2, 3};
std::cout << vec.size(); // 輸出 3

capacity() 返回 vector 當前分配的存儲空間大小（以元素數量計），可能大于或等于 size()。
示例：

std::vector<int> vec;
vec.reserve(10);
std::cout << vec.capacity(); // 輸出 10（size 仍為 0）

resize(n) 調整 vector 的 size 為 n：

若 n < size()，多余元素被刪除。
若 n > size()，新增元素默認初始化（或通過第二個參數指定值）。
示例：

std::vector<int> vec = {1, 2, 3};
vec.resize(5);      // 變為 {1, 2, 3, 0, 0}
vec.resize(2);       // 變為 {1, 2}

reserve(n) 預分配至少容納 n 個元素的內存空間，避免多次動態擴容（僅影響 capacity，不改變 size）。
示例：

std::vector<int> vec;
vec.reserve(100);    // 提前分配空間
vec.push_back(1);    // 不會觸發擴容

區別：?

size 是實際元素數量，capacity 是當前分配的內存容量。
resize 修改 size 并可能初始化/刪除元素，reserve 僅調整 capacity 不改變 size。
頻繁插入數據時，reserve 可減少重新分配開銷。

capacity的代碼在vs和g++下分別運行會發現，vs下capacity是按1.5倍增長的，g++是按2倍增長的。這個問題經常會考察，不要固化的認為，vector增容都是2倍，具體增長多少是根據具體的需求定義的。vs是PJ版本STL，g++是SGI版本STL。 reserve只負責開辟空間，如果確定知道需要用多少空間，reserve可以緩解vector增容的代價缺陷問題。 resize在開空間的同時還會進行初始化，影響size。

?模擬實現：

          size_t size() const{return _finish - _start;}size_t capacity() const{return _end_Of_Storage - _start;}void reserve(size_t n){if (n > capacity()){size_t oldsz = size();T* tmp = new T[n];/*memcpy(tmp, _start, n * sizeof(T));*/for (size_t i = 0; i < oldsz; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = tmp + oldsz;_end_Of_Storage = _start + n;}}void resize(size_t n, const T& value = T()){if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish != _start + n){*_finish = value;_finish++;}}}

vector增刪改?

尾插：push_back()?在 vector 末尾添加元素：

vector<int> vec = {1, 2, 3};
vec.push_back(4); // vec: {1, 2, 3, 4}

模擬實現：

void push_back(const T& x){/*if (size() == capacity()){size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}*_finish = x;_finish++;*/insert(end(), x);}

如果不用insert函數就使用注釋那一段代碼來實現尾插，效果是一樣的，只不過先實現insert函數的話寫尾插會更方便一點。

insert（）在指定位置插入元素：

vec.insert(vec.begin() + 1, 5); // vec: {1, 5, 2, 3, 4}

模擬實現：

iterator insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);if (size() == capacity()){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);pos = _start + len;}iterator end = _finish - 1;while (pos <= end){*(end+1) = *end;end--;}*pos = x;++_finish;return pos;}

erase()刪除指定位置的元素：?

vec.erase(vec.begin() + 2); // 刪除第3個元素，vec: {1, 5, 3, 4}
vec.erase(vec.begin(), vec.begin() + 2); // 刪除前2個元素，vec: {3, 4}

在使用erase需要注意迭代器失效的問題，?直接刪除當前迭代器指向的元素會導致該迭代器失效。

例如：

std::vector<int> vec = {1, 2, 3, 4};
auto it = vec.begin() + 1;
vec.erase(it); // it失效
// 此時訪問*it是未定義行為

以及循環刪除多個元素：

std::vector<int> vec = {1, 2, 3, 4};
for (auto it = vec.begin(); it != vec.end(); ++it) {if (*it % 2 == 0) {vec.erase(it); // it失效后，++it行為未定義}
}

對于這些我們需要重新來定義迭代器it，erase會返回指向被刪除下一位置的迭代器，所以我們需要重新接收更新迭代器，正確處理方法：

std::vector<int> vec = {1, 2, 3, 4};
for (auto it = vec.begin(); it != vec.end(); ) {if (*it % 2 == 0) {it = vec.erase(it); // 更新迭代器} else {++it;}
}

模擬實現：

iterator erase(iterator pos){assert(pos >= _start && pos < _finish);auto it = pos + 1;while (it != end()){*(it - 1) = *it;it++;}_finish--;return pos;}

對于erase刪除數據在vector中就是需要挪動數據，直接將需要刪除的數據覆蓋，將后面的數據往前挪，最后返回被刪除元素的位置。在進行刪除動作之前需要進行斷言，不可越界訪問。

尾刪：pop_back()：刪除最后一個元素

vec.pop_back(); // vec: {1, 5, 2, 3, 4}

模擬實現：

如果先實現好erase函數，pop_back函數就很好寫了。

void pop_back(){/*if(_finish != _start)--_finish;*/erase(end());}

vector的使用就介紹到這里啦，這也是常用的函數，需要了解更多可以查看vector文檔來學習，如果你已經了解string類，想必vector也手到擒來，string類和STL的用法相似，學會其中一種，再去學習其它STL就比較容易。?