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

前沿

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

一.Vector

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

erase避坑，示例代码：

int main(){//vectorstd::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>::iteratorvector<_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>_ForwardIteratorremove(_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_CXX11iteratorerase(iterator __position){ return _M_t.erase(__position); }_GLIBCXX_ABI_TAG_CXX11iteratorerase(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>::iteratorlist<_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方法在循环中使用需要注意的坑点,当然还有其他容器适用删除方法结合实际情况注意！！！