鐵汁們，今天給大家分享一篇vector模擬實(shí)現(xiàn) + 迭代器失效，來吧，開造??
成員變量定義
- 指向最后一個(gè)空間的下一個(gè)位置
?? iterator _endofstorage
- 指向存儲(chǔ)第一個(gè)有效數(shù)據(jù)空間的位置
?? iterator _start
- 指向存儲(chǔ)最后一個(gè)有效數(shù)據(jù)空間的下一個(gè)位置
?? iterator _finish
- 在成員變量聲明處給缺省值，實(shí)質(zhì)上是將缺省值給了初始化列表。
- 在創(chuàng)建一個(gè)新的對(duì)象時(shí)，都需要先走初始化列表完成初始化，在走構(gòu)造函數(shù)。
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<assert.h>
using namespace std;
template<class T>
class vector {
private:
iterator _start = nullptr; //起始位置
iterator _finish = nullptr; //有效數(shù)據(jù)的結(jié)束位置
iterator _endofstorage = nullptr; //容量的結(jié)束位置
};
默認(rèn)成員函數(shù)
構(gòu)造函數(shù)
??vector( ) { } ;
- 功能：構(gòu)造無參的對(duì)象
vector() {}; //無參構(gòu)造
??vector(size_t n, const T& val = T( ) ) ;
- 功能：構(gòu)造含n個(gè)val值的對(duì)象
vector(size_t n, const T& val = T()) //用n個(gè)val值構(gòu)造
{
resize(n, val);
}
??vector( InputIterator first, InputIterator last ) ;
- 功能：構(gòu)造與[first, last)范圍一樣多元素的對(duì)象
template<class InputIterator> // 注意： 模板內(nèi)可以在嵌套模板
vector(InputIterator first, InputIterator last) //用迭代區(qū)間進(jìn)行構(gòu)造
{ //泛型編程，函數(shù)模板，不是只適用于某個(gè)容器的的迭代器，適用于所有容器的的迭代器
while (first != last)
{
push_back(*first);
first++;
}
}
??Tips：模板內(nèi)可以嵌套其他模板。
迭代器
template<class T>
class vector {
public:
typedef T* iterator;
typedef const T* const_iterator;
}
?? Tips：指向連續(xù)物理空間的指針是天然的迭代器。
??iterator begin( ) ;
- 功能：返回指向第一個(gè)元素的位置。
iterator begin() //迭代器所指向的空間內(nèi)的值 “既可讀又可寫”
{ //只適用于const對(duì)象（權(quán)限可以平移）、不適用于非const對(duì)象（權(quán)限不可以放大）
return _start; //vector第一個(gè)元素所在的位置（指針）
}
??Tips : const_iterator 修飾的是迭代器所指向的元素不能被修改，而迭代器本身可以被修改。const修飾this指針，表示在該成員函數(shù)中成員變量不允許被修改，此處const的用法只能用于類中的成員函數(shù)。
??iterator end( ) ;
- 功能：返回指向最后一個(gè)元素的下一個(gè)位置。
iterator end()
{
return _finish; //vector最后一個(gè)元素后面所在的位置（指針）
}
??const_iterator begin( )const ;
const_iterator begin()const //迭代器所指向的空間內(nèi)的值 “只可不可寫”
{
return _start; //既適用于const對(duì)象（權(quán)限可以平移）、又適用于非const對(duì)象（權(quán)限可以縮?。?/span>
}
??const_iterator end( )const ;
const_iterator end()const
{
return _finish;
}
范圍for、對(duì)象類型匹配原則
const vector<int> v(5, 2);
for (auto& e : v)
{
cout << e << ' ';
}
cout << endl;
-
只要容器支持迭代器，就支持用范圍for來訪問, 原因：范圍for的底層實(shí)現(xiàn)為迭代器。
-
用范圍for訪問對(duì)象中的元素，對(duì)象類型不同，范圍for底層調(diào)用的迭代器接口不同。
容量操作
size
??size_t size( )const ;
- 功能：計(jì)算元素的總個(gè)數(shù)
size_t size()const //有效元素總個(gè)數(shù)
{
return _finish - _start;
}
empty
??bool empty( )const ;
- 功能：判斷vector是否為空，為空，則返回true,不為空，則返回false。
bool empty()const //判斷是否為空， 為空，則返回true,不為空，則返回false
{
return size() == 0;
}
vector<string> v1;
v1.push_back("zhangsan");
cout << v1.empty() << endl;
vector<int> v2;
cout << v2.empty() << endl;
capacity
??size_t capacity( )const ;
- 功能：獲得當(dāng)前分配給vector存儲(chǔ)空間的大小。
size_t capacity()const //容量的大小
{
return _endofstorage - _start;
}
reserve
??void reserve(size_t n) ;
- 功能：使得vector容器存儲(chǔ)空間的大小為n。
void reserve(size_t n) //開空間（擴(kuò)容）
{
if (n > capacity()) //此處在判斷:1.自己直接調(diào)用reserve,2.其他接口間接調(diào)用reserve
{
T* tmp = new T[n]; //擴(kuò)容 new:開空間+構(gòu)造函數(shù)，完成初始化
size_t old = size(); // 注意 ：因?yàn)閚ew[]會(huì)開辟新的空間
if (_start) //拷貝舊空間中的值
{
for (int i = 0; i < old; i++) //vector底層物理空間連續(xù)
tmp[i] = _start[i] ; // 若為string,則調(diào)用string的賦值重載函數(shù)(深拷貝）
delete[] _start; //delete:析構(gòu)函數(shù)+釋放空間
}
//更新成員變量
_start = tmp;
_finish = _start + old; //
_endofstorage = _start + n; //
}
}
成員變量未更新
void reserve(size_t n) //開空間（擴(kuò)容）
{
if (n > capacity()) //此處在判斷:1.自己直接調(diào)用reserve,2.其他接口間接調(diào)用reserve
{
T* tmp = new T[n]; //擴(kuò)容 new:開空間+構(gòu)造函數(shù)，完成初始化
if (_start) //拷貝舊空間中的值
{
memcpy(tmp, _start, sizeof(T) * size());
delete[] _start; //delete:析構(gòu)函數(shù)+釋放空間
}
//更新成員變量
_start = tmp;
_finish = _start + size();
_endofstorage = _start + capacity();
}
}
memcpy值拷貝
void reserve(size_t n) //開空間（擴(kuò)容）
{
if (n > capacity()) //此處在判斷:1.自己直接調(diào)用reserve,2.其他接口間接調(diào)用reserve
{
T* tmp = new T[n]; //擴(kuò)容 new:開空間+構(gòu)造函數(shù)，完成初始化
size_t old = size(); // 注意 ：因?yàn)閚ew[]會(huì)開辟新的空間
if (_start) //拷貝舊空間中的值
{
memcpy(tmp, _start, sizeof(T) * old);
delete[] _start; //delete:析構(gòu)函數(shù)+釋放空間
}
//更新成員變量
_start = tmp;
_finish = _start + old; //
_endofstorage = _start + n; //
}
}
resize
??void resize(size_t n, const typename& val = typename( ) ) ;
- 功能：調(diào)整vector容器的大小，使其內(nèi)元素個(gè)數(shù)變?yōu)閚。
void resize(size_t n, const T& val = T()) //開空間+初始化
{
if (n > size()) //插入數(shù)據(jù) -》 n > capacity:擴(kuò)容+插入 size < n <capacity:插入
{
reserve(n); // n > capacity
for(int i = size(); i < n; i++) //從size位置處向后插入
push_back(val);
}
else //n < size:尾刪
{
_finish = _start + n;
}
}
vector<int> v2;
v2.push_back(2);
v2.push_back(2);
v2.push_back(2);
v2.push_back(2);
v2.push_back(2);
for (auto& e : v2)
{
cout << e << ' ';
}
cout << endl;
v2.resize(7, 1);
for (auto& e : v2)
{
cout << e << ' ';
}
cout << endl;
v2.resize(12);
for (auto& e : v2)
{
cout << e << ' ';
}
cout << endl;
v2.resize(3);
for (auto& e : v2)
{
cout << e << ' ';
}
cout << endl;
內(nèi)置類型的構(gòu)造函數(shù)
int a = int();
cout << a << endl;
int b = int(5);
cout << b << endl;
??Tips ：初始化處默認(rèn)給缺省值，缺省值為無參構(gòu)造函數(shù)，自定義類型會(huì)去調(diào)它自己的默認(rèn)構(gòu)造函數(shù)，c++11為了兼容模板，使得內(nèi)置類型也有構(gòu)造函數(shù)，內(nèi)置類型得無參構(gòu)造函數(shù)初始化為0,eg:int val = int(), val = 0、double val = double(),val = 0.0,int* val = int*() , val = nullptr、char val = char(), val = ‘\0’。
數(shù)據(jù)訪問
front
??T& front( ) ;
- 功能：獲取第一個(gè)有效元素
T& front() //獲取第一個(gè)有效元素
{
assert(size() > 0); //斷言，確保是否有數(shù)據(jù)
return *_start;
}
back
??T& back( ) ;
- 功能：獲取最后一個(gè)有效元素
T& back() //獲取最后一個(gè)有效元素
{
assert(size() > 0); //斷言，確保是否有數(shù)據(jù)
return *(_finish - 1);
}
vector<int> v4;
v4.push_back(1);
v4.push_back(2);
v4.push_back(3);
cout << v4.front() << endl;
cout << v4.back() << endl;
operator[ ]
??T& operator[](size_t n) ;
- 功能：訪問下標(biāo)為n處的值，返回值既可讀又可寫(非const對(duì)象)。
T& operator[](size_t n) //既可讀又可寫
{
return _start[n];
}
??const T& operator[](size_t n)const ;
- 功能：訪問下標(biāo)為n處的值，返回值只可讀不可寫(const對(duì)象)。
const T& operator[](size_t n)const //只可讀不可寫
{
return _start[n];
}
vector<int> v2(5, 2);
v2[2] = 3;
cout << v2[2] << endl;
const vector<int> v3(5, 4);
cout << v3[3] << endl;
數(shù)據(jù)修改操作
push_back
??void push_back(const T& val) ;
- 功能：在末尾插入一個(gè)元素。
void push_back(const T& val) //在末尾插入一個(gè)數(shù)據(jù)
{
if (_finish == _endofstorage) //空間滿了，擴(kuò)容
{
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
}
*_finish = val; //插入數(shù)據(jù)
_finish++;
}
pop_back
??void pop_back( ) ；
- 功能：刪除最后一個(gè)元素。
void pop_back() //刪除最后一個(gè)元素
{
assert(size() > 0); //斷言，無任何數(shù)據(jù)，不能在進(jìn)行刪除操作
_finish--;
}
vector<int> v4;
v4.push_back(1);
v4.push_back(2);
v4.push_back(3);
for (auto& e : v4)
{
cout << e << ' ';
}
cout << endl;
v4.pop_back();
for (auto& e : v4)
{
cout << e << ' ';
}
cout << endl;
swap
??void swap(vector& v) ;
- 功能：交換。
void swap(vector<T>& v) //交換
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
vector<int> v2(5, 2);
vector<int> v4;
v4.push_back(1);
v4.push_back(2);
v4.push_back(3);
v4.pop_back();
for (auto& e : v2)
{
cout << e << ' ';
}
cout << endl;
for (auto& e : v4)
{
cout << e << ' ';
}
cout << endl;
v2.swap(v4);
for (auto& e : v2)
{
cout << e << ' ';
}
cout << endl;
for (auto& e : v4)
{
cout << e << ' ';
}
cout << endl;
clear
??void clear( ) ;
- 功能：使vector中元素的總個(gè)數(shù)size變?yōu)?，但容量capacity不變。
void clear() //清空 size改變，capacity不變
{
_finish = _start;
}
insert
??void insert ( iterator position , const typename& x) ；
- 功能：在指定的位置(迭代器）前插入元素x。
iterator insert(iterator pos, const T& val) //在pos位置前插入元素
{
assert(pos >= _start && pos <= _finish); //斷言，確保在[_start,_finish]范圍內(nèi)插入數(shù)據(jù)
if (_finish == _endofstorage) //空間滿了，擴(kuò)容
{
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
pos = _start + len; //擴(kuò)容會(huì)導(dǎo)致pos位置失效，更新pos位置
}
//此處數(shù)據(jù)往后挪動(dòng)，既可以用memmove，又可以用迭代器
//memmove(pos + 1, pos, sizeof(T) *( _finish - pos)); //memmove為值拷貝
iterator tmp = _finish - 1;
while (tmp >= pos)
{
*(tmp + 1) = *tmp;
tmp--;
}
*pos = val; //插入數(shù)據(jù)
_finish++;
return pos; //返回值為了，發(fā)生擴(kuò)容,pos位置更新后的值仍能被繼續(xù)使用
}
pos位置未更新
void insert(iterator pos, const T& val) //在pos位置前插入元素
{
assert(pos >= _start && pos <= _finish); //斷言，確保在[_start,_finish]范圍內(nèi)插入數(shù)據(jù)
if (_finish == _endofstorage) //空間滿了，擴(kuò)容
{
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
}
//此處數(shù)據(jù)往后挪動(dòng)，既可以用memmove，又可以用迭代器
//memmove(pos + 1, pos, sizeof(T) *( _finish - pos)); //memmove為值拷貝
iterator tmp = _finish - 1;
while (tmp >= pos)
{
*(tmp + 1) = *tmp;
tmp--;
}
*pos = val; //插入數(shù)據(jù)
_finish++;
}
vector<string> v1;
v1.push_back("zhangsan");
v1.push_back("lisi");
v1.push_back("wangwu");
v1.push_back("zhaoqan");
v1.insert(v1.begin(), "lala");
for (auto& e : v1)
{
cout << e << ' ';
}
- 因擴(kuò)容使原空間被釋放，導(dǎo)致pos指向已經(jīng)被釋放的空間（pos為野指針）。若想繼續(xù)插入新的數(shù)據(jù)，需要更新pos，使pos指向新空間。
無返回值
void insert(iterator pos, const T& val) //在pos位置前插入元素
{
assert(pos >= _start && pos <= _finish); //斷言，確保在[_start,_finish]范圍內(nèi)插入數(shù)據(jù)
if (_finish == _endofstorage) //空間滿了，擴(kuò)容
{
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
pos = _start + len; //擴(kuò)容會(huì)導(dǎo)致pos位置失效，更新pos位置
}
//此處數(shù)據(jù)往后挪動(dòng)，既可以用memmove，又可以用迭代器
//memmove(pos + 1, pos, sizeof(T) *( _finish - pos)); //memmove為值拷貝
iterator tmp = _finish - 1;
while (tmp >= pos)
{
*(tmp + 1) = *tmp;
tmp--;
}
*pos = val; //插入數(shù)據(jù)
_finish++;
}
vector<string> v1;
v1.push_back("zhangsan");
v1.push_back("lisi");
v1.push_back("wangwu");
v1.push_back("zhaoqan");
vector<string>::iterator pos = std::find(v1.begin(), v1.end(), "zhangsan");
v1.insert(pos, "zzx");
v1.insert(pos, "lala"); //出錯(cuò)處
for (auto& e : v1)
{
cout << e << ' ';
}
- 因函數(shù)為傳值調(diào)用，形參只是實(shí)參的一份臨時(shí)拷貝，形參的改變不會(huì)影響實(shí)參。
- 在容量滿了情況下，若兩次insert(pos,數(shù)據(jù))，第一次insert會(huì)進(jìn)行擴(kuò)容，擴(kuò)容導(dǎo)致原空間被釋放 。第二次insert，盡管在函數(shù)體內(nèi)更新了pos,傳值調(diào)用，pos仍指向已經(jīng)被釋放的空間，引起運(yùn)行時(shí)代碼崩潰。若仍想使用pos迭代器，只需給pos重新賦值，即：使用返回值。
erase
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish); //斷言，確保在[_start,_finish)范圍內(nèi)刪除數(shù)據(jù)
assert(size() > 0); //斷言，無任何數(shù)據(jù)，不能在進(jìn)行刪除操作
//此處數(shù)據(jù)往前覆蓋pos位置，既可以用memmove，又可以用迭代器
//memmove(pos, pos + 1, sizeof(T) * (_finish - pos - 1)); memmove為值拷貝
iterator tmp = pos;
while (tmp < _finish - 1)
{
*tmp = *(tmp + 1);
tmp++;
}
_finish--;
return pos;
}
無返回值
void erase(iterator pos)
{
assert(pos >= _start && pos < _finish); //斷言，確保在[_start,_finish)范圍內(nèi)刪除數(shù)據(jù)
assert(size() > 0); //斷言，無任何數(shù)據(jù)，不能在進(jìn)行刪除操作
memmove(pos, pos + 1, sizeof(T) * (_finish - pos - 1));
_finish--;
}
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
//刪除v中的奇數(shù)
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 != 0)
v.erase(it);
it++;
}
for (auto& e : v)
{
cout << e << ' ';
}
cout << endl;
- 因?yàn)閑rase功能為刪除pos位置處的數(shù)據(jù)，用pos+1位置向前覆蓋pos位置的數(shù)據(jù),
vectorv{1,2,3},it=v.begin(),erase(it)后,it中數(shù)據(jù)為2,在直接it++,此時(shí)it中數(shù)據(jù)為3，erase(it)后，it=v.end(),而end位置是沒有元素的，那么pos就失效了。在it++, 就越界了assert條件為假，導(dǎo)致程序崩潰。此時(shí)只需要給it重新賦值，即：添加返回值。
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
//刪除v中的奇數(shù)
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 != 0)
it = v.erase(it);
else
it++;
}
for (auto& e : v)
{
cout << e << ' ';
}
cout << endl;
迭代器失效
定義
- 在c++中，容器的insert、erase等操作可能會(huì)引起迭代器失效，如果在迭代器已經(jīng)失效的情況下，繼續(xù)使用失效的迭代器來訪問容器內(nèi)的數(shù)據(jù)，會(huì)引起運(yùn)行時(shí)程序崩潰或者產(chǎn)生不可預(yù)期的結(jié)果，這種情況就稱為迭代器失效。
insert導(dǎo)致的迭代器失效
vector<string> v1;
v1.push_back("zhangsan");
v1.push_back("lisi");
v1.push_back("wangwu");
v1.push_back("zhaoqan");
v1.insert(v1.begin(), "lala");
for (auto& e : v1)
{
cout << e << ' ';
}
- 空間滿了，在插入數(shù)據(jù)，會(huì)進(jìn)行擴(kuò)容，擴(kuò)容reserve會(huì)引起底層空間的改變，開辟新空間，原空間被釋放，導(dǎo)致pos指向已經(jīng)被釋放的空間（pos為野指針），此時(shí)只需要更新pos，使pos指向新空間。
- ??Tips: 迭代器失效——》擴(kuò)容會(huì)引起底層空間的改變，導(dǎo)致原來空間被釋放，迭代器指向已經(jīng)被釋放的空間，迭代器也野指針。
erase導(dǎo)致的迭代器失效
刪除vector中的奇數(shù)
void erase(iterator pos)
{
assert(pos >= _start && pos < _finish); //斷言，確保在[_start,_finish)范圍內(nèi)刪除數(shù)據(jù)
assert(size() > 0); //斷言，無任何數(shù)據(jù)，不能在進(jìn)行刪除操作
memmove(pos, pos + 1, sizeof(T) * (_finish - pos - 1));
_finish--;
}
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
//刪除v中的奇數(shù)
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 != 0)
v.erase(it);
it++;
}
for (auto& e : v)
{
cout << e << ' ';
}
cout << endl;
-
erase刪除pos位置元素后，pos位置之后的元素會(huì)往前挪動(dòng)，無底層空間的變化，但是如果pos剛好為最后一個(gè)元素，刪完之后pos剛好為end位置，而end位置上無元素，那么pos也就失效了，此時(shí)只需要給it重新賦值，即：添加返回值。
-
刪除vector中任意位置上元素時(shí)，vs就認(rèn)為該位置迭代器失效了。
-
??Tips: 迭代器失效——》不會(huì)引起底層空間發(fā)生變化，迭代器指向了錯(cuò)誤的位置。
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
//刪除v中的奇數(shù)
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 != 0)
it = v.erase(it);
else
it++;
}
for (auto& e : v)
{
cout << e << ' ';
}
cout << endl;
?? Tips：在erase的實(shí)現(xiàn)中，不能保證編譯器是否會(huì)進(jìn)行縮容，但是縮容會(huì)導(dǎo)致迭代器失效。insert和erase的pos可能都會(huì)失效，所以對(duì)于insert和erase使用過的迭代器不要去使用。文章來源：http://www.zghlxwxcb.cn/news/detail-833103.html
非法的間接尋址
vector<string> v1(5, "zzx");
for (auto& e : v1)
{
cout << e << ' ';
}
cout << endl;
vector<int> v2(5, 2);
for (auto& e : v2)
{
cout << e << ' ';
}
cout << endl;
鐵鐵們，vector模擬實(shí)現(xiàn)+迭代器失效就到此結(jié)束啦，若博主有不好的地方，請(qǐng)指正，歡迎鐵鐵們留言，請(qǐng)動(dòng)動(dòng)你們的手給作者點(diǎn)個(gè)??鼓勵(lì)吧，你們的鼓勵(lì)就是我的動(dòng)力?文章來源地址http://www.zghlxwxcb.cn/news/detail-833103.html
到了這里，關(guān)于【C++】vector模擬實(shí)現(xiàn)+迭代器失效的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[STL-list]介紹、與vector的對(duì)比、模擬實(shí)現(xiàn)的迭代器問題](https://imgs.yssmx.com/Uploads/2024/04/852450-1.png)
![[C++]:11.模擬實(shí)現(xiàn)vector](https://imgs.yssmx.com/Uploads/2024/02/794333-1.png)
