---

前言

👧個人主頁：@小沈YO.
😚小編介紹：歡迎來到我的亂七八糟小星球🌝
📋專欄：C++ 心愿便利店
🔑本章內容：vector
記得 評論📝 +點贊👍 +收藏😽 +關注💞哦~

---

提示：以下是本篇文章正文內容，下面案例可供參考

一、STL簡介

1.1 什么是STL

STL(standard template libaray-標準模板庫)：是C++標準庫的重要組成部分，不僅是一個可復用的組件庫，而且是一個包羅數據結構與算法的軟件框架

1.2 STL的六大組件

二、vector的介紹及使用

2.1 vector的介紹

vector的文檔介紹

• vector是表示可變大小數組的序列容器。
• 就像數組一樣，vector也采用的連續存儲空間來存儲元素。也就是意味著可以采用下標對vector的元素進行訪問，和數組一樣高效。但是又不像數組，它的大小是可以動態改變的，而且它的大小會被容器自動處理。
• 本質講，vector使用動態分配數組來存儲它的元素。當新元素插入時候，這個數組需要被重新分配大小為了增加存儲空間。其做法是，分配一個新的數組，然后將全部元素移到這個數組。就時間而言，這是一個相對代價高的任務，因為每當一個新的元素加入到容器的時候，vector并不會每次都重新分配大小。
• vector分配空間策略：vector會分配一些額外的空間以適應可能的增長，因為存儲空間比實際需要的存儲空間更大。不同的庫采用不同的策略權衡空間的使用和重新分配。但是無論如何，重新分配都應該是對數增長的間隔大小，以至于在末尾插入一個元素的時候是在常數時間的復雜度完成的。
• 因此，vector占用了更多的存儲空間，為了獲得管理存儲空間的能力，并且以一種有效的方式動態增長。
• 與其它動態序列容器相比（deque, list and forward_list）， vector在訪問元素的時候更加高效，在末尾添加和刪除元素相對高效。對于其它不在末尾的刪除和插入操作，效率更低。比起list和forward_list統一的迭代器和引用更好。

2.2 vector的使用

2.2.1 vector的定義

(constructor)構造函數聲明	接口說明
vector()（重點）	無參構造
vector（size_type n, const value_type& val = value_type()）	構造并初始化n個val
vector (const vector& x); （重點）	拷貝構造
vector (InputIterator first, InputIterator last);	使用迭代器進行初始化構造

void test_vector1()
{//構造函數vector<int> v;//無參構造vector<int> v1(5, 1);vector<int> v2(v1.begin(), v1.end());string s1 = "hello world";vector<int> v3(s1.begin(), s1.end());//隱式類型轉換vector<int> v4(v3);//拷貝構造
}

2.2.2 vector iterator 的使用

iterator的使用	接口說明
begin + end（重點）	獲取第一個數據位置的iterator/const_iterator,獲取最后一個數據的下一個位置的iterator/const_iterator
rbegin + rend	獲取最后一個數據位置的reverse_iterator,獲取第一個數據前一個位置的reverse_iterator

void test_vector1()
{vector<int> v2(v1.begin(), v1.end());string s1 = "hello world";vector<int> v3(s1.begin(), s1.end());//隱式類型轉換vector<int> v4(v3);//拷貝構造//1.iteratorvector<int>::iterator it = v3.begin();while (it != v3.end()){cout << *it << " ";it++;}cout << endl;//2.operator[]for (size_t i = 0; i < v2.size(); i++){cout << v2[i] << " ";}cout << endl;//3.范圍forfor (auto e : v4){cout << e << " ";}cout << endl;
}

2.2.3 vector 空間增長問題

容量空間	接口說明
size	獲取數據個數
capacity	獲取容量大小
empty	判斷是否為空
resize（重點）	改變vector的size
reserve （重點）	改變vector的capacity

// 測試vector的默認擴容機制
void TestVectorExpand()
{size_t sz;vector<int> v;sz = v.capacity();cout << "making v grow:\n";for (int i = 0; i < 100; ++i) {v.push_back(i);if (sz != v.capacity()) {sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}

• capacity的代碼在vs和g++下分別運行會發現，vs下capacity是按1.5倍增長的，g++是按2倍增長的。這個問題經常會考察，不要固化的認為，vector增容都是2倍，具體增長多少是根據具體的需求定義的。vs是PJ版本STL，g++是SGI版本STL。

• reserve只負責開辟空間，如果確定知道需要用多少空間，reserve可以緩解vector增容的代價缺陷問題。

// 如果已經確定vector中要存儲元素大概個數，可以提前將空間設置足夠
// 就可以避免邊插入邊擴容導致效率低下的問題了
void TestVectorExpandOP()
{vector<int> v;size_t sz = v.capacity();v.reserve(100); // 提前將容量設置好，可以避免一遍插入一遍擴容cout << "making bar grow:\n";for (int i = 0; i < 100; ++i) {v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}

• resize在開空間的同時還會進行初始化，影響size

void test_vector3()
{vector<int> v1;cout << v1.max_size() << endl;size_t sz;vector<int> v;//v.reserve(100);   ---> size=0,capacity=100v.resize(100);      ---> size=100,capacity=100//for (size_t i = 0; i < v.size(); i++)//當寫成這種形式用reserve(100)是不會進入循環的因為v.size()返回值是0for (size_t i = 0; i < 100; i++){v[i] = i;//斷言在release下不起作用//雖然空間開出來了100但是不能訪問，因為operator[]里面加了斷言，斷言訪問的下標必須是小于size的,大于size就越界了,所以只能訪問[0，size-1]的數據,但是reverse(100)--->size=0}for (auto e : v){cout << e << " ";}cout << endl;
}

上面的代碼用reserve(100)雖然給 v 提前開了 100 個空間，但是 v 中的有效元素個數size還是 0，所以不能直接通過下標去訪問 vector 對象中的每一個元素，因為 operator[ ] 實現中的第一步就是檢查下標的合理性，防止越界訪問，執行 assert(pos < _size)，而此時 _size 是 0，就會越界報錯。而把 reserve 改成 resize 就可以正常運行，因為 resize 會改變 _size 的大小。

2.2.4 vector 增刪查改

vector增刪查改	接口說明
push_back（重點）	尾插
pop_back （重點）	尾刪
find	查找 - - -（注意這個是算法模塊實現，不是vector的成員接口）
insert	在position之前插入val
erase	刪除position位置的數據
swap	交換兩個vector的數據空間
operator[] （重點）	像數組一樣訪問

vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.insert(v.begin(), 0);auto it=find(v.begin(), v.end(), 3);尋找--->注意這個是算法模塊實現，不是vector的成員接口if (it != v.end()){v.insert(it, 30);插入}for (auto e : v){cout << e << " ";}cout << endl;it = find(v.begin(), v.end(), 3);if (it != v.end()){v.erase(it);刪除}for (auto e : v){cout << e << " ";}cout << endl;cout << v.size() << endl;cout << v.capacity() << endl;v.clear();v.shrink_to_fit();//縮容不建議用cout << v.size() << endl;cout << v.capacity() << endl;
}

三、vector模擬實現

3.1 成員變量

class vector
{
public:typedef T* iterator;typedef const T* const_iterator;
private:iterator _start;iterator _finish;iterator _end_of_storage;
};

3.2 成員函數

3.2.1 構造函數

//無參構造
vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}
//帶參構造并初始化
vector(int n, const T& val  = T())
{reserve(n);for (int i = 0; i < n; i++){push_back(val);}
}vector(size_t n, const T& val = T())
{rserve(n);for (size_t i = 0; i < n; i++){push_back(val);}
}
//迭代器區間初始化
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);first++;}
}

• 無參的構造并不陌生
• 帶參的構造并初始化為什么要寫兩個？

因為如果不單獨提供一個 vector(int n, const T& val = T())；代碼vector v1(10, 1) 會走最匹配的，即和迭代器區間初始化函數匹配（迭代器區間初始化采用的是函數模板），但是我們希望它走 vector(size_t n, const T& val = T()) 構造函數，可是 10 是 int 型，和 size_t 不匹配上（只會走最匹配的），因此就會去和迭代器區間初始化函數進行匹配，InputIterator 就會被實例化成 int 型，函數中會對 int 型解引用，就會報錯

• 迭代器區間初始化采用的是函數模板，因為它可能使用不同類型的迭代器。

3.2.2 拷貝構造函數

vector(const vector<T>& v)//const對象:_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{reserve(v.capacity());for (auto& e : v)//這里加上&防止T是個大對象拷貝代價大{push_back(e);}
}

3.2.3 operator=

vector<T> operator=(vector<T> tmp)
{swap(tmp);return *this;
}
void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}

3.2.4 size

size_t size() const
{return _finish - _start;
}

3.2.5 capacity

size_t capacity() const
{return _end_of_storage - _start;
}

3.2.6 reserve(注意memcpy的拷貝方式)

void reserve(size_t n)
{if (n > capacity()){T* tmp = new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * sz);delete[] _start;}_start = tmp;_finish = _start + size();_end_of_storage = _start + cp;}
}
_________________________________________________________________________________________
void reserve(size_t n)
{if (n > capacity()){T* tmp = new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * sz);delete[] _start;}_finish = tmp + size();_start = tmp;_end_of_storage = _start + cp;}
}
_________________________________________________________________________________________
void reserve(size_t n)
{if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * sz);delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}
}

注意：第一種代碼的寫法是不正確的，因為當開辟新空間tmp，將_start中的數據拷貝到tmp中，釋放原空間，將_start指針指向新空間，所以運行代碼_finish = _start + size();時要先調用size()，而size=_finish - _start，其中_finish是nullptr（構造時初始化），而_start并不是nullptr（此時是tmp），所以我們預期中的size并不是等于0，而是size=0-_start，所以_finish=_start+0-_start=0
解決方式：

• 寫成_finish = tmp + size(); _start = tmp;注意先后順序，如果寫成 _start = tmp; _finish = tmp + size(); 先調用size=_finish-_start=0-tmp;最終_finish=tmp+0-tmp還是沒有解決問題，同樣也不能寫成_finish = _start + size(); _start = tmp; 此時的_start=0，所以_finish=0+0=0，也是不對的
• 第一種的解決方式是可以的但是可讀性太差，順序不對就導致錯誤，所以可以提前用一個變量存儲size()的返回值，size_t sz = size();此時就不會因為順序報錯啦

上面這種擴容邏輯，當 T 是內置類或者是不需要進行深拷貝的自定義類型來說，是可以的。但是當 T 是需要進行深拷貝的類型時，上述這種擴容方式就會出現問題。下述代碼以 vector 為例：

void reserve(size_t n)
{if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * sz);delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}
}
void test_vector5()
{vector<string> s;s.push_back("11111111111111111111");s.push_back("11111111111111111111");s.push_back("11111111111111111111");s.push_back("11111111111111111111");s.push_back("11111111111111111111");for (auto e : s){cout << e << " ";}cout << endl;
}

通過上圖可以明顯地觀察到當插入4個字符串時是沒有問題的但是當插入第五個字符串時就會出現問題，顯然是擴容中出現了問題，上述代碼用 memcpy 將舊空間的數據拷貝到新空間，那么新舊空間中存儲的 string 對象指向同一個堆區上的字符串空間，接著在執行 delete[] _start; 銷毀舊空間的時候，由于該 _start 是一個 string* 的指針，所以會先調用 string 的析構函數，將對象中申請的空間釋放，也就是釋放 _str 指向的空間，然后再去調用 operator delete 函數釋放 string 對象的空間。所以新空間中存儲的 string 對象就出現了問題，因為它的成員變量 _str 指向的空間已經被釋放了。
顯然 memcpy 執行的是淺拷貝，只需要修改成tmp[i] = _start[i]; 這樣會調用 string 對象的賦值運算重載，進行深拷貝。

void reserve(size_t n)
{if (n > capacity()){size_t sz = size();T* tmp = new T[n];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;_end_of_storage = _start + n;}
}

3.2.7 resize

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;}}
}

3.2.8 operator[]

//讀寫
T& operator[](size_t pos)
{assert(pos < size());return _start[pos];
}
//只能讀
const T& operator[](size_t pos) const
{assert(pos < size());return _start[pos];
}

3.2.9 insert（涉及迭代器失效）

void insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);//檢查容量}iterator end = _finish - 1;//插入數據while (end >= pos){*(end + 1) = *end;end--;}*pos = x;_finish++;
}
___________________________________________________________________________________________-
void insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){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 的時候，會引發一個問題 ---- 迭代器失效：如果失效就不能再使用這個迭代器，如果使用了，結果未定義。
首先pos 是一個迭代器，在 pos 位置插入一個數據時，要在插入數據之前先檢查容量，進行擴容，但是執行了擴容邏輯后，_start、_finish、_end_of_storage 都指向了新空間，舊空間被釋放了，且 pos 指向的卻還是原來空間中的某個位置，此時 pos 就變成了野指針，再去 pos 指向的位置插入數據時，就會造成非法訪問就像第一種所寫的代碼（總而言之就是擴容導致pos失效）
解決方式：為了解決迭代器失效的問題，可以在檢查容量擴容之前先保存一下pos的相對位置，在進行擴容釋放舊空間指向新空間邏輯后，更新一下pos指針（總而言之就是更新pos）

iterator insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){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++;return pos
}
void test_vector3()
{vector<int>v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);vector<int>::iterator it = v.begin()+2;v.insert(it, 30);for (auto e : v){cout << e << " ";}cout << endl;
}

對于上述代碼調用insert，雖然更新了 pos，但是由于是傳值，形參 pos 的更新，并不會改變實參的 it，所以insert后it可能會失效。
解決上述問題很簡單直接把形參的 pos 變成引用不就可以嗎？這樣形參pos的改變也就使得實參it改變。
這樣是可以的解決了傳值傳參的問題，但是也會引發諸多問題，例如：v.insert(v.begin(), 30);當運行這段代碼時就會報錯，因為實參具有常性（begin()是傳值返回，會產生一個臨時變量，臨時變量具有常性），&必須要傳變量不能傳帶const屬性的值。
所以形參 pos 用引用的話，就需要加 const 進行修飾。但是如果用 const 進行修飾，那在函數內部就不能對 pos 進行更新，所以形參 pos 不能用引用，可以采用返回值的方式，將更新后的 pos 返回。

3.2.10 erase（涉及迭代器失效）

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

根據上述insert實現中迭代器失效是因為擴容引起的，但是erase 只是刪除 pos 位置元素，pos 位置之后的元素往前覆蓋，沒有導致空間的改變，理論上迭代器不會失效
但是根據上述代碼，如果 pos 剛好是最后一個元素，刪完之后 pos 剛好是 _finish 的位置，而 _finish 位置是沒有元素的，那么 pos 就失效了。為了迭代器失效問題，還是可以采用返回值的方式，返回 pos 下一個位置元素的迭代器。

3.2.11 push_back

void push_back(const T& x)
{if (_finish == _end_of_storage){reserve( capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;            _finish++;                
}
__________________________________________________________________________________
//push_back可以直接復用insert
void push_back(const T& x)
{insert(end(), x);
}

3.2.12 pop_back

void pop_back()
{erase(--end());
}

3.2.13 迭代器

iterator begin()
{return _start;
}iterator end()
{return _finish;
}const_iterator begin() const
{return _start;
}
const_iterator end() const
{return _finish;
}vector<int>::iterator it = v.begin();
while (it != v.end())
{*it *= 10;cout << *it << " ";it++;
}
cout << endl;
for (auto e : v)
{cout << e << " ";
}cout << endl;
}

---