STL之迭代器&&迭代器失效

Dear 丶 2022-05-17 12:46 341阅读 0赞

## **1.说说设计模式？（迭代器模式）** ##

迭代器模式作为STL的六大组件之一，通俗来讲，它就是用来遍历容器的，对容器进行一定的操作。我们通常使用的容器vector、list、map、set、multimap、multiset、deque，内部是实现有顺序表、链表、红黑树。如果我们遍历这些容器就要明白它们的底层构造，相当不方便。iterator被定义出来就是不需要了解这些容器的底层实现，来访问修改容器中的数据。也就是说：**iterator模式是一种运用于聚合对象的一种模式。通过iterator模式，我们可以在不知道对象内部表示的情况下，按照iterator提供的方法访问聚合对象中的各个元素。**

**作用**：**能够让迭代器与算法互不干扰的相互发展，最后又能无间隙的粘合在一起。**

vector<int> v1{ 1, 2, 3, 4, 5, 6 };
    
    vector<int>::iterator iter = v1.begin();
    
    while (iter!= v1.end())
    
    {
    
         *iter = " ";     //不能对其赋值
    
         /*cout << *iter << " ";
    
         ++iter;*/
    
    }

## **2.迭代器失效的原理及解决办法** ##

**1**.  **对于序列式容器（vector，deque），删除当前的iterator会使后面所有的元素的迭代器都失效。**因为数组式容器都是使用的连续分配的内存，删除一个元素会使后面的元素都往前移动一个位置，所以使用erase函数删除数据时，iterator++指向的是未知的区域。 所以删除一个数据后，其他数据的地址发生了变化，之前获取的迭代器根据原有的信息就访问不到正确的数据。只要改一下代码使其返回下一个有效的迭代器就可以了。

for (iter = container.begin(); iter != container.end();)
    
    {
    
          if (*iter % 2 == 0)
    
               iter = container.erase(iter);    //erase的返回值是删除元素下一个元素的迭代器
    
          else{
    
               iter++;
    
          }
    
    }

**2. 对于关联容器（map、set、multiset、multimap），删除当前的iterator只会使当前的迭代器失效，只要在删除时，递增当前的iterator即可。**这是因为map之类的容器是由红黑树实现的，对红黑树插入或者删除结点不会对其他结点造成影响。erase迭代器，只是被删除的迭代器失效，返回为void，只需要采用erase(it++)的方式删除迭代器。 map.erase(iter)之后,iter就已经失效了，所以iter无法自增，即iter++就会出bug.解决方案，就是在iter失效之前，先自增。

擦除操作引发迭代器失效
    
    for (iter = map.begin(); iter != map1.end(); )
    
    {
            int Key = iter->first;
            string strValue = iter->second;
            if (Key % 2 == 0)
            {
                //map<int, string>::iterator  tmpIter = iter;
                //iter++;
                //map1.erase(tmpIter);
    
    
                map1.erase(iter++);    //先把iter传值到erase里面，然后iter自增，然后执行erase
            }
            else
            {
                iter ++;
            }
    }
    
    
    map<int, string>::iterator tmpIter =iter; 
    iter++;
    dataMap.erase(tmpIter);
    
    //这几句的意思是,先保留要删除的节点迭代器，再让iter向下一个有意义的节点，然后删除节点。
    所以这个操作结束后iter指向的是下一个有意义的节点，没有失效。

**3.容器list是使用不连续分配的内存，在调用erase函数进行删除某一个结点时，导致这个结点的迭代器失效。**因为在将结点删除以后，没有改变当前迭代器的指向。第一种：为erase函数设置一个返回值，返回当前结点的下一个结点的迭代器，即 iterator iter = erase （iter）。第二种：给erase传值时为 erase（iter++）；这是因为当把当前位置传递给函数之后，自动指向下一个位置。

list<int> l1{1, 2, 3, 4, 5};
    list<int>::iterator iter = l1.begin();
    while(iter != l1.end())
    {
        if(*iter % 2 == 0)
        {
            //iter = l1.erase(iter); //返回删除元素的下一个迭代器
            l1.erase(iter++);
        }
        else
        {
            iter++;
        }
    }

**4.对于vector和string，如果容器内存被重新分配，插入元素后，iterators,pointers,references失效；如果没有重新分配，那么插入点之前的iterator有效，插入点之后的iterator失效。对于deque，如果插入点位于除front和back的其它位置，iterators,pointers,references失效；当我们插入元素到front和back时，deque的迭代器失效，但reference和pointers有效。**

** **