酒店 手机网站模板,区块链,广州旅游景点,网站外链哪里做前沿 如下总结的三种容器#xff0c;开头都会涉及当前容器的特点#xff0c;再者就本次针对erase方法的使用避坑总结。
一.Vector vector关联关联容器#xff0c;存储内存是连续#xff0c;且特点支持快速访问#xff0c;但是插入和删除效率比较地(需要找查找和移动)。另…前沿 如下总结的三种容器开头都会涉及当前容器的特点再者就本次针对erase方法的使用避坑总结。
一.Vector vector关联关联容器存储内存是连续且特点支持快速访问但是插入和删除效率比较地(需要找查找和移动)。另外在删除元素是需注意迭代器的失效情况。
erase避坑示例代码
int main(){//vectorstd::vectorstd::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::vectorstd::string::iterator it v.begin(); it ! v.end(); it){std::cout *it std::endl;}std::cout ------------------ std::endl;for(std::vectorstd::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::vectorstd::string::iterator it v.begin(); it ! v.end(); it){std::cout *it std::endl;}return 0;
}
输出结果
[rootbogon 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
[rootbogon fuxi_csdn]#
上述删除前删除后结果发现未能实现删除全部的three元素这是何原因呢请看下文经查询发现vecotr容器的erase方法实现有关。当vector容器适用erase方法删除元素时上述代码中通过v.erase(it),传入的是一个迭代器元素通过查阅官方网站查看erase的定义详情如下
c98: 上述这段话含义是从容器中移除单个元素或者从迭代范围内移除元素并且通过移除元素的操作有效的减少了容器的大小。因为vector容器底层适用数组作为底层存储结构所以在移除末尾以外的其他元素容器内的元素位置会进行元素移动且重新分配位置这是一个很低效的操作方法。
通过上述文档我们可以知道vector容器在删除某个元素时(末尾除外)剩余的元素会进行移动后面的元素会将前面剔除的元素的位置覆盖。如此以来上述输出代码的问题就得意显现出来。那么到底是怎么移动导致的上述问题的呢看如下图解 通过上图所示当找到一个three之后erase函数内部将当前位置元素剔除掉在将剩余的元素向前移动。此时it的位置没有发生改变仍旧在原来的位置上网上说返回了删除元素下一个元素迭代器概念等价如此但是实际上原因是因为后面的元素移动了所以先前删除元素的it此时就指向了移动后的元素也算是下一个元素的迭代器。在erase的源码:
#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
templatetypename _Tp, typename _Alloctypename 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::vectorstd::string::iterator it v.begin(); it ! v.end(); it){if(*it five){v.erase(it);}}输出:
[rootbogon fuxi_csdn]# ./a.out
del before size - 8
one
two
three
three
three
three
four
five
------------------
Segmentation fault (core dumped)
删除最有一个元素因删除后当前的it失效在进行it就会越界从而导致程序崩溃。
知晓了上述代码产生的原因所以针对上述代码优化修改: for(std::vectorstd::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: templatetypename _ForwardIterator, typename _Tp_ForwardIteratorremove(_ForwardIterator __first, _ForwardIterator __last,const _Tp __value){// concept requirements__glibcxx_function_requires(_Mutable_ForwardIteratorConcept_ForwardIterator)__glibcxx_function_requires(_EqualOpConcepttypename 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 vectorint main()
{std::mapint, 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::mapint, std::string::iterator it m.begin(); it ! m.end(); it){std::cout it-first it-second std::endl;}for(std::mapint, 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::mapint, 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)
正常输出:
rootubu-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 上述代码在c98跟c11对应的删除有偏差 98版本的erase都是返回的整形,如果按照上代码实现出现崩溃问题后经过查询发现stl内部erase的实现当调用时会拷贝一份当前迭代器之后如果没将it移动那么当前的it就会失效从而导致程序崩溃异常。正确的用法通过v.erase(it)联合it。在erase(it)调用内部实现流程时erase临时拷贝一份当前迭代器因it作为参数其优先级比函数调用优先级高所以erase流程为先拷贝在走it此时迭代器已经就走到删除元素的下一个位置如此一来即可正常遍历运行。
上述途中c11中优化了erase方法剔除元素后返回删除元素的下一个元素的迭代器。使用时需要注意方式:
for(std::mapint, std::string::iterator it m.begin(); it ! m.end();){if(it-second three){it m.erase(it);// or m.erase(it);std::coutret it it-firststd::endl;}else{it;}} 针对上述c11看下优化后的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::listint l;l.push_back(1);l.push_back(2);l.push_back(3);std::cout before erase std::endl;for(std::listint::iterator it l.begin(); it ! l.end(); it){std::cout *it std::endl;}for(std::listint::iterator it l.begin(); it ! l.end();it){if(*it 2){l.erase(it); // 会崩溃}}std::cout after erase std::endl;for(std::listint::iterator it l.begin(); it ! l.end(); it){std::cout *it std::endl;}return 0;
}
输出:
[rootbogon fuxi_csdn]# ./a.out
before erase
1
2
3
Segmentation fault (core dumped)
如上出现段错误。何故 查看list内部实现的erase跟前面vector跟map的erase相似都是剔除当前元素后返回下一个元素的迭代器源码如下: templatetypename _Tp, typename _Alloctypename 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::listint::iterator it l.begin(); it ! l.end();){if(*it 2){l.erase(it);}else {it;}}
总结stl库提拱了方便的存储结构供给我们日常使用在使用时需要注意潜在的风险问题避免实际应用时出现不可预期的问题以上就是vector map list 容器的erase方法在循环中使用需要注意的坑点,当然还有其他容器适用删除方法结合实际情况注意
