STL容器中元素的删除erase（）、remove（）

62 阅读 0 评论 41 点赞

我是靠谱客的博主秀丽钢笔，最近开发中收集的这篇文章主要介绍STL容器中元素的删除erase（）、remove（），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.引言

以下代码有什么问题，如何修改？

[cpp] 
view plain
copy

 #include<iostream>  
 #include<vector>  
 using namespace std;  
   
 void print(vector<int>);//传引用不妥！！  
   
 int main()  
 {  
     vector<int> array;   
     array.push_back(1);  
     array.push_back(6);  
     array.push_back(6);  
     array.push_back(3);  
 //删除array中的所有的6  
     vector<int>::iterator itor;  
     vector<int>::iterator itor2;  
     itor=array.begin();  
     for (itor=array.begin();itor!=array.end();itor++;)  
     {  
         if (6==*itor)  
         {  
             itor2=itor;  
             array.erase(itor2);  
         }  
     }  
     print(array);  
     return 0;  
 }  
   
 void print(vector<int> v)  
 {  
     cout<<"nvector size is: "<<v.size()<<endl;  
 }  

2.vector中erase源码

这段代码运行后容量只减小1，具体问题出在哪不知道。先看一下erase的源码。

[cpp] 
view plain
copy

 iterator erase(iterator position)   
 {  
     if (position + 1 != end()) //若position不是指向最后一个元素  
            copy(position + 1, finish, position); //运用的是copy，将删除位置的元素向后移动  
     --finish;//vector中finish所指位置为end()返回值   
     destroy(finish);  
     return position;  
 }  
 iterator erase(iterator first, iterator last) //允许last在first之前，后果自负  
 {  
     iterator i = copy(last, finish, first);  
 destroy(i, finish);  
 finish = finish - (last - first);  
     return first;  
 }  

现在知道了，如果这时删除一个元素之后，itor已经指向下一个元素，所以再调用itor++，那么连续的2个6就只能删除前一个。

所以以上的for循环可以改为：

[cpp] 
view plain
copy

 for (itor=array.begin();itor!=array.end();itor++;)  
 {  
     if (6==*itor)  
     {  
         itor2=itor;  
         array.erase(itor2);  
         itor--;  
     }  
 }  

3.remove源码

但是这样的代码可读性欠佳，还有一种改法就是更加规范的简洁的操作：调用算法remove，之后再进行erase。

此时将for循环替代为:array.erase(remove(array.begin().array.end(),6),array.end());当然这个时候要包含头文件<algorithm>。

为什么要删除，remove返回后的迭代器到vector末尾的元素呢？看remove算法源码。

remove操作移除[first,last)之中所有与value相等的元素。这一算法并不真正从容器中删除那些元素（换句话说容器的大小并没有改变），而是将每一个不与value相等的元素轮番赋值给first之后的空间。返回值ForwardIterator标示出重新整理后的最后元素的下一个位置。例如序列{0,1,0,2,0,3,0,4}，如果执行remove删除0，则结果是{1,2,3,4,0,3,0,4}，返回值ForwardIterator指向第5个元素。所以如果要删除那些残余元素可以使用erase的两迭代器版本。源码如下：

[cpp] 
view plain
copy

 tamplate<class ForwardIterator, class T>  
 ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value)  
 {  
     first=find(first, last, value);//找到第一个相等的元素  
     ForwardIterator next = first;//以next标示出来  
     //以下利用“remove_copy（）允许新旧容器重叠”的性质，进行移除操作  
     //并将结果置于原容器中  
     return first == last ? first : remove_copy(++next,last,first,value);  
 }  

remove_copy并不改变原来的容器，只是将所要删除的值删除后，将新容器存储在result迭代器所指的位置处。

[cpp] 
view plain
copy

 tamplate<class InputIterator, class OutputIterator, class T>  
 OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value)  
 {  
     for(;first != last;++first)  
         if(*first != value)    //如果不相等  
         {  
             *result = *first;  //赋值给新容器  
             ++result;                 
         }  
     return result;  
 }  

当然remove函数也有仿函数版本的remove_if，remove_copy_if。

4.list中的remove和erase操作

list中的erase：

[cpp] 
view plain
copy

 iterator erase（iterator position）  
 {  
     link_type next_node = link_typr(position.node->next);  
     link_type prev_node = link_typr(position.node->prev);  
     prev_node->next = next_node;  
     next_node->prev = prev_node;  
     destroy_node(position.node);  
     return iterator(next_node);  
 }  

remove是算法库中的一个算法，但是list的结构使用这种remove算法时效率低下。根据list的结构，标准库专门为list设计了remove操作（其他容器是没有的）。

[cpp] 
view plain
copy

 template<class T, calss Alloc>  
 void list<T,Alloc>::remove(const T& value)  
 {  
     iterator first = begin();  
     iterator last = end();  
     while(first != last)  
     {  
         iterator next = first;  
         ++next;  
         if(*first == value)