2.vector的使用

1.vector的定義

?2.vector iterator的使用

?

?注意：所有的迭代器區(qū)間都是左閉右開，且不光可以傳vector的迭代器，還可以傳其他類型的迭代器，只要類型可以匹配。

下面是代碼演示

void Print(const vector<int>& v)
{// const對(duì)象使用const迭代器進(jìn)行遍歷打印vector<int>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;
}

3. vector 空間增長問題

?

// 如果已經(jīng)確定vector中要存儲(chǔ)元素大概個(gè)數(shù)，可以提前將空間設(shè)置足夠
// 就可以避免邊插入邊擴(kuò)容導(dǎo)致效率低下的問題了
void TestVector()
{vector<int> v;size_t sz = v.capacity();v.reserve(100); // 提前將容量設(shè)置好，可以避免一遍插入一遍擴(kuò)容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';}}
}

4.vector 增刪查改

?重要的函數(shù)接口參數(shù)

void push_back (const value_type& val);void pop_back();template <class InputIterator, class T>   
InputIterator find (InputIterator first, InputIterator last, const T& val);iterator insert (iterator position, const value_type& val);
void insert (iterator position, size_type n, const value_type& val);iterator erase (iterator position);iterator erase (iterator first, iterator last);

3.vector 迭代器失效問題（重點(diǎn)）

迭代器的使用特別廣泛，迭代器的主要作用就是讓算法能夠不用關(guān)心底層數(shù)據(jù)結(jié)構(gòu)，其底層實(shí)際就是一個(gè)指針，或者是對(duì)指針進(jìn)行了封裝，比如：vector的迭代器就是原生態(tài)指針T* 。因此迭代器失效，實(shí)際就是迭代器底層對(duì)應(yīng)指針?biāo)赶虻目臻g被銷毀了，而使用一塊已經(jīng)被釋放的空間，造成的后果是程序崩潰(即如果繼續(xù)使用已經(jīng)失效的迭代器，程序可能會(huì)崩潰)。

1. 會(huì)引起其底層空間改變的操作

比如：resize、reserve、insert、assign、push_back等，都有可能造成迭代器失效

#include <iostream>
using namespace std;
#include <vector>
int main()
{vector<int> v{1,2,3,4,5,6};auto it = v.begin();
// 將有效元素個(gè)數(shù)增加到100個(gè)，多出的位置使用8填充，操作期間底層會(huì)擴(kuò)容// v.resize(100, 8);// reserve的作用就是改變擴(kuò)容大小但不改變有效元素個(gè)數(shù)，操作期間可能會(huì)引起底層容量改變// v.reserve(100);// 插入元素期間，可能會(huì)引起擴(kuò)容，而導(dǎo)致原空間被釋放// v.insert(v.begin(), 0);// v.push_back(8);// 給vector重新賦值，可能會(huì)引起底層容量改變v.assign(100, 8);while(it != v.end()){cout<< *it << " " ;++it;}cout<<endl;return 0;
}

2.指定位置元素的刪除操作--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查找3所在位置的iteratorvector<int>::iterator pos = find(v.begin(), v.end(), 3);// 刪除pos位置的數(shù)據(jù)，導(dǎo)致pos迭代器失效。v.erase(pos);cout << *pos << endl; // 此處會(huì)導(dǎo)致非法訪問return 0;
}

#include <iostream>
using namespace std;
#include <vector>
int main()
{vector<int> v{ 1, 2, 3, 4 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)v.erase(it);++it;} return 0;
}int main()
{vector<int> v{ 1, 2, 3, 4 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)it = v.erase(it);    //返回一個(gè)迭代器，指向刪除數(shù)據(jù)的下一個(gè)位置else++it;}return 0;
}

第一個(gè)代碼是錯(cuò)誤的，會(huì)造成迭代器失效，且其刪除邏輯是不對(duì)的。以上面的代碼為例，當(dāng)程序刪除“2”以后，pos位置會(huì)變成“3”，然后it++,迭代器就指向了4，就錯(cuò)過了對(duì)3的判斷，且最后一個(gè)是偶數(shù)4，刪除以后，迭代器會(huì)超過_finish,導(dǎo)致it永遠(yuǎn)不會(huì)==v.end()。

3. Linux下，g++編譯器對(duì)迭代器的處理情況。

// 1. 擴(kuò)容之后，迭代器已經(jīng)失效了，程序雖然可以運(yùn)行，但是運(yùn)行結(jié)果已經(jīng)不對(duì)了
int main()
{vector<int> v{1,2,3,4,5};auto it = v.begin();cout << "擴(kuò)容之前，vector的容量為: " << v.capacity() << endl;// 通過reserve將底層空間設(shè)置為100，目的是為了讓vector的迭代器失效 v.reserve(100);cout << "擴(kuò)容之后，vector的容量為: " << v.capacity() << endl;// 經(jīng)過上述reserve之后，it迭代器肯定會(huì)失效，在vs下程序就直接崩潰了，但是linux下不會(huì)// 雖然可能運(yùn)行，但是輸出的結(jié)果是不對(duì)的while(it != v.end()){cout << *it << " ";++it;}cout << endl;return 0;
}
輸出：
擴(kuò)容之前，vector的容量為: 5
擴(kuò)容之后，vector的容量為: 100
0 2 3 4 5 409 1 2 3 4 5// 2. erase刪除任意位置代碼后，linux下迭代器并沒有失效
// 因?yàn)榭臻g還是原來的空間，后序元素往前搬移了，it的位置還是有效的
#include <vector>
#include <algorithm>
int main()
{vector<int> v{1,2,3,4,5};vector<int>::iterator it = find(v.begin(), v.end(), 3);v.erase(it);
cout << *it << endl;while(it != v.end()){cout << *it << " ";++it;}cout << endl;return 0;
}程序可以正常運(yùn)行，并打印：
4
4 5// 3: erase刪除的迭代器如果是最后一個(gè)元素，刪除之后it已經(jīng)超過end
// 此時(shí)迭代器是無效的，++it導(dǎo)致程序崩潰
int main()
{vector<int> v{1,2,3,4,5};// vector<int> v{1,2,3,4,5,6};auto it = v.begin();while(it != v.end()){if(*it % 2 == 0)v.erase(it);++it;}for(auto e : v)cout << e << " ";cout << endl;return 0;
}

從上述三個(gè)例子中可以看到：Linux下，g++編譯器對(duì)迭代器失效的檢測(cè)并不是非常嚴(yán)格，處理也沒有vs下極端，SGI STL中，迭代器失效后，代碼并不一定會(huì)崩潰，但是運(yùn)行結(jié)果肯定不對(duì)，如果it不在begin和end范圍內(nèi)，肯定會(huì)崩潰的。

二.vector深度剖析及模擬實(shí)現(xiàn)

?

1.std::vector的核心框架接口的模擬實(shí)現(xiàn)

#pragma once#include <iostream>
using namespace std;
#include <assert.h>namespace Kevin
{template<class T>class vector{public:// Vector的迭代器是一個(gè)原生指針typedef T* iterator;typedef const T* const_iterator;///// 構(gòu)造和銷毀vector(): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){}vector(size_t n, const T& value = T()): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){reserve(n);while (n--){push_back(value);}}/** 理論上將，提供了vector(size_t n, const T& value = T())之后* vector(int n, const T& value = T())就不需要提供了，但是對(duì)于：* vector<int> v(10, 5);* 編譯器在編譯時(shí)，認(rèn)為T已經(jīng)被實(shí)例化為int，而10和5編譯器會(huì)默認(rèn)其為int類型* 就不會(huì)走vector(size_t n, const T& value = T())這個(gè)構(gòu)造方法，* 最終選擇的是：vector(InputIterator first, InputIterator last)* 因?yàn)榫幾g器覺得區(qū)間構(gòu)造兩個(gè)參數(shù)類型一致，因此編譯器就會(huì)將InputIterator實(shí)例化為int* 但是10和5根本不是一個(gè)區(qū)間，編譯時(shí)就報(bào)錯(cuò)了* 故需要增加該構(gòu)造方法*/vector(int n, const T& value = T()): _start(new T[n]), _finish(_start+n), _endOfStorage(_finish){for (int i = 0; i < n; ++i){_start[i] = value;}}// 若使用iterator做迭代器，會(huì)導(dǎo)致初始化的迭代器區(qū)間[first,last)只能是vector的迭代器// 重新聲明迭代器，迭代器區(qū)間[first,last)可以是任意容器的迭代器template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}vector(const vector<T>& v): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){reserve(v.capacity());iterator it = begin();const_iterator vit = v.cbegin();while (vit != v.cend()){*it++ = *vit++;}_finish = it;}vector<T>& operator=(vector<T> v){swap(v);return *this;}~vector(){if (_start){delete[] _start;_start = _finish = _endOfStorage = nullptr;}}/// 迭代器相關(guān)iterator begin(){return _start;}iterator end(){return _finish;}const_iterator cbegin() const{return _start;}const_iterator cend() const{return _finish;}//// 容量相關(guān)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()){size_t oldSize = size();// 1. 開辟新空間T* tmp = new T[n];// 2. 拷貝元素// 這里直接使用memcpy會(huì)有問題嗎？同學(xué)們思考下//if (_start)//	memcpy(tmp, _start, sizeof(T)*size);if (_start){for (size_t i = 0; i < oldSize; ++i)tmp[i] = _start[i];// 3. 釋放舊空間delete[] _start;}_start = tmp;_finish = _start + oldSize;_endOfStorage = _start + n;}}void resize(size_t n, const T& value = T()){// 1.如果n小于當(dāng)前的size，則數(shù)據(jù)個(gè)數(shù)縮小到nif (n <= size()){_finish = _start + n;return;}// 2.空間不夠則增容if (n > capacity())reserve(n);// 3.將size擴(kuò)大到niterator it = _finish;_finish = _start + n;while (it != _finish){*it = value;++it;}}///// 元素訪問T& operator[](size_t pos) { assert(pos < size());return _start[pos]; }const T& operator[](size_t pos)const { assert(pos < size());return _start[pos]; }T& front(){return *_start;}const T& front()const{return *_start;}T& back(){return *(_finish - 1);}const T& back()const{return *(_finish - 1);}/// vector的修改操作void push_back(const T& x) { insert(end(), x); }void pop_back() { erase(end() - 1); }void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}iterator insert(iterator pos, const T& x){assert(pos <= _finish);// 空間不夠先進(jìn)行增容if (_finish == _endOfStorage){//size_t size = size();size_t newCapacity = (0 == capacity()) ? 1 : capacity() * 2;reserve(newCapacity);// 如果發(fā)生了增容，需要重置pospos = _start + size();}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}// 返回刪除數(shù)據(jù)的下一個(gè)數(shù)據(jù)// 方便解決:一邊遍歷一邊刪除的迭代器失效問題iterator erase(iterator pos){// 挪動(dòng)數(shù)據(jù)進(jìn)行刪除iterator begin = pos + 1;while (begin != _finish) {*(begin - 1) = *begin;++begin;}--_finish;return pos;}private:iterator _start;		// 指向數(shù)據(jù)塊的開始iterator _finish;		// 指向有效數(shù)據(jù)的尾iterator _endOfStorage;  // 指向存儲(chǔ)容量的尾};
}

2.?使用memcpy拷貝問題

int main()
{bite::vector<bite::string> v;v.push_back("1111");v.push_back("2222");v.push_back("3333");return 0;
}

假設(shè)模擬實(shí)現(xiàn)的vector中的reserve接口中，使用memcpy進(jìn)行的拷貝,上面的代碼會(huì)有什么問題嗎？

?

?

如果拷貝的是自定義類型的元素，memcpy既高效又不會(huì)出錯(cuò)，但如果拷貝的是自定義類型元素，并且自定義類型元素中涉及到資源管理時(shí)，就會(huì)出錯(cuò)，因?yàn)閙emcpy的拷貝實(shí)際是淺拷貝。

?結(jié)論：如果對(duì)象中涉及到資源管理時(shí)，千萬不能使用memcpy進(jìn)行對(duì)象之間的拷貝，因?yàn)閙emcpy是 淺拷貝，否則可能會(huì)引起內(nèi)存泄漏甚至程序崩潰。

3.動(dòng)態(tài)二維數(shù)組理解

vector<vector<int>> vv(n);

完成元素填充后，如下圖：