STL之Vector&Map&List针对erase方法踩坑笔记

络腮胡菲菲  论坛元老 | 2025-1-14 22:36:31 | 显示全部楼层 | 阅读模式
打印 上一主题 下一主题
楼主

主题 1792|帖子 1792|积分 5376

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要 登录 才可以下载或查看，没有账号？立即注册

x
前沿

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

        vector关联关联容器，存储内存是连续，且特点支持快速访问，但是插入和删除效率比较地(需要找查找和移动)。别的在删除元素是，需注意迭代器的失效情况。
erase避坑，示例代码：
  1. int main(){
  3.     //vector
  4.     std::vector<std::string> v;
  5.     v.push_back("one");
  6.     v.push_back("two");
  7.     v.push_back("three");
  8.     v.push_back("three");
  9.     v.push_back("three");
  10.     v.push_back("three");
  11.     v.push_back("four");
  12.     v.push_back("five");
  14.     std::cout<< "del before size - " << v.size() << std::endl;
  16.     for(std::vector<std::string>::iterator it = v.begin(); it != v.end(); ++it)
  17.     {
  18.         std::cout << *it << std::endl;
  19.     }
  20.     std::cout << "------------------" << std::endl;
  21.     for(std::vector<std::string>::iterator it = v.begin(); it != v.end(); ++it)
  22.     {
  23.         if(*it == "three")
  24.         {
  25.             v.erase(it);
  26.         }
  27.     }
  28.     std::cout<< "del after size - " << v.size() << std::endl;
  29.     for(std::vector<std::string>::iterator it = v.begin(); it != v.end(); ++it)
  30.     {
  31.         std::cout << *it << std::endl;
  32.     }
  33.     return 0;
  34. }
复制代码
输出效果：
  1. [root@bogon fuxi_csdn]# ./a.out
  2. del before size - 8
  3. one
  4. two
  5. three
  6. three
  7. three
  8. three
  9. four
  10. five
  11. ------------------
  12. del after size - 6
  13. one
  14. two
  15. three
  16. three
  17. four
  18. five
  19. [root@bogon fuxi_csdn]#
复制代码
上述删除前&删除后效果发现未能实现删除全部的three元素，这是何缘故原由呢？请看下文，经查询发现vecotr容器的erase方法实现有关。当vector容器适用erase方法删除元素时，上述代码中通过v.erase(it),传入的是一个迭代器元素，通过查阅官方网站查看erase的定义，详情如下：
c++98:

 上述这段话寄义是，从容器中移除单个元素大概从迭代范围内移除元素，并且通过移除元素的操作，有用的减少了容器的巨细。由于vector容器底层适用数组作为底层存储结构，所以在移除末尾以外的其他元素，容器内的元素位置会进行元素移动且重新分配位置，这是一个很低效的操作方法。
通过上述文档我们可以知道，vector容器在删除某个元素时(末尾除外)，剩余的元素会进行移动，后面的元素会将前面剔除的元素的位置覆盖。如此以来上述输出代码的题目就自得显现出来。那么到底是怎么移动导致的上述题目的呢？看如下图解：

通过上图所示，当找到一个three之后，erase函数内部将当前位置元素剔除掉，在将剩余的元素向前移动。此时it的位置没有发生改变仍旧在原来的位置上，网上说返回了删除元素下一个元素迭代器，概念等价如此，但是现实上缘故原由是由于后面的元素移动了，所以先前删除元素的it此时就指向了移动后的元素，也算是下一个元素的迭代器。在erase的源码:
  1. #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
  2. template<typename _Tp, typename _Alloc>
  3.     typename vector<_Tp, _Alloc>::iterator
  4.     vector<_Tp, _Alloc>::
  5.     erase(iterator __position)
  6.     {
  7.       if (__position + 1 != end())
  8.         _GLIBCXX_MOVE3(__position + 1, end(), __position);
  9.       --this->_M_impl._M_finish;
  10.       _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
  11.       return __position;
  12.     }
复制代码
上述代码，将__position+ 1之后到结尾元素进行移动，在进行处置惩罚，末了return位置，仍旧是原来的it位置，指向的就是删除后下一个元素。通过以上图解+代码中的循环(tmp = it ++ => it++)，就能表明输出内容为什么会如此了！不但如此，如上代码，元素为偶数,进行删除操作,不会报错,但是无法告竣删除全部元素的处置惩罚。偶合迭代器不会越界。当为奇数个数，程序就会崩溃，出现段错误，当迭代去指向末了一个元素时,被删除时,在进行++操作，越界,导致程序崩溃,可以将上述代码删除three修改成删除five即可验证。
比方修改上述代码如下&输出效果:
  1.   for(std::vector<std::string>::iterator it = v.begin(); it != v.end(); ++it)
  2.     {
  3.         if(*it == "five")
  4.         {
  5.             v.erase(it);
  6.         }
  7.     }
  9. 输出:
  10. [root@bogon fuxi_csdn]# ./a.out
  11. del before size - 8
  12. one
  13. two
  14. three
  15. three
  16. three
  17. three
  18. four
  19. five
  20. ------------------
  21. Segmentation fault (core dumped)
复制代码
删除最有一个元素，因删除后当前的it失效，在进行++it就会越界，从而导致程序崩溃。
知晓了上述代码产生的缘故原由，所以针对上述代码优化修改:
  1. for(std::vector<std::string>::iterator it = v.begin(); it != v.end(); )
  2. {
  3.         if(*it == "three")
  4.         {
  5.             it = v.erase(it);
  6.         }else{
  7.             ++it;
  8.         }
  9. }
复制代码
别的也可以通过std::remove配合批量删除重复的元素：
  1. v.erase(std::remove(v.begin(), v.end(), "three"), v.end());// 剔除范围内所有three
复制代码
上述方式中remove方法先将需要非目的元素全部移动到前面，剩余的局势要删除的元素，末了返回一个迭代器，再通过erase范围性质删除目的元素。源代码如下:std::remove:
  1. template<typename _ForwardIterator, typename _Tp>
  2.     _ForwardIterator
  3.     remove(_ForwardIterator __first, _ForwardIterator __last,
  4.            const _Tp& __value)
  5.     {
  6.       // concept requirements
  7.       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
  8.                                   _ForwardIterator>)
  9.       __glibcxx_function_requires(_EqualOpConcept<
  10.             typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
  11.       __glibcxx_requires_valid_range(__first, __last);
  13.     // 找到目标元素的第一个位置
  14.       __first = _GLIBCXX_STD_A::find(__first, __last, __value);
  15.       if(__first == __last)
  16.         return __first;
  17.       _ForwardIterator __result = __first;
  18.       ++__first;
  19.       for(; __first != __last; ++__first)
  20.         if(!(*__first == __value))
  21.           {
  22.             *__result = _GLIBCXX_MOVE(*__first); // 将非目标元素前移动
  23.             ++__result;
  24.           }
  25.       return __result;
  26.     }
复制代码
代码中先找找到范围内的目的元素的第一个位置，然后利用__result位置为非目的元素的移动存储位置，当元素查找完之后，返回终极的__result位置，那么erase(__result,v.end()),就清算的是全部要删除的目的元素。
二.Map

        Map是一种哈希表结构情势的容器，其底层采取红黑树作为存储结构具有高效的增删查，别的还具备主动排序(属于自定义类型可以指定排序方法，可查看本博的C++之map踩坑记载博文)。现实使用中非常便利，为应用层开辟提供高效的开辟便利。本次重要讨论的是map容器适用erase时所避的坑，避免现实使用时出过错导致一些列题目。
erase避坑，示例代码：
  1. #include <iostream>
  2. #include <map>
  3. #include <vector>
  6. int main()
  7. {
  8.     std::map<int, std::string> m;
  9.     m.insert(std::make_pair(1, "one"));
  10.     m.insert(std::make_pair(2, "two"));
  11.     m.insert(std::make_pair(3, "three"));
  12.     m.insert(std::make_pair(4, "four"));
  13.     m.insert(std::make_pair(5, "five"));
  15.     std::cout<< "before erase" << std::endl;
  16.     for (std::map<int, std::string>::iterator it = m.begin(); it != m.end(); ++it)
  17.     {
  18.         std::cout << it->first << " " << it->second << std::endl;
  19.     }
  21.     for(std::map<int, std::string>::iterator it = m.begin(); it != m.end();)
  22.     {
  23.         if(it->first == 3)
  24.         {
  25.             //m.erase(it); //该处会崩溃
  26.             m.erase(it++); // 正确用法
  27.         }else
  28.         {
  29.             ++it;
  30.         }
  31.     }
  33.     std::cout << "After erase" << std::endl;
  34.     for (std::map<int, std::string>::iterator it = m.begin(); it != m.end(); ++it)
  35.     {
  36.         std::cout << it->first << " " << it->second << std::endl;
  37.     }
  38.     return 0;
  39. }
复制代码
崩溃输出:
  1. before erase
  2. 1 one
  3. 2 two
  4. 3 three
  5. 4 four
  6. 5 five
  7. ret it = 3
  8. Segmentation fault (core dumped)
复制代码
正常输出:
  1. root@ubu-virtual-machine:~# ./a.out
  2. before erase
  3. 1 one
  4. 2 two
  5. 3 three
  6. 4 four
  7. 5 five
  8. ret it = 4
  9. After erase
  10. 1 one
  11. 2 two
  12. 4 four
  13. 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方法，剔除元素后返回删除元素的下一个元素的迭代器。使用时需要注意方式:
  1. for(std::map<int, std::string>::iterator it = m.begin(); it != m.end();)
  2.     {
  3.         if(it->second == "three")
  4.         {
  5.             it = m.erase(it);// or m.erase(it++);
  6.             std::cout<<"ret it = "<<it->first<<std::endl;
  7.         }else{
  8.             ++it;
  9.         }
  10.     }
复制代码
 针对上述c++11看下优化后的erase源码：
  1.   _GLIBCXX_ABI_TAG_CXX11
  2.       iterator
  3.       erase(iterator __position)
  4.       { return _M_t.erase(__position); }
  6.     _GLIBCXX_ABI_TAG_CXX11
  7.       iterator
  8.       erase(const_iterator __position)
  9.       {
  10.         const_iterator __result = __position; // 拷贝
  11.         ++__result;// 指向下个元素
  12.         _M_erase_aux(__position); // 销毁要删除的元素
  13.         return __result._M_const_cast();// 返回下个元素
  14.       }
复制代码
上述的erase方法实现，先拷贝，定义下个元素迭代器，销毁目的元素，返回删除的下个元素。
三.List

        List是一个双向链表容器，它有一些特定的优点和缺点，适用于不同的场景。其优点高效的插入和删除操作，双向链表，支持双向遍历，内存碎片化较小，不需要频繁的内存重新分配。但是也存在一些缺点,较高的内存开销,如额外的指针内存。不支持随机访问，关联容器，因其链结构，迭代器每次都要指针跳转，性能不如直接访问快。
erase避坑，示例代码：
  1. int main()
  2. {
  3.     std::list<int> l;
  4.     l.push_back(1);
  5.     l.push_back(2);
  6.     l.push_back(3);
  7.     std::cout<< "before erase" << std::endl;
  8.     for(std::list<int>::iterator it = l.begin(); it != l.end(); ++it)
  9.     {
  10.         std::cout << *it << std::endl;
  11.     }
  13.     for(std::list<int>::iterator it = l.begin(); it != l.end();++it)
  14.     {
  15.         if(*it == 2)
  16.         {
  17.             l.erase(it); // 会崩溃
  18.         }
  19.     }
  21.     std::cout<< "after erase" << std::endl;
  22.     for(std::list<int>::iterator it = l.begin(); it != l.end(); ++it)
  23.     {
  24.         std::cout << *it << std::endl;
  25.     }
  26.     return 0;
  27. }
复制代码
输出:
  1. [root@bogon fuxi_csdn]# ./a.out
  2. before erase
  3. 1
  4. 2
  5. 3
  6. Segmentation fault (core dumped)
复制代码
如上出现段错误。何以？ 查看list内部实现的erase，跟前面vector跟map的erase相似，都是剔除当前元素后返回下一个元素的迭代器，源码如下:
  1. template<typename _Tp, typename _Alloc>
  2.     typename list<_Tp, _Alloc>::iterator
  3.     list<_Tp, _Alloc>::
  4.     erase(iterator __position)
  5.     {
  6.       iterator __ret = iterator(__position._M_node->_M_next);
  7.       _M_erase(__position);
  8.       return __ret;
  9.     }
复制代码
 代码中先进行next操作，然后销毁当前要删除元素，return返回__ret表现下个元素位置。所以循环中使用erase需要注意方式同map方式一样即可，跟改为：
  1. for(std::list<int>::iterator it = l.begin(); it != l.end();)
  2. {
  3.     if(*it == 2)
  4.     {
  5.         l.erase(it++);
  6.     }else   {
  7.         ++it;
  8.     }
  9. }
复制代码
总结，stl库提拱了方便的存储结构供给我们一样平常使用，在使用时需要注意潜伏的风险题目，避免现实应用时出现不可预期的题目，以上就是vector & map & list 容器的erase方法在循环中使用需要注意的坑点,固然还有其他容器适用删除方法结合现实情况注意！！！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
回复

举报

0 个回复

倒序浏览
返回列表

快速回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

络腮胡菲菲

论坛元老
这个人很懒什么都没写!

楼主热帖

标签云

集成商 AI 运维 CIO 存储 服务器
微信订阅号
微信服务号
微信客服
小程序
H5
关于我们 商务合作 网站地图
©Copyright 2022-2024 杭州祥升科技有限公司 版权所有 浙ICP备20004199号
快速回复 返回顶部 返回列表