目录
开头:
我们想要去了解为什么会有迭代器失效,我们就要先去了解vector中的迭代器是怎么去实现的.
迭代器可能是一个类也可能是原生的指针,list的迭代器就是一个类来实现的,而我们的vector中的迭代器是用原生指针来实现的.
typedef T* iterator;
typedef const T* const_iterator;
这里的T指的是模版参数.
1.什么是迭代器失效
这里的vector中的迭代器是原生的指针,所以出现迭代器失效有以下情况.
1.野指针(指向非法的空间)和空指针
2.迭代器的指向有问题
2.为什么会出现迭代器失效
常见的迭代器失效有多种情况insert和erase,push_back等会导致迭代器失效.
2.1 insert
我们来看一下我们模拟实现的insert是怎么样的.
void insert(iterator pos , const T& x) {
//判断迭代器位置是否合法
assert(pos >= _start && pos <= _finish);
//判断是否需要扩容
if (_finish == _end_of_storage) {
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
//移动数据
iterator end = _finish - 1;
while (end >= pos) {
*(end + 1) = *end;
--end;
}
_finish++;
*(pos) = x;
} 我们在插入数据的时候会出现问题而且这个问题是偶然发生的.
我们看两种情况一个插入成功,一个出现了随机值是为什么？想要去明白为什么,就要去理解vector的内部insert实现是什么情况.
第一种情况没有出现问题是以为没有发生扩容,第二中情况发生了问题是因为发生了扩容.发生了扩容就会导致野指针的问题.
第一种情况:
第二中情况:
我们看到扩容之后会导致野指针的问题,pos还是指向原来的位置而_start和_finish指向新的空间.会导致我们的循环不进去_finish直接加加,对pos的解引用不会影响到新的空间.所以会出现随机值.
解决方法:
我们只需要保存pos到_start的距离,就是size_t sz = pos - _start. 扩容完成之后再加上就可以了. pos = _start + sz; 就是要修改pos的位置.在返回pos位置的迭代器就可以了.
修改后的代码:
iterator insert(iterator pos , const T& x) {
//判断迭代器位置是否合法
assert(pos >= _start && pos <= _finish);
//判断是否需要扩容
if (_finish == _end_of_storage) {
//保存pos到_start的距离
size_t sz = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
//更新pos的位置
pos = _start + sz;
}
//移动数据
iterator end = _finish - 1;
while (end >= pos) {
*(end + 1) = *end;
--end;
}
_finish++;
*(pos) = x;
return pos;
}
修改成功就能正常插入了.
2.2 erase
erase删除不会出现野指针的问题,会出现迭代器的指向失效的问题.
我们可以看一下erase的内部实现.
void erase(iterator pos) {
assert(pos >= _start && pos < _finish);
if (_start) {
iterator end = pos + 1;
while (end < _finish) {
*(end - 1) = *end;
end++;
}
--_finish;
}
}例如我们要删除vector中所有的偶数,
这个就是典型的迭代器指向发生改变导致迭代器失效.我们来分析一下为什么会有迭代器失效.
那么我们应该要怎么去解决这个问题呢？我们可以返回删除完成之后pos位置的迭代器这样就完成了.
修改后的代码:
iterator erase(iterator pos) {
assert(pos >= _start && pos < _finish);
if (_start) {
iterator end = pos + 1;
while (end < _finish) {
*(end - 1) = *end;
end++;
}
--_finish;
}
return pos;
}
我们看这样结果就正确了.
3.总结
迭代器使用之后,不要在重复使用否则会导致迭代器失效.