C++中vector迭代器失效是怎么回事，该怎么办
导读：在实际案例的操作过程中，我们可能会遇到“C++中vector迭代器失效是怎么回事，该怎么办”这样的问题，那么我们该如何处理和解决这样的情况呢？这篇小编就给大家总结了一些方法，具有一定的借鉴价值，希望对大家有所帮助，接下来就让小编带领大家一起...
在实际案例的操作过程中，我们可能会遇到“C++中vector迭代器失效是怎么回事，该怎么办”这样的问题，那么我们该如何处理和解决这样的情况呢？这篇小编就给大家总结了一些方法，具有一定的借鉴价值，希望对大家有所帮助，接下来就让小编带领大家一起了解看看吧。问题：
（1）删除vector中所有的偶数
#include iostream>
#include vector>
using namespace std;
int main()
{
vectorint>
vec;
for (int i = 0;
i 10;
++i) {
vec.push_back(i);
}
//把vec容器中的所有偶数删除
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()
{
vectorint>
vec;
for (int i = 0;
i 10;
++i) {
vec.push_back(i);
}
//把vec容器中的所有偶数前面添加一个小于偶数值1的数字
auto it = vec.begin();
for (;
it != vec.end();
++it) {
if ((*it) % 2 == 0) {
vec.insert(it,*it-1);
}
}
return 0;
}
运行导致程序崩溃！
原因：iterator失效
当删除（获取增加）it位置的元素时，导致it后面的迭代器全部失效。因此多次调用erase insert导致崩溃
迭代器失效原因
1 当容器调用erase时，当前位置到容器末尾元素的所有的迭代器全部失效
2 当容器调用insert时，当前位置到容器末尾元素的所有的迭代器全部失效；
3 当容器调用insert时，如果引起容器内存扩容，原来容器的所有的迭代器就全部失效
解决：
进行更新操作：erase（insert）后会返回指向下一个元素的迭代器
解释：vector::erase - C++ Reference
从向量中删除单个元素（位置）或一系列元素（[第一、最后一个]）。
这有效地减少了容器的大小，减少了被删除的元素的数量，这些元素会被销毁。
由于向量使用数组作为其底层存储，擦除向量端以外位置的元素会导致容器在段擦除后将所有元素重新定位到其新位置。与其他类型的序列容器对相同操作执行的操作相比，这通常是一种低效的操作（如列表或转发列表）。
同理有：vector::insert - C++ Reference
通过在指定位置的元素之前插入新元素来扩展向量，从而通过插入的元素数量有效地增加容器大小。
当且仅当新向量大小超过当前向量容量时，这会导致自动重新分配分配分配的存储空间。
因为向量使用数组作为其底层存储，所以在向量末端以外的位置插入元素会导致容器将位置之后的所有元素重新定位到它们的新位置。与其他类型的序列容器（如list或forward_list）对相同操作执行的操作相比，这通常是一种低效的操作。
这些参数确定插入的元素数量及其初始化值：
也说明了进行插入操作会导致之后的迭代器失效
修改代码：
#include iostream>
#include vector>
using namespace std;
int main()
{
vectorint>
vec;
for (int i = 0;
i 10;
++i) {
vec.push_back(i);
}
//把vec容器中的所有偶数删除
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()
{
vectorint>
vec;
for (int i = 0;
i 10;
++i) {
vec.push_back(i);
}
//把vec容器中的所有偶数前面添加一个小于偶数值1的数字
auto it = vec.begin();
for (;
it != vec.end();
++it) {
if ((*it) % 2 == 0) {
it = vec.insert(it, *it - 1);
//it原来的位置插入了新的，需要++it两次，才能到该偶数的后一个元素
++it;
}
}
for (auto val : vec) {
cout val " ";
}
return 0;
}
这样就没有问题。
vector中实现
https://www.jb51.net/article/229393.htm接该文最终实现的vector上继续：
头插法：
检查迭代器失效：
在进行删除或增加的时候，要检测该位置到last位置，使其迭代器失效
void pop_back() // 从容器末尾删除元素
{
if (empty())
return;
//检查迭代器 从该位置到最后
verify(_last-1,_last);
// 不仅要把_last指针--，还需要析构删除的元素
--_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;
//删除当前迭代器节点，继续判断后面的迭代器是否失效
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)//只负责内存开辟
{
return (T*)malloc(sizeof(T) * size);
}
void deallocate(void *p)//只负责内存释放
{
free(p);
}
void construct(T *p, const T &
val)//已经开辟好的内存上，负责对象构造
{
new (p) T(val);
//定位new，指定内存上构造val，T(val)拷贝构造
}
void destroy(T *p)//只负责对象析构
{
p->
~T();
//~T()代表了T类型的析构函数
}
}
;
template typename T, typename Alloc = AllocatorT>
>
class vector//向量容器
{
public:
vector(int size = 10)//构造
{
//_first = new T[size];
_first = _allocator.allocate(size);
_last = _first;
_end = _first + size;
}
~vector()//析构
{
//delete[]_first;
for (T *p = _first;
p != _last;
++p)
{
_allocator.destroy(p);
//把_first指针指向的数组的有效元素析构
}
_allocator.deallocate(_first);
//释放堆上的数组内存
_first = _last = _end = nullptr;
}
vector(const vectorT>
&
rhs)//拷贝构造
{
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;
}
vectorT>
&
operator=(const vectorT>
&
rhs)//赋值运算符重载
{
if (this == &
rhs)
{
return *this;
}
//delete[]_first;
for (T *p = _first;
p != _last;
++p)
{
_allocator.destory(p);
//把_first指针指向的数组的有效元素析构
}
_allocator.deallocate(_first);
//释放堆上的数组内存
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指针指向的内存构造一个值为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指针--，还需要析构删除的元素
--_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//返回容器中元素个数
{
return _last - _first;
}
T&
operator[](int index)
{
if (index 0 || index >
= size())
{
throw "OutOfRangeException";
}
return _first[index];
}
//迭代器一般实现成容器的嵌套类型
class iterator
{
public:
friend class vector T, Alloc>
;
//新生成当前容器某一个位置元素的迭代器
iterator(vectorT, 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;
//当前迭代器是哪个容器对象
vectorT, 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;
//删除当前迭代器节点，继续判断后面的迭代器节点是否失效
pre->
_next = it->
_next;
delete it;
it = pre->
_next;
}
else
{
pre = it;
it = it->
_next;
}
}
}
//自定义vector容器insert方法实现
iterator insert(iterator it, const T &
val)
{
//1.这里我们未考虑扩容
//2.还未考虑it._ptr指针合法性，假设它合法
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方法实现
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;
//起始数组位置
T *_last;
//指向最后一个有效元素后继位置
T *_end;
//指向数组空间的后继位置
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()
{
vectorint>
vec(200);
for (int i = 0;
i 10;
++i) {
vec.push_back(i);
}
//把vec容器中的所有偶数前面添加一个小于偶数值1的数字
auto it = vec.begin();
for (;
it != vec.end();
++it) {
if ((*it) % 2 == 0) {
it = vec.insert(it, *it - 1);
//it原来的位置插入了新的，需要++it两次，才能到该偶数的后一个元素
++it;
}
}
for (auto val : vec) {
std::cout val " ";
}
return 0;
}
测试vector
#include iostream>
//容器的空间配置器
template typename T>
struct Allocator
{
T* allocate(size_t size)//只负责内存开辟
{
return (T*)malloc(sizeof(T) * size);
}
void deallocate(void *p)//只负责内存释放
{
free(p);
}
void construct(T *p, const T &
val)//已经开辟好的内存上，负责对象构造
{
new (p) T(val);
//定位new，指定内存上构造val，T(val)拷贝构造
}
void destroy(T *p)//只负责对象析构
{
p->
~T();
//~T()代表了T类型的析构函数
}
}
;
template typename T, typename Alloc = AllocatorT>
>
class vector//向量容器
{
public:
vector(int size = 10)//构造
{
//_first = new T[size];
_first = _allocator.allocate(size);
_last = _first;
_end = _first + size;
}
~vector()//析构
{
//delete[]_first;
for (T *p = _first;
p != _last;
++p)
{
_allocator.destroy(p);
//把_first指针指向的数组的有效元素析构
}
_allocator.deallocate(_first);
//释放堆上的数组内存
_first = _last = _end = nullptr;
}
vector(const vectorT>
&
rhs)//拷贝构造
{
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;
}
vectorT>
&
operator=(const vectorT>
&
rhs)//赋值运算符重载
{
if (this == &
rhs)
{
return *this;
}
//delete[]_first;
for (T *p = _first;
p != _last;
++p)
{
_allocator.destory(p);
//把_first指针指向的数组的有效元素析构
}
_allocator.deallocate(_first);
//释放堆上的数组内存
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指针指向的内存构造一个值为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指针--，还需要析构删除的元素
--_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//返回容器中元素个数
{
return _last - _first;
}
T&
operator[](int index)
{
if (index 0 || index >
= size())
{
throw "OutOfRangeException";
}
return _first[index];
}
//迭代器一般实现成容器的嵌套类型
class iterator
{
public:
friend class vector T, Alloc>
;
//新生成当前容器某一个位置元素的迭代器
iterator(vectorT, 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;
//当前迭代器是哪个容器对象
vectorT, 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;
//删除当前迭代器节点，继续判断后面的迭代器节点是否失效
pre->
_next = it->
_next;
delete it;
it = pre->
_next;
}
else
{
pre = it;
it = it->
_next;
}
}
}
//自定义vector容器insert方法实现
iterator insert(iterator it, const T &
val)
{
//1.这里我们未考虑扩容
//2.还未考虑it._ptr指针合法性，假设它合法
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方法实现
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;
//起始数组位置
T *_last;
//指向最后一个有效元素后继位置
T *_end;
//指向数组空间的后继位置
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()
{
vectorint>
vec(200);
for (int i = 0;
i 10;
++i) {
vec.push_back(i);
}
//把vec容器中的所有偶数前面添加一个小于偶数值1的数字
auto it = vec.begin();
for (;
it != vec.end();
++it) {
if ((*it) % 2 == 0) {
it = vec.insert(it, *it - 1);
//it原来的位置插入了新的，需要++it两次，才能到该偶数的后一个元素
++it;
}
}
for (auto val : vec) {
std::cout val " ";
}
return 0;
}
总结
以上就是关于“C++中vector迭代器失效是怎么回事，该怎么办”的介绍了，感谢各位的阅读，希望文本对大家有所帮助。如果想要了解更多知识，欢迎关注网络，小编每天都会为大家更新不同的知识。
声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！
若转载请注明出处： C++中vector迭代器失效是怎么回事，该怎么办
本文地址： https://pptw.com/jishu/653170.html