C++容器：在遍历过程中删除元素

2024-07-13 09:25| 来源: 网络整理| 查看: 265

C++11之后，标准库引入了大量由基本数据结构封装而成的容器类型。容器的引入，一定程度上降低Cpp的上手难度。

在实际的开发过程中，经常需要根据业务需求，在遍历过程中从容器里删除指定的元素。而一些不规范的使用方式，将埋下稳定性风险。

一、推荐模板

对于在遍历过程中删除指定元素，推荐使用以下模板：

for(auto it = _container.begin(); it != _container.end(); ) { if(__pred(*it)) { //do something with (*it); it = _container.erase(it); } else { ++it; } }

二、常见遍历模式的缺陷

1. 下面这种遍历方式应该是大家最容易想到的：

for(auto it = _container.begin(); it != _container.end(); ++it) { if(__pred(*it)) { _container.erase(it); } }

这种遍历方式的问题比较明显，主要是两种：

间隔遍历，部分元素被跳过； heap-buffer-used-after-free，也就是使用被释放的动态内存；

第一类问题主要出现在以vector为代表的容器中

int main() { std::vector nums{1,2,3,4,5,6,7,8}; for(auto iter = nums.begin(); iter != nums.end(); ++iter) { if(*iter == 4) { nums.erase(iter); } else { std::cout_M_impl._M_finish); _GLIBCXX_ASAN_ANNOTATE_SHRINK(1); return __position; }

　　_GLIBCXX_MOVE3 将当前iter之后的元素向前挪动了一个元素。

第二类问题主要出现在以list、map为代表的容器中

int main() { std::unordered_map nums{{1,2}, {2,3}, {3,4}}; for(auto iter = nums.begin(); iter != nums.end(); ++iter) { if(iter->first == 2) { nums.erase(iter); } } return 0; }

g++ _Container.cpp -o _Container && _Container

程序崩溃后报 heap-use-after-free错误，并输出崩溃时的调用栈。我们试着从stl的源码寻找错误的原因。

template auto _Hashtable:: erase(const_iterator __it) -> iterator { __node_type* __n = __it._M_cur; std::size_t __bkt = _M_bucket_index(__n); // Look for previous node to unlink it from the erased one, this // is why we need buckets to contain the before begin to make // this search fast. __node_base* __prev_n = _M_get_previous_node(__bkt, __n); return _M_erase(__bkt, __prev_n, __n); } template auto _Hashtable:: _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n) -> iterator { if (__prev_n == _M_buckets[__bkt]) _M_remove_bucket_begin(__bkt, __n->_M_next(), __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0); else if (__n->_M_nxt) { size_type __next_bkt = _M_bucket_index(__n->_M_next()); if (__next_bkt != __bkt) _M_buckets[__next_bkt] = __prev_n; } __prev_n->_M_nxt = __n->_M_nxt; iterator __result(__n->_M_next()); this->_M_deallocate_node(__n); --_M_element_count; return __result; }

　　实现上，根据迭代器找到指定的元素后，不仅将元素从容器中删除，同时释放了存储该元素的动态内存。此时++iter引用了已被释放的内存，引发heap-use-after-free错误。

【本文地址】

公司简介

联系我们