問題：

（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;
}

運(yùn)行導(dǎo)致程序崩潰！

（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ù)前面添加一個(gè)小于偶數(shù)值1的數(shù)字
auto it = vec.begin();
for (; it != vec.end(); ++it) {
  if ((*it) % 2 == 0) {
    vec.insert(it,*it-1);
  }
}
return 0;
}

運(yùn)行導(dǎo)致程序崩潰！

原因：iterator失效

當(dāng)刪除（獲取增加）it位置的元素時(shí)，導(dǎo)致it后面的迭代器全部失效。因此多次調(diào)用erase insert導(dǎo)致崩潰

迭代器失效原因

1 當(dāng)容器調(diào)用erase時(shí)，當(dāng)前位置到容器末尾元素的所有的迭代器全部失效

2 當(dāng)容器調(diào)用insert時(shí)，當(dāng)前位置到容器末尾元素的所有的迭代器全部失效；

3 當(dāng)容器調(diào)用insert時(shí)，如果引起容器內(nèi)存擴(kuò)容，原來容器的所有的迭代器就全部失效

解決：

進(jìn)行更新操作：erase（insert）后會(huì)返回指向下一個(gè)元素的迭代器

解釋：vector::erase - C++ Reference

從向量中刪除單個(gè)元素（位置）或一系列元素（[第一、最后一個(gè)]）。
這有效地減少了容器的大小，減少了被刪除的元素的數(shù)量，這些元素會(huì)被銷毀。
由于向量使用數(shù)組作為其底層存儲(chǔ)，擦除向量端以外位置的元素會(huì)導(dǎo)致容器在段擦除后將所有元素重新定位到其新位置。與其他類型的序列容器對(duì)相同操作執(zhí)行的操作相比，這通常是一種低效的操作（如列表或轉(zhuǎn)發(fā)列表）。

同理有：vector::insert - C++ Reference

通過在指定位置的元素之前插入新元素來擴(kuò)展向量，從而通過插入的元素?cái)?shù)量有效地增加容器大小。

當(dāng)且僅當(dāng)新向量大小超過當(dāng)前向量容量時(shí)，這會(huì)導(dǎo)致自動(dòng)重新分配分配分配的存儲(chǔ)空間。

因?yàn)橄蛄渴褂脭?shù)組作為其底層存儲(chǔ)，所以在向量末端以外的位置插入元素會(huì)導(dǎo)致容器將位置之后的所有元素重新定位到它們的新位置。與其他類型的序列容器（如list或forward_list）對(duì)相同操作執(zhí)行的操作相比，這通常是一種低效的操作。
這些參數(shù)確定插入的元素?cái)?shù)量及其初始化值：

也說明了進(jìn)行插入操作會(huì)導(dǎo)致之后的迭代器失效

修改代碼：

#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ù)前面添加一個(gè)小于偶數(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ù)的后一個(gè)元素
    ++it;
  }
}

for (auto val : vec) {
  cout << val << " ";
}
return 0;
}

這樣就沒有問題。

vector中實(shí)現(xiàn) ??????

http://m.ythuaji.com.cn/article/226666.html接該文最終實(shí)現(xiàn)的vector上繼續(xù)：

頭插法：

檢查迭代器失效：

在進(jìn)行刪除或增加的時(shí)候，要檢測(cè)該位置到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;//刪除當(dāng)前迭代器節(jié)點(diǎn)，繼續(xù)判斷后面的迭代器是否失效
      delete it;
      it = pre->_next;
    }
    else {
      pre = it;
      it = it->_next;
    }
  
  }
}

insert

//insert
iterator insert(iterator it, const T&val) {
   //未考慮擴(kuò)容和it._ptr的合法性 todo
  verify(it._ptr - 1, _last);
  //依次向后移動(dòng)一個(gè)位置
  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)//只負(fù)責(zé)內(nèi)存開辟
{
  return (T*)malloc(sizeof(T) * size);
}
void deallocate(void *p)//只負(fù)責(zé)內(nèi)存釋放
{
  free(p);
}
void construct(T *p, const T &val)//已經(jīng)開辟好的內(nèi)存上，負(fù)責(zé)對(duì)象構(gòu)造
{
  new (p) T(val);//定位new，指定內(nèi)存上構(gòu)造val，T(val)拷貝構(gòu)造
}
void destroy(T *p)//只負(fù)責(zé)對(duì)象析構(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)//賦值運(yùn)算符重載
{
  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)造一個(gè)值為val的對(duì)象
  _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//返回容器中元素個(gè)數(shù)
{
  return _last - _first;
}
T& operator[](int index)
{
  if (index < 0 || index >= size())
  {
    throw "OutOfRangeException";
  }
  return _first[index];
}
//迭代器一般實(shí)現(xiàn)成容器的嵌套類型
class iterator
{
public:
  friend class vector <T, Alloc>;
  //新生成當(dāng)前容器某一個(gè)位置元素的迭代器
  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)//迭代器為空或迭代兩個(gè)不同容器
    {
      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;
  //當(dāng)前迭代器是哪個(gè)容器對(duì)象
  vector<T, Alloc> *_pVec;//指向當(dāng)前對(duì)象容器的指針
};
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;
      //刪除當(dāng)前迭代器節(jié)點(diǎn)，繼續(xù)判斷后面的迭代器節(jié)點(diǎn)是否失效
      pre->_next = it->_next;
      delete it;
      it = pre->_next;
    }
    else
    {
      pre = it;
      it = it->_next;
    }
  }
}

//自定義vector容器insert方法實(shí)現(xiàn)
iterator insert(iterator it, const T &val)
{
  //1.這里我們未考慮擴(kuò)容
  //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方法實(shí)現(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;//指向最后一個(gè)有效元素后繼位置
T *_end;//指向數(shù)組空間的后繼位置
Alloc _allocator;//定義容器的空間配置器對(duì)象

//容器迭代器失效增加代碼
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()//擴(kuò)容
{
  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ù)前面添加一個(gè)小于偶數(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ù)的后一個(gè)元素
    ++it;
  }
}

for (auto val : vec) {
  std::cout << val << " ";
}

return 0;
}

測(cè)試vector

#include <iostream>

//容器的空間配置器
template <typename T>
struct Allocator
{
T* allocate(size_t size)//只負(fù)責(zé)內(nèi)存開辟
{
  return (T*)malloc(sizeof(T) * size);
}
void deallocate(void *p)//只負(fù)責(zé)內(nèi)存釋放
{
  free(p);
}
void construct(T *p, const T &val)//已經(jīng)開辟好的內(nèi)存上，負(fù)責(zé)對(duì)象構(gòu)造
{
  new (p) T(val);//定位new，指定內(nèi)存上構(gòu)造val，T(val)拷貝構(gòu)造
}
void destroy(T *p)//只負(fù)責(zé)對(duì)象析構(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)//賦值運(yùn)算符重載
{
  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)造一個(gè)值為val的對(duì)象
  _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//返回容器中元素個(gè)數(shù)
{
  return _last - _first;
}
T& operator[](int index)
{
  if (index < 0 || index >= size())
  {
    throw "OutOfRangeException";
  }
  return _first[index];
}
//迭代器一般實(shí)現(xiàn)成容器的嵌套類型
class iterator
{
public:
  friend class vector <T, Alloc>;
  //新生成當(dāng)前容器某一個(gè)位置元素的迭代器
  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)//迭代器為空或迭代兩個(gè)不同容器
    {
      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;
  //當(dāng)前迭代器是哪個(gè)容器對(duì)象
  vector<T, Alloc> *_pVec;//指向當(dāng)前對(duì)象容器的指針
};
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;
      //刪除當(dāng)前迭代器節(jié)點(diǎn)，繼續(xù)判斷后面的迭代器節(jié)點(diǎn)是否失效
      pre->_next = it->_next;
      delete it;
      it = pre->_next;
    }
    else
    {
      pre = it;
      it = it->_next;
    }
  }
}

//自定義vector容器insert方法實(shí)現(xiàn)
iterator insert(iterator it, const T &val)
{
  //1.這里我們未考慮擴(kuò)容
  //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方法實(shí)現(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;//指向最后一個(gè)有效元素后繼位置
T *_end;//指向數(shù)組空間的后繼位置
Alloc _allocator;//定義容器的空間配置器對(duì)象

//容器迭代器失效增加代碼
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()//擴(kuò)容
{
  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ù)前面添加一個(gè)小于偶數(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ù)的后一個(gè)元素
    ++it;
  }
}

for (auto val : vec) {
  std::cout << val << " ";
}

return 0;
}

總結(jié)

到此這篇關(guān)于C++中vector迭代器失效問題的文章就介紹到這了,更多相關(guān)C++中vector迭代器失效內(nèi)容請(qǐng)搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！

原文鏈接：https://blog.csdn.net/LIJIWEI0611/article/details/121318554