vector
1. vector介紹
- vector文檔
- vector其實就是一個順序表，它表示可變大小數組的序列容器。
- 像數組一樣，可以使用下標+
[]來訪問vector的元素，和數組一樣高效；甚至，它的大小是可以動態改變的，其大小由容器自動處理。- 在底層上，vector使用動態分配空間來儲存元素。當新元素插入，原空間不夠時，需要重新分配一塊連續的空間來增加存儲空間，做法是開辟大一點的空間，然后將原內容拷貝過來，再釋放原空間，此舉的時間成本相對較高。
- vector會額外分配一些空間，以適應可能的增長，實際的存儲空間可能比需要的空間更大。不同的STL庫的實現采取不同的策略。
- vector的成員變量和string不同，string是兩個整型存size和capacity，一個char指針指向動態開辟的空間；而vector是三個迭代器（底層類似于指針），分別是開頭的迭代器、最后一個元素下一個位置的迭代器、開辟的空間的最末端的迭代器。
- string是管理字符串的類，那么vector< char>實例化為char是否能替代string呢？
當然不可以，因為string后都有’\0’，可以更好和C的字符串對接，另外string的接口也更加豐富，可以更好的管理字符串。
2. vector的常用接口
vector的許多接口中有很多別名：
相比于string，vector的接口數量就顯得很少了，下面我們看看vector常用的接口。
-
構造函數(constructor)
(constructor) 功能 explicit vector (const allocator_type& alloc = allocator_type());默認構造函數 explicit vector (size_type n, const value_type& val = value_type(),const allocator_type& alloc = allocator_type());用n個val值初始化 template <class InputIterator>vector (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());用迭代器初始化（可以允許其他類型作為參數初始化） vector (const vector& x);拷貝構造函數 vector<int> v1; vector<int> v2(3, 2); int nums[] = { 1,2,3 }; vector<int> v3(arr, arr + 3); vector<int> v4(v3); -
容量操作
函數 功能 size_type size(); const返回有效元素個數 size_type capacity(); const返回實際空間大小 bool empty(); const判斷是否為空 void resize (size_type n, value_type val = value_type());改變有效元素個數 void reserve (size_type n);改變空間大小 補充：
- resize：
當n小于有效元素個數時，會將n之后的所有元素刪除，只保留從頭到n位置的元素；
當n大于有效元素個數，卻小于實際空間大小時，會在最后一個有效元素后填充值val，直到n位置；
當n大于實際空間大小時，會開辟空間，然后在最后一個有效元素后填充值val，直到n位置。 - reserve：
當n大于實際空間大小時，開辟空間。其余任何情況不做處理。
- resize：
-
迭代器
函數 功能 iterator begin();const_iterator begin() const;返回容器開頭的位置的迭代器 iterator end();const_iterator end() const;返回容器最后一個有效元素的下一個位置的迭代器 reverse_iterator rbegin();const_reverse_iterator rbegin() const;返回容器最后一個有效元素的位置的迭代器 reverse_iterator rend();const_reverse_iterator rend() const;返回容器開頭的前一個位置的迭代器 
-
訪問元素
函數 功能 reference operator[] (size_type n);const_reference operator[] (size_type n) const;訪問下標為n的元素 reference at (size_type n);const_reference at (size_type n) const;訪問下標為n的元素 vector<int> v(3, 2); cout << v[0] << endl; cout << v.at(1) << endl; -
修改操作
函數 功能 void push_back (const value_type& val);尾插一個值 void pop_back();尾刪一個值 insert在某個位置插入元素 erase刪除某個位置的元素 void swap (vector& x);交換兩個vector對象 void clear();清空有效元素
3. 模擬實現vector類（部分接口）
#include<iostream>
#include<assert.h>using namespace std;namespace Myspace
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;vector(){ }vector(size_t n, const T& value = T()){// 開空間_start = new T[n];_finish = _start + n;_endofstorage = _finish;// 放數據for (auto& e : *this){e = value;}}vector(int n, const T& value = T()){// 開空間_start = new T[n];_finish = _start + n;_endofstorage = _finish;// 放數據for (auto& e : *this){e = value;}}vector(long n, const T& value = T()){// 開空間_start = new T[n];_finish = _start + n;_endofstorage = _finish;// 放數據for (auto& e : *this){e = value;}}template<typename InputIterator>vector(InputIterator first, InputIterator last){/*int len = last - first;_start = new T[n];_finish = _start + len;_endofstorage = _finish;for (auto& e : *this){e = *first;first++;}*/_start = new T[last - first];for (size_t i = 0; i < last - first; i++){_start[i] = first[i];}_finish = _start + (last - first);_endofstorage = _start + (last - first);}vector(const vector& v){_start = new T[v.capacity()];for (size_t i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_endofstorage = _start + capacity();}~vector(){if (_start){delete[] _start;_start = _finish = _endofstorage = nullptr;}}vector<T>& operator= (vector<T> v){swap(v);return *this;}//---------------------------------- 迭代器 ---------------------------------------//iterator begin(){return _start;}const_iterator begin() const{return _start;}iterator end(){return _finish;}const_iterator end() const{return _finish;}//---------------------------------- 容量 ---------------------------------------//size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}bool empty() const{return _start == _finish;}void reserve(size_t n){if (n > capacity()){int len = size();iterator tmp = new T[n];// 這里拷貝數據不能用memcpy，如果T需要深拷貝，memcpy只是淺拷貝if (_start){for (size_t i = 0; i < n; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + len;_endofstorage = _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++;}}}//---------------------------------- 修改 ---------------------------------------//void push_back(const T value){if (_finish == _endofstorage){reserve(_start == _endofstorage ? 4 : capacity() * 2);}*_finish = value;++_finish;}void pop_back(){assert(_start != _finish);--_finish;}iterator insert(iterator pos, const T& value){assert(pos >= _start && pos <= _finish);if (_finish == _endofstorage){int len = pos - _start; // 防止擴容后迭代器失效reserve(_start == _endofstorage ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}_finish++;*pos = value;return pos;}iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator it = pos + 1;while (it != _finish){*(it - 1) = *it;++it;}--_finish;return pos;}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}private:iterator _start = nullptr; // 給缺省值，在構造函數的初始化列表中自動初始化iterator _finish = nullptr;iterator _endofstorage = nullptr;};
}
注意：
- 構造函數
vector(int n, const T& value = T())接口需要重載多個（int/size_t/long），以防止創建對象時（vector<int> v(2,3);）編譯器自動匹配到vector(InputIterator first, InputIterator last)這個接口。
原因：編譯器總會選擇最匹配的接口。 - 在擴容時拷貝數據的時候，不要使用memcpy（上述代碼的第151行），原因如下：
如果模板實例化為string，那么此時就相當于memcpy(string1, string2, size)，將兩個string類memcpy，一定是淺拷貝，因為string類本身有個char*的指針，需要動態開辟空間，memcpy僅僅是將兩個指針指向了同一塊空間，并沒有開辟新的空間。
直接賦值即可，賦值會調用string自己的賦值運算符重載，它自己會實現深拷貝。
不止是string，其他任何動態管理空間的類都是如此。
4. 迭代器失效
-
迭代器的作用：
迭代器就是為了不管各個容器的底層如何實現，都能夠使用算法。其底層實際是個指針，或是對指針的封裝，比如string和vector的迭代器就是char* 和 T*。 -
迭代器失效：
當迭代器底層所指向的空間被銷毀了，還依舊使用該迭代器，那么就會造成野指針的問題，后果是程序崩潰。在VS2022下直接報錯崩潰，在Linux下可能不會報錯，因此對于程序員來說，避免迭代器失效是必須的。 -
可能引起迭代器失效的場景：
- 擴容操作
#include <iostream> using namespace std; #include <vector> int main() {vector<int> v{1,2,3,4,5,6};auto it = v.begin();v.resize(100, 8);v.reserve(100);v.insert(v.begin(), 0);v.push_back(8);v.assign(100, 8);while(it != v.end()){cout<< *it << " " ;++it;}cout<<endl;return 0; }以上五個接口可能會導致迭代器it失效，原因：
使用接口改變底層空間時，可能會擴容，而vector的擴容邏輯是：開辟一塊新空間，將原數據拷貝至新空間，然后釋放舊空間。擴完容之后底層地址空間就變了，而外部的迭代器it依舊指向原來已經被釋放的空間，對迭代器再次操作時，就是對已經釋放的空間進行操作，會引起代碼奔潰。- 刪除指定位置元素 — erase
#include <iostream> using namespace std; #include <vector> int main() {int a[] = { 1, 2, 3, 4 };vector<int> v(a, a + sizeof(a) / sizeof(int));// 使用find查找4所在位置的iteratorvector<int>::iterator pos = find(v.begin(), v.end(), 3);// 刪除pos位置的數據，導致pos迭代器失效。v.erase(pos);cout << *pos << endl; // 此處會導致非法訪問return 0; }上述代碼導致迭代器失效的原因：
erase刪除pos位置的元素，后面的元素會往前挪動，理論上沒有產生擴容，底層地址空間就不會改變，迭代器不應該失效。但是如果pos位置是最后一個元素，刪除之后，pos位置就成了end()，是最后一個有效元素的下一個位置，此位置不屬于有效數據的區間，此迭代器就失效了。在VS中再對pos迭代器進行操作，程序就會奔潰。 -
解決辦法：
完成擴容或刪除操作之后，給迭代器重新賦值即可。 -
Linux下，g++編譯器對迭代器失效的檢測并不是很嚴格，處理也沒有VS下那么極端。
-
vs下迭代器失效
-
g++下迭代器失效
由此可見，SGI版本的STL（Linux下的g++編譯），迭代器失效后代碼不一定會奔潰（如果迭代器不在begin和end的范圍內也會奔潰），但是它的結果一定不正確。
-
-
不僅vector存在迭代器失效的問題，string也有迭代器失效的問題，因此我們在使用STL時，一定要小心迭代器失效！
 函數支持變長參數列表)
