W...Y的主頁 😊
代碼倉庫分享?💕
🍔前言:
我們學習了STL中的string以及其所有重要接口并進行了模擬實現,但是STL中包含的內容不止于此。學習了string之后繼續學習STL中的vector,學習成本會大大降低,因為他們非現類似,現在就讓我們進入vector的世界中吧!
目錄
vector的介紹及使用
vector的介紹
vector的使用
?vector的定義
vector iterator 的使用
vector 空間增長問題
vector 增刪查改
??編輯
vector的深度剖析以及模擬實現
vector類的創建以及構造函數與析構函數
?迭代器相關模擬實現
?容量相關模擬實現
元素訪問相關模擬實現
vector的修改操作模擬實現
?vector 迭代器失效問題
賦值重載函數的模擬
vector的介紹及使用
vector的介紹
1. vector是表示可變大小數組的序列容器。
2. 就像數組一樣,vector也采用的連續存儲空間來存儲元素。也就是意味著可以采用下標對vector的元素進行訪問,和數組一樣高效。但是又不像數組,它的大小是可以動態改變的,而且它的大小會被容器自動處理。
3. 本質講,vector使用動態分配數組來存儲它的元素。當新元素插入時候,這個數組需要被重新分配大小為了增加存儲空間。其做法是,分配一個新的數組,然后將全部元素移到這個數組。就時間而言,這是一個相對代價高的任務,因為每當一個新的元素加入到容器的時候,vector并不會每次都重新分配大小。
4. vector分配空間策略:vector會分配一些額外的空間以適應可能的增長,因為存儲空間比實際需要的存儲空間更大。不同的庫采用不同的策略權衡空間的使用和重新分配。但是無論如何,重新分配都應該是對數增長的間隔大小,以至于在末尾插入一個元素的時候是在常數時間的復雜度完成的。
5. 因此,vector占用了更多的存儲空間,為了獲得管理存儲空間的能力,并且以一種有效的方式動態增長。
6. 與其它動態序列容器相比(deque, list and forward_list), vector在訪問元素的時候更加高效,在末尾添加和刪除元素相對高效。對于其它不在末尾的刪除和插入操作,效率更低。比起list和forward_list統一的迭代器和引用更好。
?
vector的使用
vector學習時一定要學會查看文檔:vector的文檔介紹,vector在實際中非常的重要,在實際中我們熟悉常見的接口就可以,下面列出了哪些接口是要重點掌握的。
?vector的定義
(constructor)構造函數聲明? | 接口說明 |
vector()(重點)? | 無參構造 |
vector(size_type n, const value_type& val = value_type()) | 構造并初始化n個val |
vector (const vector& x); (重點)? | 拷貝構造 |
vector (InputIterator first, InputIterator last);? | 使用迭代器進行初始化構造 |
這些vector定義參數全都是被typedef的內容,我們應該了解每個參數的含義:?下面演示以下如何使用構造函數與拷貝構造函數:
#define _CRT_SECURE_NO_WARNINGS#include <iostream>
using namespace std;
#include <vector>// vector的構造int TestVector1()
{// constructors used in the same order as described above:vector<int> first; // empty vector of intsvector<int> second(4, 100); // four ints with value 100vector<int> third(second.begin(), second.end()); // iterating through secondvector<int> fourth(third); // a copy of third// 下面涉及迭代器初始化的部分,我們學習完迭代器再來看這部分// the iterator constructor can also be used to construct from arrays:int myints[] = { 16,2,77,29 };vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));cout << "The contents of fifth are:";for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)cout << ' ' << *it;cout << '\n';return 0;
}
這里要強調一下迭代器構造函數,我們一般看到的類型是iterator類型的,而模板這里的模板參數給予的是inputiterator,并且給與class模板:
迭代器也是分類型的,不僅僅只有string、vector迭代器,還有其他的迭代器。所以我們可以傳入不同的迭代器對vector進行初始化操作。數組就是一個非常好的例子,在上述例子中我們也體現出不同迭代器對vector的初始化。?
vector iterator 的使用
iterator的使用 | 接口說明 |
begin +end(重點) | 獲取第一個數據位置的iterator/const_iterator, 獲取最后一個數據的下一個位置 的iterator/const_iterator |
rbegin + rend | 獲取最后一個數據位置的reverse_iterator,獲取第一個數據前一個位置的 reverse_iterator |
?迭代器都是左閉右開的區間。
void PrintVector(const vector<int>& v)
{// const對象使用const迭代器進行遍歷打印vector<int>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;
}void TestVector2()
{// 使用push_back插入4個數據vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);// 使用迭代器進行遍歷打印vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;// 使用迭代器進行修改it = v.begin();while (it != v.end()){*it *= 2;++it;}// 使用反向迭代器進行遍歷再打印// vector<int>::reverse_iterator rit = v.rbegin();auto rit = v.rbegin();while (rit != v.rend()){cout << *rit << " ";++rit;}cout << endl;PrintVector(v);
}
上述代碼我們使用迭代器對vector進行了正向與反向的遍歷打印,很好的說明了迭代器的使用。我們也可以使用[]重載進行遍歷,但這里我們不推薦使用,因為下標訪問對底層邏輯是數組的可以進行訪問,但是在后面的鏈表、樹中就不能了,我們要盡早習慣使用迭代器。
vector 空間增長問題
容量空間? | 接口說明 |
size | 獲取數據個數 |
capacity | 獲取容量大小 |
empty | 判斷是否為空 |
resize | 改變vector的size |
reserve | 改變vector的capacity |
vector這些接口與string是一模一樣,只要學會使用string的接口vector的這些接口也不再話下:
void TestVector3()
{vector<int> v;// set some initial content:for (int i = 1; i < 10; i++)v.push_back(i);v.resize(5);v.resize(8, 100);v.resize(12);cout << "v contains:";for (size_t i = 0; i < v.size(); i++)cout << ' ' << v[i];cout << '\n';
}// 測試vector的默認擴容機制
// vs:按照1.5倍方式擴容
// linux:按照2倍方式擴容
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';}}
}// 往vecotr中插入元素時,如果大概已經知道要存放多少個元素
// 可以通過reserve方法提前將容量設置好,避免邊插入邊擴容效率低
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';}}
}
?vector的擴容與string的擴容機制是一樣的,都是vs下是1.5倍擴容增長,Linux下是2倍增長。
vector中有一個函數接口我們可以有所了解,這個函數是用來縮容的。如果size的大小為8,而capacity的大小為80,我們可以使用shrink_to_fit函數進行縮容。但是我們不建議縮容,因為會進行空間的深拷貝以及析構。有所了解即可。
注意:reserve只負責開辟空間,如果確定知道需要用多少空間,reserve可以緩解vector增容的代價缺陷問題。resize在開空間的同時還會進行初始化,影響size。
vector 增刪查改
vector增刪查改 | 接口說明 |
push_back | 尾插 |
pop_back | 尾刪 |
find | 查找。(注意這個是算法模塊實現,不是vector的成員接口) |
insert | 在position之前插入val |
erase | 刪除position位置的數據 |
swap | 交換兩個vector的數據空間 |
operator[] | 像數組一樣訪問 |
?
?insert與erase中與string有區別,在string中支持使用下標進行訪問,而在vector中只支持迭代器進行訪問。
find查找函數在vector中是沒有的,而包含在algorithm頭文件中
這樣我們每次使用find都必須包含算法頭文件,但是find函數是一個模板函數,所以只要是迭代器無論是什么類型的都可以進行復用!!!
剩下的接口與string是一樣的,使用起來非常簡單,下面是演示代碼:
// 尾插和尾刪:push_back/pop_back
void TestVector4()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);auto it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;v.pop_back();v.pop_back();it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;
}// 任意位置插入:insert和erase,以及查找find
// 注意find不是vector自身提供的方法,是STL提供的算法
void TestVector5()
{// 使用列表方式初始化,C++11新語法vector<int> v{ 1, 2, 3, 4 };// 在指定位置前插入值為val的元素,比如:3之前插入30,如果沒有則不插入// 1. 先使用find查找3所在位置// 注意:vector沒有提供find方法,如果要查找只能使用STL提供的全局findauto pos = find(v.begin(), v.end(), 3);if (pos != v.end()){// 2. 在pos位置之前插入30v.insert(pos, 30);}vector<int>::iterator it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;pos = find(v.begin(), v.end(), 3);// 刪除pos位置的數據v.erase(pos);it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;
}// operator[]+index 和 C++11中vector的新式for+auto的遍歷
// vector使用這兩種遍歷方式是比較便捷的。
void TestVector6()
{vector<int> v{ 1, 2, 3, 4 };// 通過[]讀寫第0個位置。v[0] = 10;cout << v[0] << endl;// 1. 使用for+[]小標方式遍歷for (size_t i = 0; i < v.size(); ++i)cout << v[i] << " ";cout << endl;vector<int> swapv;swapv.swap(v);cout << "v data:";for (size_t i = 0; i < v.size(); ++i)cout << v[i] << " ";cout << endl;// 2. 使用迭代器遍歷cout << "swapv data:";auto it = swapv.begin();while (it != swapv.end()){cout << *it << " ";++it;}// 3. 使用范圍for遍歷for (auto x : v)cout << x << " ";cout << endl;
}
vector的深度剖析以及模擬實現
要實現vector我們先要從STL中了解vector的底層邏輯。
上圖就是vector在STL中的源代碼,其中就有許多不知名的參數在vector中的使用我們也能看到,為了更好的理解,這些都是被typedef的。接下來我們可以看到類中的參數并不是我們以前學習到的T* tmp、int size以及int capacity,而是用三個指針進行的,分別是start、finish以及end_of_storage所體現的。
這三個指針分別代表著首指針,內容尾部指針以及空間尾部指針,與size、capacity有著密切的關聯,這樣說還不夠明顯,我們接著往下看。
vector中的size與capacity函數的源代碼,就是將提供私有成員進行相減得到的大小。我們就可以理解其中的start、finish、end_of_storage的指向了。?
?其實大體的結構沒有改變,只是使用指針去定義vector中的各種數據。
現在我們就可以進行vector的模擬實現了。
vector類的創建以及構造函數與析構函數
#pragma once#include <iostream>
using namespace std;
#include <assert.h>namespace why
{template<class T>class vector{public:// Vector的迭代器是一個原生指針typedef T* iterator;typedef const T* const_iterator;///// 構造和銷毀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())就不需要提供了,但是對于:* vector<int> v(10, 5);* 編譯器在編譯時,認為T已經被實例化為int,而10和5編譯器會默認其為int類型* 就不會走vector(size_t n, const T& value = T())這個構造方法,* 最終選擇的是:vector(InputIterator first, InputIterator last)* 因為編譯器覺得區間構造兩個參數類型一致,因此編譯器就會將InputIterator實例化為int* 但是10和5根本不是一個區間,編譯時就報錯了* 故需要增加該構造方法*/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做迭代器,會導致初始化的迭代器區間[first,last)只能是vector的迭代器// 重新聲明迭代器,迭代器區間[first,last)可以是任意容器的迭代器template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}~vector(){if (_start){delete[] _start;_start = _finish = _endOfStorage = nullptr;}}//拷貝構造函數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;}private:iterator _start; // 指向數據塊的開始iterator _finish; // 指向有效數據的尾iterator _endOfStorage; // 指向存儲容量的尾};
}
這是vector常見的構造函數與析構函數。
無參默認函數非常簡單,而第二種構造函數是將一種類型的內容進行n個初始化,那為什么在模擬構造時要寫兩個此類函數構成重載嗎?不是多此一舉?
因為假如不寫重載就會與第三個迭代器類模板沖突,因為我們傳入的參數很可能是兩個int類型的值,我們用戶本意是將n個int類型的值進行初始化,但是兩個int值會與更匹配的模板進行結合,導致非法間接尋址,所以我們必須要重載一個int型。
?迭代器相關模擬實現
iterator begin(){return _start;}iterator end(){return _finish;}const_iterator cbegin() const{return _start;}const_iterator cend() 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()){size_t oldSize = size();// 1. 開辟新空間T* tmp = new T[n];// 2. 拷貝元素// 這里直接使用memcpy會有問題嗎?同學們思考下//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小于當前的size,則數據個數縮小到nif (n <= size()){_finish = _start + n;return;}// 2.空間不夠則增容if (n > capacity())reserve(n);// 3.將size擴大到niterator it = _finish;_finish = _start + n;while (it != _finish){*it = value;++it;}}
?reserve函數是擴容函數,在復用的時候肯定會遇到異地擴容的情況,所以我們必須進行深拷貝處理,使用memcpy可以解決一些普通變量的拷貝比如:int、double等等。但是面對復雜的內容就無法解決,所以我們必須使用賦值進行拷貝。
假設模擬實現的vector中的reserve接口中,使用memcpy進行的拷貝,以下代碼會發生什么問題?
int main()
{bite::vector<bite::string> v;v.push_back("1111");v.push_back("2222");v.push_back("3333");return 0;
}
問題分析:
1. memcpy是內存的二進制格式拷貝,將一段內存空間中內容原封不動的拷貝到另外一段內存空間中
2. 如果拷貝的是自定義類型的元素,memcpy既高效又不會出錯,但如果拷貝的是自定義類型元素,并且自定義類型元素中涉及到資源管理時,就會出錯,因為memcpy的拷貝實際是淺拷貝。?
結論:如果對象中涉及到資源管理時,千萬不能使用memcpy進行對象之間的拷貝,因為memcpy是淺拷貝,否則可能會引起內存泄漏甚至程序崩潰。?
我們必須打好reserve的基礎,這個擴容在后面的許多函數都必須要用,我們必須創建好。
resize的函數算法與string中的算法原理相同。
元素訪問相關模擬實現
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);}
在不改變內容的情況下,我們必須考慮有const的,所以必須進行函數重載。
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);// 空間不夠先進行增容if (_finish == _endOfStorage){//size_t size = size();size_t newCapacity = (0 == capacity()) ? 1 : capacity() * 2;reserve(newCapacity);// 如果發生了增容,需要重置pospos = _start + size();}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}// 返回刪除數據的下一個數據// 方便解決:一邊遍歷一邊刪除的迭代器失效問題iterator erase(iterator pos){// 挪動數據進行刪除iterator begin = pos + 1;while (begin != _finish) {*(begin - 1) = *begin;++begin;}--_finish;return pos;}
在創建insert與erase函數時,我們都會遇到一種問題,迭代器失效。
?vector 迭代器失效問題
迭代器的主要作用就是讓算法能夠不用關心底層數據結構,其底層實際就是一個指針,或者是對指針進行了封裝,比如:vector的迭代器就是原生態指針T* 。因此迭代器失效,實際就是迭代器底層對應指針所指向的空間被銷毀了,而使用一塊已經被釋放的空間,造成的后果是程序崩潰(即如果繼續使用已經失效的迭代器,程序可能會崩潰)。
對于vector可能會導致其迭代器失效的操作有:
1. 會引起其底層空間改變的操作,都有可能是迭代器失效,比如: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();
// 將有效元素個數增加到100個,多出的位置使用8填充,操作期間底層會擴容
// v.resize(100, 8);
// reserve的作用就是改變擴容大小但不改變有效元素個數,操作期間可能會引起底層容量改變
// v.reserve(100);
// 插入元素期間,可能會引起擴容,而導致原空間被釋放
// v.insert(v.begin(), 0);
// v.push_back(8);
// 給vector重新賦值,可能會引起底層容量改變
v.assign(100, 8);
/*
出錯原因:以上操作,都有可能會導致vector擴容,也就是說vector底層原理舊空間被釋放掉,
而在打印時,it還使用的是釋放之間的舊空間,在對it迭代器操作時,實際操作的是一塊已經被釋放的
空間,而引起代碼運行時崩潰。
解決方式:在以上操作完成之后,如果想要繼續通過迭代器操作vector中的元素,只需給it重新
賦值即可。
*/
while(it != v.end())
{
cout<< *it << " " ;
++it;
}
cout<<endl;
return 0;
}
指定位置元素的刪除操作--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所在位置的iterator
vector<int>::iterator pos = find(v.begin(), v.end(), 3);
// 刪除pos位置的數據,導致pos迭代器失效。
v.erase(pos);
cout << *pos << endl; // 此處會導致非法訪問
return 0;
}
?erase刪除pos位置元素后,pos位置之后的元素會往前搬移,沒有導致底層空間的改變,理論上講迭代器不應該會失效,但是:如果pos剛好是最后一個元素,刪完之后pos剛好是end的位置,而end位置是沒有元素的,那么pos就失效了。因此刪除vector中任意位置上元素時,vs就認為該位置迭代器失效了。
Linux下,g++編譯器對迭代器失效的檢測并不是非常嚴格,處理也沒有vs下極端。
迭代器失效解決辦法:在使用前,對迭代器重新賦值即可。
賦值重載函數的模擬
void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}
vector<T>& operator=(vector<T> v){swap(v);return *this;}
我們可以偷個懶,將拷貝好的內容直接進行交換即可實現賦值的作用。
以上我們將vector與vector的模擬實現全部完成。相信大家看完這篇博客可以對vector有更深的理解。
創作不易,希望大家多多支持!!!