STL之VectorMapList针对erase方法踩坑笔记

前沿

        如下总结的三种容器，开头都会涉及当前容器的特点，再者就本次针对erase方法的使用避坑总结。

一.Vector

        vector关联关联容器，存储内存是连续，且特点支持快速访问，但是插入和删除效率比较地(需要找查找和移动)。另外在删除元素是，需注意迭代器的失效情况。

erase避坑，示例代码：

int main(){

    //vector
    std::vector<std::string> v;
    v.push_back("one");
    v.push_back("two");
    v.push_back("three");
    v.push_back("three");
    v.push_back("three");
    v.push_back("three");
    v.push_back("four");
    v.push_back("five");

    std::cout<< "del before size - " << v.size() << std::endl;

    for(std::vector<std::string>::iterator it = v.begin(); it != v.end(); ++it)
    {
        std::cout << *it << std::endl;
    }
    std::cout << "------------------" << std::endl;
    for(std::vector<std::string>::iterator it = v.begin(); it != v.end(); ++it)
    {
        if(*it == "three")
        {
            v.erase(it);
        }
    }
    std::cout<< "del after size - " << v.size() << std::endl;
    for(std::vector<std::string>::iterator it = v.begin(); it != v.end(); ++it)
    {
        std::cout << *it << std::endl;
    }
    return 0;
}

输出结果：

[root@bogon fuxi_csdn]# ./a.out 
del before size - 8
one
two
three
three
three
three
four
five
------------------
del after size - 6
one
two
three
three
four
five
[root@bogon fuxi_csdn]#

上述删除前&删除后结果发现未能实现删除全部的three元素，这是何原因呢？请看下文，经查询发现vecotr容器的erase方法实现有关。当vector容器适用erase方法删除元素时，上述代码中通过v.erase(it),传入的是一个迭代器元素，通过查阅官方网站查看erase的定义，详情如下：

c++98:

 上述这段话含义是，从容器中移除单个元素或者从迭代范围内移除元素，并且通过移除元素的操作，有效的减少了容器的大小。因为vector容器底层适用数组作为底层存储结构，所以在移除末尾以外的其他元素，容器内的元素位置会进行元素移动且重新分配位置，这是一个很低效的操作方法。

通过上述文档我们可以知道，vector容器在删除某个元素时(末尾除外)，剩余的元素会进行移动，后面的元素会将前面剔除的元素的位置覆盖。如此以来上述输出代码的问题就得意显现出来。那么到底是怎么移动导致的上述问题的呢？看如下图解：

通过上图所示，当找到一个three之后，erase函数内部将当前位置元素剔除掉，在将剩余的元素向前移动。此时it的位置没有发生改变仍旧在原来的位置上，网上说返回了删除元素下一个元素迭代器，概念等价如此，但是实际上原因是因为后面的元素移动了，所以先前删除元素的it此时就指向了移动后的元素，也算是下一个元素的迭代器。在erase的源码:

#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
template<typename _Tp, typename _Alloc>
    typename vector<_Tp, _Alloc>::iterator
    vector<_Tp, _Alloc>::
    erase(iterator __position)
    {
      if (__position + 1 != end())
	_GLIBCXX_MOVE3(__position + 1, end(), __position);
      --this->_M_impl._M_finish;
      _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
      return __position;
    }

上述代码，将__position+ 1之后到结尾元素进行移动，在进行处理，最后return位置，仍旧是原来的it位置，指向的就是删除后下一个元素。通过以上图解+代码中的循环(tmp = it ++ => it++)，就能解释输出内容为什么会如此了！不仅如此，如上代码，元素为偶数,进行删除操作,不会报错,但是无法达成删除所有元素的处理。巧合迭代器不会越界。当为奇数个数，程序就会崩溃，出现段错误，当迭代去指向最后一个元素时,被删除时,在进行++操作，越界,导致程序崩溃,可以将上述代码删除three修改成删除five即可验证。

例如修改上述代码如下&输出结果:

  for(std::vector<std::string>::iterator it = v.begin(); it != v.end(); ++it)
    {
        if(*it == "five")
        {
            v.erase(it);
        }
    }

输出:
[root@bogon fuxi_csdn]# ./a.out 
del before size - 8
one
two
three
three
three
three
four
five
------------------
Segmentation fault (core dumped)

删除最有一个元素，因删除后当前的it失效，在进行++it就会越界，从而导致程序崩溃。

知晓了上述代码产生的原因，所以针对上述代码优化修改:

 for(std::vector<std::string>::iterator it = v.begin(); it != v.end(); )
 {
        if(*it == "three")
        {
            it = v.erase(it);
        }else{
            ++it;
        }
 }

另外也可以通过std::remove配合批量删除重复的元素：

 v.erase(std::remove(v.begin(), v.end(), "three"), v.end());// 剔除范围内所有three

上述方式中remove方法先将需要非目标元素全部移动到前面，剩余的局势要删除的元素，最后返回一个迭代器，再通过erase范围性质删除目标元素。源代码如下:std::remove:

 template<typename _ForwardIterator, typename _Tp>
    _ForwardIterator
    remove(_ForwardIterator __first, _ForwardIterator __last,
	   const _Tp& __value)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
				  _ForwardIterator>)
      __glibcxx_function_requires(_EqualOpConcept<
	    typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
      __glibcxx_requires_valid_range(__first, __last);

    // 找到目标元素的第一个位置
      __first = _GLIBCXX_STD_A::find(__first, __last, __value); 
      if(__first == __last)
        return __first;
      _ForwardIterator __result = __first;
      ++__first;
      for(; __first != __last; ++__first)
        if(!(*__first == __value))
          {
            *__result = _GLIBCXX_MOVE(*__first); // 将非目标元素前移动
            ++__result;
          }
      return __result;
    }

代码中先找找到范围内的目标元素的第一个位置，然后利用__result位置为非目标元素的移动存储位置，当元素查找完之后，返回最终的__result位置，那么erase(__result,v.end()),就清理的是所有要删除的目标元素。

二.Map

        Map是一种哈希表结构形式的容器，其底层采用红黑树作为存储结构具有高效的增删查，另外还具备自动排序(属于自定义类型可以指定排序方法，可查看本博的C++之map踩坑记录博文)。实际使用中非常便利，为应用层开发提供高效的开发便利。本次主要讨论的是map容器适用erase时所避的坑，避免实际使用时出过错导致一些列问题。

erase避坑，示例代码：

#include <iostream>
#include <map>
#include <vector>
 
 
int main()
{
    std::map<int, std::string> m;
    m.insert(std::make_pair(1, "one"));
    m.insert(std::make_pair(2, "two"));
    m.insert(std::make_pair(3, "three"));
    m.insert(std::make_pair(4, "four"));
    m.insert(std::make_pair(5, "five"));
 
    std::cout<< "before erase" << std::endl;
    for (std::map<int, std::string>::iterator it = m.begin(); it != m.end(); ++it)
    {
        std::cout << it->first << " " << it->second << std::endl;
    }
 
    for(std::map<int, std::string>::iterator it = m.begin(); it != m.end();)
    {
        if(it->first == 3)
        {
            //m.erase(it); //该处会崩溃
            m.erase(it++); // 正确用法
        }else
        {
            ++it;
        }
    }
 
    std::cout << "After erase" << std::endl;
    for (std::map<int, std::string>::iterator it = m.begin(); it != m.end(); ++it)
    {
        std::cout << it->first << " " << it->second << std::endl;
    }
    return 0;
}

崩溃输出:

before erase
1 one
2 two
3 three
4 four
5 five
ret it = 3
Segmentation fault (core dumped)

正常输出:

root@ubu-virtual-machine:~# ./a.out 
before erase
1 one
2 two
3 three
4 four
5 five
ret it = 4
After erase
1 one
2 two
4 four
5 five

 上述代码在c++98跟c++11对应的删除有偏差：

98版本的erase都是返回的整形,如果按照上代码实现，出现崩溃问题，后经过查询发现stl内部erase的实现，当调用时，会拷贝一份当前迭代器，之后如果没将it移动，那么当前的it就会失效，从而导致程序崩溃异常。正确的用法通过v.erase(it++)联合++it。在erase(it++)调用内部实现流程时，erase临时拷贝一份当前迭代器，因it++作为参数，其优先级比函数调用优先级高，所以erase流程为先拷贝，在走it++，此时迭代器已经就走到删除元素的下一个位置，如此一来，即可正常遍历运行。

上述途中c++11中优化了erase方法，剔除元素后返回删除元素的下一个元素的迭代器。使用时需要注意方式:

for(std::map<int, std::string>::iterator it = m.begin(); it != m.end();)
    {
        if(it->second == "three")
        {
            it = m.erase(it);// or m.erase(it++);
            std::cout<<"ret it = "<<it->first<<std::endl;
        }else{
            ++it;
        }
    }

 针对上述c++11看下优化后的erase源码：

  _GLIBCXX_ABI_TAG_CXX11
      iterator
      erase(iterator __position)
      { return _M_t.erase(__position); }

    _GLIBCXX_ABI_TAG_CXX11
      iterator
      erase(const_iterator __position)
      {
	const_iterator __result = __position; // 拷贝
	++__result;// 指向下个元素
	_M_erase_aux(__position); // 销毁要删除的元素
	return __result._M_const_cast();// 返回下个元素
      }

上述的erase方法实现，先拷贝，定义下个元素迭代器，销毁目标元素，返回删除的下个元素。

三.List

        List是一个双向链表容器，它有一些特定的优点和缺点，适用于不同的场景。其优点高效的插入和删除操作，双向链表，支持双向遍历，内存碎片化较小，不需要频繁的内存重新分配。但是也存在一些缺点,较高的内存开销,如额外的指针内存。不支持随机访问，关联容器，因其链结构，迭代器每次都要指针跳转，性能不如直接访问快。

erase避坑，示例代码：

int main()
{
    std::list<int> l;
    l.push_back(1);
    l.push_back(2);
    l.push_back(3);
    std::cout<< "before erase" << std::endl;
    for(std::list<int>::iterator it = l.begin(); it != l.end(); ++it)
    {
        std::cout << *it << std::endl;
    }

    for(std::list<int>::iterator it = l.begin(); it != l.end();++it)
    {
        if(*it == 2)
        {
            l.erase(it); // 会崩溃
        }
    }

    std::cout<< "after erase" << std::endl;
    for(std::list<int>::iterator it = l.begin(); it != l.end(); ++it)
    {
        std::cout << *it << std::endl;
    }
    return 0;
}

输出:

[root@bogon fuxi_csdn]# ./a.out 
before erase
1
2
3
Segmentation fault (core dumped)

如上出现段错误。何故？ 查看list内部实现的erase，跟前面vector跟map的erase相似，都是剔除当前元素后返回下一个元素的迭代器，源码如下:

 template<typename _Tp, typename _Alloc>
    typename list<_Tp, _Alloc>::iterator
    list<_Tp, _Alloc>::
    erase(iterator __position)
    {
      iterator __ret = iterator(__position._M_node->_M_next);
      _M_erase(__position);
      return __ret;
    }

 代码中先进行next操作，然后销毁当前要删除元素，return返回__ret表示下个元素位置。所以循环中使用erase需要注意方式同map方式一样即可，跟改为：

 for(std::list<int>::iterator it = l.begin(); it != l.end();)
 {
    if(*it == 2)
    {
        l.erase(it++);
    }else   {
        ++it;
    }
 }

总结，stl库提拱了方便的存储结构供给我们日常使用，在使用时需要注意潜在的风险问题，避免实际应用时出现不可预期的问题，以上就是vector & map & list 容器的erase方法在循环中使用需要注意的坑点,当然还有其他容器适用删除方法结合实际情况注意！！！