C++中vector迭代器失效問題詳解
更新時間：2021年11月17日 10:01:24 作者：~怎么回事啊~
vector是向量類型,它可以容納許多類型的數(shù)據(jù),如若干個整數(shù),所以稱其為容器,這篇文章主要給大家介紹了關(guān)于C++中vector迭代器失效問題的相關(guān)資料,需要的朋友可以參考下
問題：
（1）刪除vector中所有的偶數(shù)
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> vec;
for (int i = 0; i < 10; ++i) {
vec.push_back(i);
}
//把vec容器中的所有偶數(shù)刪除
auto it = vec.begin();
for (; it != vec.end(); ++it) {
if ((*it) % 2 == 0) {
vec.erase(it);
}
}
return 0;
}
運行導致程序崩潰！
（2）vector容器插入元素問題
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> vec;
for (int i = 0; i < 10; ++i) {
vec.push_back(i);
}
//把vec容器中的所有偶數(shù)前面添加一個小于偶數(shù)值1的數(shù)字
auto it = vec.begin();
for (; it != vec.end(); ++it) {
if ((*it) % 2 == 0) {
vec.insert(it,*it-1);
}
}
return 0;
}
運行導致程序崩潰！
原因：iterator失效
當刪除（獲取增加）it位置的元素時，導致it后面的迭代器全部失效。因此多次調(diào)用erase insert導致崩潰
迭代器失效原因
1 當容器調(diào)用erase時，當前位置到容器末尾元素的所有的迭代器全部失效
2 當容器調(diào)用insert時，當前位置到容器末尾元素的所有的迭代器全部失效；
3 當容器調(diào)用insert時，如果引起容器內(nèi)存擴容，原來容器的所有的迭代器就全部失效
解決：
進行更新操作：erase（insert）后會返回指向下一個元素的迭代器
解釋：vector::erase - C++ Reference
從向量中刪除單個元素（位置）或一系列元素（[第一、最后一個]）。
這有效地減少了容器的大小，減少了被刪除的元素的數(shù)量，這些元素會被銷毀。
由于向量使用數(shù)組作為其底層存儲，擦除向量端以外位置的元素會導致容器在段擦除后將所有元素重新定位到其新位置。與其他類型的序列容器對相同操作執(zhí)行的操作相比，這通常是一種低效的操作（如列表或轉(zhuǎn)發(fā)列表）。
同理有：vector::insert - C++ Reference
通過在指定位置的元素之前插入新元素來擴展向量，從而通過插入的元素數(shù)量有效地增加容器大小。
當且僅當新向量大小超過當前向量容量時，這會導致自動重新分配分配分配的存儲空間。
因為向量使用數(shù)組作為其底層存儲，所以在向量末端以外的位置插入元素會導致容器將位置之后的所有元素重新定位到它們的新位置。與其他類型的序列容器（如list或forward_list）對相同操作執(zhí)行的操作相比，這通常是一種低效的操作。
這些參數(shù)確定插入的元素數(shù)量及其初始化值：
也說明了進行插入操作會導致之后的迭代器失效
修改代碼：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> vec;
for (int i = 0; i < 10; ++i) {
vec.push_back(i);
}
//把vec容器中的所有偶數(shù)刪除
auto it = vec.begin();
while (it!=vec.end())
{
if ((*it) % 2 == 0) {
it = vec.erase(it);
}
else {
it++;
}
}
for(auto it:vec) {
cout << it << " ";
}
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> vec;
for (int i = 0; i < 10; ++i) {
vec.push_back(i);
}
//把vec容器中的所有偶數(shù)前面添加一個小于偶數(shù)值1的數(shù)字
auto it = vec.begin();
for (; it != vec.end(); ++it) {
if ((*it) % 2 == 0) {
it = vec.insert(it, *it - 1);
//it原來的位置插入了新的，需要++it兩次，才能到該偶數(shù)的后一個元素
++it;
}
}
for (auto val : vec) {
cout << val << " ";
}
return 0;
}
這樣就沒有問題。
vector中實現(xiàn)
http://m.fzitv.net/article/229393.htm 接該文最終實現(xiàn)的vector上繼續(xù)：
頭插法：
檢查迭代器失效：
在進行刪除或增加的時候，要檢測該位置到last位置，使其迭代器失效
void pop_back() // 從容器末尾刪除元素
{
if (empty())
return;
//檢查迭代器 從該位置到最后
verify(_last-1,_last);
// 不僅要把_last指針--，還需要析構(gòu)刪除的元素
--_last;
_allocator.destroy(_last);
}
//檢查迭代器失效
void verify(T* first, T* last) {
Iterator_Base * pre = &this->_head;
Iterator_Base * it = this->_head._next;
while (it != nullptr) {
if (it->_cur->_ptr > first && it->_cur->_ptr <= last) {
it->_cur->_pVec = nullptr;//迭代器失效，把iterator持有的容器指針置空
pre->_next = it->_next;//刪除當前迭代器節(jié)點，繼續(xù)判斷后面的迭代器是否失效
delete it;
it = pre->_next;
}
else {
pre = it;
it = it->_next;
}
}
}
insert
//insert
iterator insert(iterator it, const T&val) {
//未考慮擴容和it._ptr的合法性 todo
verify(it._ptr - 1, _last);
//依次向后移動一個位置
T*p = _last;
while (p > it->_ptr) {
_allocator.construct(p,*(p-1));
_allocator.destroy(p-1);
p--;
}
//在該位置插入
_allocator.construct(p, val);
_last++;
return iterator(this, p);//生成新的迭代器
}
erase
#include <iostream>
//容器的空間配置器
template <typename T>
struct Allocator
{
T* allocate(size_t size)//只負責內(nèi)存開辟
{
return (T*)malloc(sizeof(T) * size);
}
void deallocate(void *p)//只負責內(nèi)存釋放
{
free(p);
}
void construct(T *p, const T &val)//已經(jīng)開辟好的內(nèi)存上，負責對象構(gòu)造
{
new (p) T(val);//定位new，指定內(nèi)存上構(gòu)造val，T(val)拷貝構(gòu)造
}
void destroy(T *p)//只負責對象析構(gòu)
{
p->~T();//~T()代表了T類型的析構(gòu)函數(shù)
}
};
template <typename T, typename Alloc = Allocator<T>>
class vector//向量容器
{
public:
vector(int size = 10)//構(gòu)造
{
//_first = new T[size];
_first = _allocator.allocate(size);
_last = _first;
_end = _first + size;
}
~vector()//析構(gòu)
{
//delete[]_first;
for (T *p = _first; p != _last; ++p)
{
_allocator.destroy(p);//把_first指針指向的數(shù)組的有效元素析構(gòu)
}
_allocator.deallocate(_first);//釋放堆上的數(shù)組內(nèi)存
_first = _last = _end = nullptr;
}
vector(const vector<T> &rhs)//拷貝構(gòu)造
{
int size = rhs._end - rhs._first;//空間大小
//_first = new T[size];
_first = _allocator.allocate(size);
int len = rhs._last - rhs._first;//有效元素
for (int i = 0; i < len; ++i)
{
//_first[i] = rhs._first[i];
_allocator.construct(_first + i, rhs._first[i]);
}
_last = _first + len;
_end = _first + size;
}
vector<T>& operator=(const vector<T> &rhs)//賦值運算符重載
{
if (this == &rhs)
{
return *this;
}
//delete[]_first;
for (T *p = _first; p != _last; ++p)
{
_allocator.destory(p);//把_first指針指向的數(shù)組的有效元素析構(gòu)
}
_allocator.deallocate(_first);//釋放堆上的數(shù)組內(nèi)存
int size = rhs._end - rhs._first;//空間大小
_first = _allocator.allocate(size);
int len = rhs._last - rhs._first;//有效元素
for (int i = 0; i < len; ++i)
{
_allocator.construct(_first + i, rhs._first[i]);
}
_last = _first + len;
_end = _first + size;
return *this;
}
void push_back(const T &val)//尾插
{
if (full())
{
expand();
}
//*_last++ = val;
_allocator.construct(_last, val);//_last指針指向的內(nèi)存構(gòu)造一個值為val的對象
_last++;
}
void pop_back()//尾刪
{
if (empty()) return;
verify(_last - 1, _last);
//erase(it); verift(it._ptr, _last);
//insert(it,val); verift(it._ptr, _last);
//--_last;
//不僅要把_last指針--，還需要析構(gòu)刪除的元素
--_last;
_allocator.destroy(_last);
}
T back()const//返回容器末尾元素值
{
return *(_last - 1);
}
bool full()const
{
return _last == _end;
}
bool empty()const
{
return _first == _last;
}
int size()const//返回容器中元素個數(shù)
{
return _last - _first;
}
T& operator[](int index)
{
if (index < 0 || index >= size())
{
throw "OutOfRangeException";
}
return _first[index];
}
//迭代器一般實現(xiàn)成容器的嵌套類型
class iterator
{
public:
friend class vector <T, Alloc>;
//新生成當前容器某一個位置元素的迭代器
iterator(vector<T, Alloc> *pvec = nullptr
, T *ptr = nullptr)
:_ptr(ptr), _pVec(pvec)
{
Iterator_Base *itb = new Iterator_Base(this, _pVec->_head._next);
_pVec->_head._next = itb;
}
bool operator!=(const iterator &it)const
{
//檢查迭代器的有效性
if (_pVec == nullptr || _pVec != it._pVec)//迭代器為空或迭代兩個不同容器
{
throw "iterator incompatable!";
}
return _ptr != it._ptr;
}
void operator++()
{
//檢查迭代器有效性
if (_pVec == nullptr)
{
throw "iterator incalid!";
}
_ptr++;
}
T& operator*()
{
//檢查迭代器有效性
if (_pVec == nullptr)
{
throw "iterator invalid!";
}
return *_ptr;
}
const T& operator*()const
{
if (_pVec == nullptr)
{
throw "iterator invalid!";
}
return *_ptr;
}
private:
T *_ptr;
//當前迭代器是哪個容器對象
vector<T, Alloc> *_pVec;//指向當前對象容器的指針
};
iterator begin()
{
return iterator(this, _first);
}
iterator end()
{
return iterator(this, _last);
}
//檢查迭代器失效
void verify(T *first, T *last)
{
Iterator_Base *pre = &this->_head;
Iterator_Base *it = this->_head._next;
while (it != nullptr)
{
if (it->_cur->_ptr > first && it->_cur->_ptr <= last)
{
//迭代器失效，把iterator持有的容器指針置nullptr
it->_cur->_pVec = nullptr;
//刪除當前迭代器節(jié)點，繼續(xù)判斷后面的迭代器節(jié)點是否失效
pre->_next = it->_next;
delete it;
it = pre->_next;
}
else
{
pre = it;
it = it->_next;
}
}
}
//自定義vector容器insert方法實現(xiàn)
iterator insert(iterator it, const T &val)
{
//1.這里我們未考慮擴容
//2.還未考慮it._ptr指針合法性，假設(shè)它合法
verify(it._ptr - 1, _last);
T *p = _last;
while (p > it._ptr)
{
_allocator.construct(p, *(p - 1));
_allocator.destroy(p - 1);
p--;
}
_allocator.construct(p, val);
_last++;
return iterator(this, p);
}
//自定義vector容器erase方法實現(xiàn)
iterator erase(iterator it)
{
verify(it._ptr - 1, _last);
T *p = it._ptr;
while (p < _last - 1)
{
_allocator.destroy(p);
_allocator.construct(p, *(p + 1));
p++;
}
_allocator.destroy(p);
_last--;
return iterator(this, it._ptr);
}
private:
T *_first;//起始數(shù)組位置
T *_last;//指向最后一個有效元素后繼位置
T *_end;//指向數(shù)組空間的后繼位置
Alloc _allocator;//定義容器的空間配置器對象
//容器迭代器失效增加代碼
struct Iterator_Base
{
Iterator_Base(iterator *c = nullptr, Iterator_Base *n = nullptr)
:_cur(c), _next(n) {}
iterator *_cur;
Iterator_Base *_next;
};
Iterator_Base _head;
void expand()//擴容
{
int size = _end - _first;
//T *ptmp = new T[2*size];
T *ptmp = _allocator.allocate(2 * size);
for (int i = 0; i < size; ++i)
{
_allocator.construct(ptmp + i, _first[i]);
//ptmp[i] = _first[i];
}
//delete[]_first;
for (T *p = _first; p != _last; ++p)
{
_allocator.destroy(p);
}
_allocator.deallocate(_first);
_first = ptmp;
_last = _first + size;
_end = _first + 2 * size;
}
};
int main()
{
vector<int> vec(200);
for (int i = 0; i < 10; ++i) {
vec.push_back(i);
}
//把vec容器中的所有偶數(shù)前面添加一個小于偶數(shù)值1的數(shù)字
auto it = vec.begin();
for (; it != vec.end(); ++it) {
if ((*it) % 2 == 0) {
it = vec.insert(it, *it - 1);
//it原來的位置插入了新的，需要++it兩次，才能到該偶數(shù)的后一個元素
++it;
}
}
for (auto val : vec) {
std::cout << val << " ";
}
return 0;
}
測試vector
#include <iostream>
//容器的空間配置器
template <typename T>
struct Allocator
{
T* allocate(size_t size)//只負責內(nèi)存開辟
{
return (T*)malloc(sizeof(T) * size);
}
void deallocate(void *p)//只負責內(nèi)存釋放
{
free(p);
}
void construct(T *p, const T &val)//已經(jīng)開辟好的內(nèi)存上，負責對象構(gòu)造
{
new (p) T(val);//定位new，指定內(nèi)存上構(gòu)造val，T(val)拷貝構(gòu)造
}
void destroy(T *p)//只負責對象析構(gòu)
{
p->~T();//~T()代表了T類型的析構(gòu)函數(shù)
}
};
template <typename T, typename Alloc = Allocator<T>>
class vector//向量容器
{
public:
vector(int size = 10)//構(gòu)造
{
//_first = new T[size];
_first = _allocator.allocate(size);
_last = _first;
_end = _first + size;
}
~vector()//析構(gòu)
{
//delete[]_first;
for (T *p = _first; p != _last; ++p)
{
_allocator.destroy(p);//把_first指針指向的數(shù)組的有效元素析構(gòu)
}
_allocator.deallocate(_first);//釋放堆上的數(shù)組內(nèi)存
_first = _last = _end = nullptr;
}
vector(const vector<T> &rhs)//拷貝構(gòu)造
{
int size = rhs._end - rhs._first;//空間大小
//_first = new T[size];
_first = _allocator.allocate(size);
int len = rhs._last - rhs._first;//有效元素
for (int i = 0; i < len; ++i)
{
//_first[i] = rhs._first[i];
_allocator.construct(_first + i, rhs._first[i]);
}
_last = _first + len;
_end = _first + size;
}
vector<T>& operator=(const vector<T> &rhs)//賦值運算符重載
{
if (this == &rhs)
{
return *this;
}
//delete[]_first;
for (T *p = _first; p != _last; ++p)
{
_allocator.destory(p);//把_first指針指向的數(shù)組的有效元素析構(gòu)
}
_allocator.deallocate(_first);//釋放堆上的數(shù)組內(nèi)存
int size = rhs._end - rhs._first;//空間大小
_first = _allocator.allocate(size);
int len = rhs._last - rhs._first;//有效元素
for (int i = 0; i < len; ++i)
{
_allocator.construct(_first + i, rhs._first[i]);
}
_last = _first + len;
_end = _first + size;
return *this;
}
void push_back(const T &val)//尾插
{
if (full())
{
expand();
}
//*_last++ = val;
_allocator.construct(_last, val);//_last指針指向的內(nèi)存構(gòu)造一個值為val的對象
_last++;
}
void pop_back()//尾刪
{
if (empty()) return;
verify(_last - 1, _last);
//erase(it); verift(it._ptr, _last);
//insert(it,val); verift(it._ptr, _last);
//--_last;
//不僅要把_last指針--，還需要析構(gòu)刪除的元素
--_last;
_allocator.destroy(_last);
}
T back()const//返回容器末尾元素值
{
return *(_last - 1);
}
bool full()const
{
return _last == _end;
}
bool empty()const
{
return _first == _last;
}
int size()const//返回容器中元素個數(shù)
{
return _last - _first;
}
T& operator[](int index)
{
if (index < 0 || index >= size())
{
throw "OutOfRangeException";
}
return _first[index];
}
//迭代器一般實現(xiàn)成容器的嵌套類型
class iterator
{
public:
friend class vector <T, Alloc>;
//新生成當前容器某一個位置元素的迭代器
iterator(vector<T, Alloc> *pvec = nullptr
, T *ptr = nullptr)
:_ptr(ptr), _pVec(pvec)
{
Iterator_Base *itb = new Iterator_Base(this, _pVec->_head._next);
_pVec->_head._next = itb;
}
bool operator!=(const iterator &it)const
{
//檢查迭代器的有效性
if (_pVec == nullptr || _pVec != it._pVec)//迭代器為空或迭代兩個不同容器
{
throw "iterator incompatable!";
}
return _ptr != it._ptr;
}
void operator++()
{
//檢查迭代器有效性
if (_pVec == nullptr)
{
throw "iterator incalid!";
}
_ptr++;
}
T& operator*()
{
//檢查迭代器有效性
if (_pVec == nullptr)
{
throw "iterator invalid!";
}
return *_ptr;
}
const T& operator*()const
{
if (_pVec == nullptr)
{
throw "iterator invalid!";
}
return *_ptr;
}
private:
T *_ptr;
//當前迭代器是哪個容器對象
vector<T, Alloc> *_pVec;//指向當前對象容器的指針
};
iterator begin()
{
return iterator(this, _first);
}
iterator end()
{
return iterator(this, _last);
}
//檢查迭代器失效
void verify(T *first, T *last)
{
Iterator_Base *pre = &this->_head;
Iterator_Base *it = this->_head._next;
while (it != nullptr)
{
if (it->_cur->_ptr > first && it->_cur->_ptr <= last)
{
//迭代器失效，把iterator持有的容器指針置nullptr
it->_cur->_pVec = nullptr;
//刪除當前迭代器節(jié)點，繼續(xù)判斷后面的迭代器節(jié)點是否失效
pre->_next = it->_next;
delete it;
it = pre->_next;
}
else
{
pre = it;
it = it->_next;
}
}
}
//自定義vector容器insert方法實現(xiàn)
iterator insert(iterator it, const T &val)
{
//1.這里我們未考慮擴容
//2.還未考慮it._ptr指針合法性，假設(shè)它合法
verify(it._ptr - 1, _last);
T *p = _last;
while (p > it._ptr)
{
_allocator.construct(p, *(p - 1));
_allocator.destroy(p - 1);
p--;
}
_allocator.construct(p, val);
_last++;
return iterator(this, p);
}
//自定義vector容器erase方法實現(xiàn)
iterator erase(iterator it)
{
verify(it._ptr - 1, _last);
T *p = it._ptr;
while (p < _last - 1)
{
_allocator.destroy(p);
_allocator.construct(p, *(p + 1));
p++;
}
_allocator.destroy(p);
_last--;
return iterator(this, it._ptr);
}
private:
T *_first;//起始數(shù)組位置
T *_last;//指向最后一個有效元素后繼位置
T *_end;//指向數(shù)組空間的后繼位置
Alloc _allocator;//定義容器的空間配置器對象
//容器迭代器失效增加代碼
struct Iterator_Base
{
Iterator_Base(iterator *c = nullptr, Iterator_Base *n = nullptr)
:_cur(c), _next(n) {}
iterator *_cur;
Iterator_Base *_next;
};
Iterator_Base _head;
void expand()//擴容
{
int size = _end - _first;
//T *ptmp = new T[2*size];
T *ptmp = _allocator.allocate(2 * size);
for (int i = 0; i < size; ++i)
{
_allocator.construct(ptmp + i, _first[i]);
//ptmp[i] = _first[i];
}
//delete[]_first;
for (T *p = _first; p != _last; ++p)
{
_allocator.destroy(p);
}
_allocator.deallocate(_first);
_first = ptmp;
_last = _first + size;
_end = _first + 2 * size;
}
};
int main()
{
vector<int> vec(200);
for (int i = 0; i < 10; ++i) {
vec.push_back(i);
}
//把vec容器中的所有偶數(shù)前面添加一個小于偶數(shù)值1的數(shù)字
auto it = vec.begin();
for (; it != vec.end(); ++it) {
if ((*it) % 2 == 0) {
it = vec.insert(it, *it - 1);
//it原來的位置插入了新的，需要++it兩次，才能到該偶數(shù)的后一個元素
++it;
}
}
for (auto val : vec) {
std::cout << val << " ";
}
return 0;
}
總結(jié)
到此這篇關(guān)于C++中vector迭代器失效問題的文章就介紹到這了,更多相關(guān)C++中vector迭代器失效內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
紅黑樹(Red?Black?Tre)是一種自平衡二叉查找樹,是在計算機科學中用到的一種數(shù)據(jù)結(jié)構(gòu),典型的用途是實現(xiàn)關(guān)聯(lián)數(shù)組,下面這篇文章主要給大家介紹了關(guān)于C++使用一棵紅黑樹同時封裝出map和set的相關(guān)資料,需要的朋友可以參考下2023-04-04
本篇文章是對正確使用語句塊進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了自己簡單封裝的一個CDialog類,實例分析了自定義封裝CDialog類的相關(guān)技巧,比較簡單易懂,需要的朋友可以參考下2015-04-04
在Qt自帶的控件中，也存在抽屜控件：QToolBar。但是，該控件有個缺點：一次只能展開一個抽屜信息，無法實現(xiàn)多個展開。所以本文將自定義實現(xiàn)復雜抽屜效果，需要的可以參考一下2022-10-10
這篇文章主要為大家詳細介紹了C++實現(xiàn)單鏈表的構(gòu)造，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-04-04
C++賦值函數(shù)+移動賦值函數(shù)+移動構(gòu)造函數(shù)詳解
這篇文章主要介紹了C++賦值函數(shù)+移動賦值函數(shù)+移動構(gòu)造函數(shù)詳解，文章圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-08-08
如果沒有計算器，我們?nèi)绾吻?的平方根2013-05-05
C語言MultiByteToWideChar和WideCharToMultiByte案例詳解
這篇文章主要介紹了C語言MultiByteToWideChar和WideCharToMultiByte案例詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-08-08![淺析int*p[ ]與int(*p)[ ]的區(qū)別](http://img.jbzj.com/images/xgimg/bcimg8.png)
以下是對int*p[ ]與int(*p)[ ]的區(qū)別進行了詳細的分析介紹，需要的朋友可以參考下2013-07-07
多維數(shù)組與多級指針是初學者經(jīng)常感覺迷糊的一個地方。超過二維的數(shù)組和超過二級的指針其實并不多用。但只要掌握一定的方法，理解多級指針和“多維”數(shù)組完全可以像理解一級指針和一維數(shù)組那樣簡單。2016-08-08