一、容器与迭代器

1.1 STL容器

容器是用来管理一大群元素的，为了适应不同需要，STL提供了不同的容器。

在C++中，容器被定义为：在数据存储上，有一种对象类型，它可以持有其他对象或指向其他对象的指针，这种对象类型就叫做容器。简单理解，即容器就是保存其他对象的对象。而且，这种“对象”还有处理“其他对象”的方法。

 STL将通用容器分为了三类：顺序性容器、关联式容器、容器适配器。

顺序容器：将单一类型元素聚集起来成为容器，然后根据位置来存储和访问这些元素。主要有vector、list、deque（双端队列）。顺序容器适配器：stack、queue和priority_queue。
关联容器：支持通过键来高效地查找和读取元素。主要有：pair、set、map、multiset和multimap。

标准容器类    说明
（1）顺序性容器
vector    从后面快速的插入与删除，直接访问任何元素
deque    从前面或后面快速的插入与删除，直接访问任何元素
list    双链表，从任何地方快速插入与删除
（2）关联容器
set    快速查找，不允许重复值
multiset    快速查找，允许重复值
map    一对多映射，基于关键字快速查找，不允许重复值
multimap    一对多映射，基于关键字快速查找，允许重复值
（3）容器适配器
stack    后进先出
queue    先进先出
priority_queue    最高优先级元素总是第一个出列

1.2 迭代器

  迭代器是为了表示容器中某个元素位置这个概念而产生的，是一种检查容器内元素并遍历元素的数据类型。C++更趋向于使用迭代器而非下标进行操作，因为标准库（STL）为每一种标准容器定义了一种迭代器类型，而只有少数容器支持下标操作访问容器元素。每种容器都定义了自己的迭代器类型。

迭代器可以指向容器中的某个元素，通过迭代器就可以读写它指向的元素。从这一点上看，迭代器和指针类似。

二、容器的删除

2.1 关联容器的删除

对于关联容器(如map, set,multimap,multiset)，删除当前的iterator，仅仅会使当前的iterator失效，只要在erase时，递增当前iterator即可。这是因为map之类的容器，使用了红黑树来实现，插入、删除一个结点不会对其他结点造成影响。erase迭代器只是被删元素的迭代器失效，但是返回值为void，所以要采用erase(iter++)的方式删除迭代器。

AssociContainer <int> c;　　//关联容器：map multimap set multiset

for(auto it=c.begin();it!=c.end();)

{

　　if(badValue(*it))
　　　　c.erase(it++);　　//关联容器erase返回值为void
　　else
　　　　　++it;
}

错误的用法：删除迭代器后又 ++ 操作。

    //删除操作引发迭代器失效
    for (iter = dataMap.begin(); iter != dataMap.end();iter++)
     {
             int nKey = iter->first;
             string strValue = iter->second;
  
            if (nKey % 2 == 0)
            {
                 dataMap.erase(iter);    //错误 
  
            }
            /* cout<<iter->second<<endl;*/
     }

说明：c.erase(it++) 会把it的旧值传给erase，但在erase开始执行之前it会自增，正好符合我们的期望。关联容器这样写没有任何问题，迭代器不会失效

解析：dataMap.erase(iter++);这句话分三步走，先把iter传值到erase里面，然后iter自增，然后执行erase,所以iter在失效前已经自增了。

2.2 顺序容器的删除

对于序列式容器(如vector,deque)，序列式容器就是数组式容器，删除当前的iterator会使后面所有元素的iterator都失效。这是因为vetor,deque使用了连续分配的内存，删除一个元素导致后面所有的元素会向前移动一个位置。所以不能使用erase(iter++)的方式，还好erase方法可以返回下一个有效的iterator。

SeqContainer<int> c;　　//顺序容器:vector list deque

for(auto it=c.begin();it!=c.end();)

{
　　if(badValue(*it))
　　　　it=c.erase(it);　　//顺序容器的erase返回的是下一个迭代器
　　else
　　　　++it;
}

迭代器失效的情况：

void vectorTest()
{
    vector<int> container;
    for (int i = 0; i < 10; i++)
    {
        container.push_back(i);
    }

    vector<int>::iterator iter;
     for (iter = container.begin(); iter != container.end(); iter++)
    {
            if (*iter > 3)
              container.erase(iter); //删除iter后，iter++报错
    }

     for (iter = container.begin(); iter != container.end(); iter++)
    {
            cout<<*iter<<endl;
    }
}

 总结：vector是一个顺序容器，在内存中是一块连续的内存，当删除一个元素后，内存中的数据会发生移动，以保证数据的紧凑。所以删除一个数据后，其他数据的地址发生了变化，之前获取的迭代器根据原有的信息就访问不到正确的数据。

根本原因是顺序容器是连续内存，你erase一个元素之后，后面的元素都要向前移动一个位置，不仅迭代器it失效，包括后面的所有迭代器都失效；同样你也能想象，insert元素也是同样的道理。

2.3 链表式容器

对于同样不连续内存容器list来说，因为其erase方法的灵活性，使用法则跟关联型容器一致

对于链表式容器(如list)，删除当前的iterator，仅仅会使当前的iterator失效，这是因为list之类的容器，使用了链表来实现，插入、删除一个结点不会对其他结点造成影响。只要在erase时，递增当前iterator即可，并且erase方法可以返回下一个有效的iterator。

方式一:递增当前iterator

for (iter = cont.begin(); it != cont.end();)
{
   (*iter)->doSomething();
   if (shouldDelete(*iter))
      cont.erase(iter++);
   else
      ++iter;
}

方式二:通过erase获得下一个有效的iterator

for (iter = cont.begin(); iter != cont.end();)
{
   (*it)->doSomething();
   if (shouldDelete(*iter))
      iter = cont.erase(iter);  //erase删除元素，返回下一个迭代器
   else
      ++iter;
}

三、总结

迭代器失效分三种情况考虑，也是分三种数据结构考虑，分别为数组型，链表型，树型数据结构。

数组型数据结构：该数据结构的元素是分配在连续的内存中，insert和erase操作，都会使得删除点和插入点之后的元素挪位置，所以，插入点和删除掉之后的迭代器全部失效，也就是说insert(*iter)(或erase(*iter))，然后在iter++，是没有意义的。解决方法：erase(*iter)的返回值是下一个有效迭代器的值。 iter =cont.erase(iter);

链表型数据结构：对于list型的数据结构，使用了不连续分配的内存，删除运算使指向删除位置的迭代器失效，但是不会失效其他迭代器.解决办法两种，erase(*iter)会返回下一个有效迭代器的值，或者erase(iter++).

树形数据结构： 使用红黑树来存储数据，插入不会使得任何迭代器失效；删除运算使指向删除位置的迭代器失效，但是不会失效其他迭代器.erase迭代器只是被删元素的迭代器失效，但是返回值为void，所以要采用erase(iter++)的方式删除迭代器。

参考文献：

【1】迭代器失效问题：STL容器如何正确删除元素（迭代器失效问题） - 划水程序员 - 博客园

【2】C++迭代器失效的几种情况总结：C++迭代器失效的几种情况总结 - Boblim - 博客园

【3】C++容器和迭代器：C++容器和迭代器_韶光-CSDN博客_容器迭代器

【4】STL的迭代器erase方法： STL的迭代器erase方法 - 知乎