首页 > 资讯 > 后端开发 > 其他教程 >C++中vector迭代器失效问题详解

272

分享到

C++中vector迭代器失效问题详解

2024-04-02 19:04:59 272人浏览八月长安

摘要

目录问题：（1）删除vector中所有的偶数（2）vector容器插入元素问题迭代器失效原因解决：总结问题：（1）删除vector中所有的偶数 #i

问题：

（1）删除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容器中的所有偶数删除
  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容器中的所有偶数前面添加一个小于偶数值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()
{
  vector<int> 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()
{
  vector<int> 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 = Allocator<T>>
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 vector<T> &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;
  }
  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指针指向的数组的有效元素析构
    }
    _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(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;
        //删除当前迭代器节点，继续判断后面的迭代器节点是否失效
        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()
{
  vector<int>   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 = Allocator<T>>
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 vector<T> &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;
  }
  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指针指向的数组的有效元素析构
    }
    _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(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;
        //删除当前迭代器节点，继续判断后面的迭代器节点是否失效
        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()
{
  vector<int>   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迭代器失效问题的文章就介绍到这了,更多相关C++中vector迭代器失效内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

--结束END--

本文标题: C++中vector迭代器失效问题详解

本文链接: https://lsjlt.com/news/157498.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

回答

如何调试操作系统的错误？
操作系统

2023-11-15发布

回答

操作系统中的I/O系统是如何实现的？
操作系统

2023-11-15发布

回答

如何实现操作系统的内存管理？
操作系统

2023-11-15发布

回答

什么是虚拟内存，它对操作系统有什么影响？
操作系统

2023-11-15发布

回答

ASP中的MVC架构和WebForms架构有什么区别和使用场景？
ASP.NET

2023-11-15发布

回答

ASP中的数据验证和数据校验有什么不同？
ASP.NET

2023-11-15发布

回答

ASP中的ADO对象和DAO对象有什么区别和使用方法？
ASP.NET

2023-11-15发布

回答

Node.js中的包管理器NPM是什么？如何使用它进行依赖管理？
node.js

2023-11-15发布

回答

Vue.js中的动态组件是什么？如何使用它来动态渲染组件？
VUE

2023-11-15发布

回答

如何使用Vue.js实现懒加载和预加载？
VUE

2023-11-15发布

C++中vector迭代器失效问题详解

目录

问题：

（1）删除vector中所有的偶数

（2）vector容器插入元素问题

迭代器失效原因

解决：

总结

C++中vector迭代器失效问题详解

C++Vector迭代器失效问题的解决方法

C/C++迭代器的失效问题详解

[C++] STL_vector 迭代器失效问题

C++迭代器失效问题及解决

Scrapy之迭代爬取网页中失效问题及解决

C++迭代器iterator详解

c++迭代器失效的情况有哪些

map迭代器遍历失效怎么解决

C++模拟实现List迭代器详解

详解nodejs中的异步迭代器

vue中@keyup.enter失效问题及解决

C++中vector和数组之间的转换及其效率问题怎么解决

详解C++ 的STL迭代器原理和实现

C++中常见的代码优化问题详解

C++中常见的代码重用问题详解

C++中常见的代码复用问题详解

Java中Iterator(迭代器)的用法详解

Java中Iterator迭代器的使用详解

详解ES6 中的迭代器和生成器

c语言怎么计算字符串长度

c++排序函数sort怎么使用

C++中beginthreadex线程启动不了怎么解决

c语言swap函数如何调用

c++中使用swap函数报错怎么解决

c++中decltype的用法是什么

c语言中sizeof语句怎么使用

C语言怎么实现对文件夹加密

c语言怎么将小数转换成整数

C++中coledatetime函数的用法是什么