canco

浏览: 254596 次
性别:
来自: 北京

最近访客更多访客>>

lsyoulin

taojiashun

keepgoingxjw

China_qd_zjk

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

STL序列式容器中删除元素的方法和陷阱二

博客分类：

技术

算法

2.使用STL中通用算法或容器成员函数删除元素的方法

以上手工编写for循环代码删除容器中元素的方法也有一些问题，如果判断条件特别复杂，又有循环判断的话，循环中间又有异常处理的话，++itVect的位置就要小心放置了，稍不留意就要出错。所以手工编写代码删除容器中元素的方法不太安全，代码重复，也不够优雅，要注意的地方很多。

对于这种情况，可以考虑使用STL中通用算法remvoe()和remove_if()帮忙。而remvoe()和remove_if()这两个算法也有一个问题需要程序员特别小心。在通用算法中的 remove（包括remove_if）函数，并不真正从容器中删除元素，而是“应被删除的元素”被其后的“未被删除的元素”覆盖。返回值ForwardIterator指向经移除后的最后元素的下一位置。如vector{0,1,2,3,3,4}，执行remove()，希望移除所有值为3的元素，结果为{0,1,2,4,3,4}，返回值ForwardIterator指向第5个元素。即：<o:p></o:p>

0 1 2 3 3 4 移除前<o:p></o:p>

0 1 2 4 3 4 移除后<o:p></o:p>

<o:p></o:p>

移除值为3的元素。移除后3被其后的4替代，最后两位元素为残余数据。<o:p></o:p>

<o:p></o:p>

例 5：<o:p></o:p>

void main() {<o:p></o:p>

vector<int> vectInt;<o:p></o:p>

int i;<o:p></o:p>

for (i = 0; i < 5; i++ ) {<o:p></o:p>

vectInt.push_back( i );<o:p></o:p>

if ( 3 == i ) {<o:p></o:p>

vectInt.push_back( i );<o:p></o:p>

}<o:p></o:p>

remove( vectInt.begin(), vectInt.end(), 3 );<o:p></o:p>

cout << " after deleted , size = " << vectInt.size() << endl;<o:p></o:p>

for ( i = 0; i < vectInt.size();; i++ ) {<o:p></o:p>

cout << "i = " << i << " , " << vectInt[i] << endl;<o:p></o:p>

}<o:p></o:p>

运行结果为：<o:p></o:p>

after deleted , size = 6 // 从这行可以看出，移除后容器的大小没变<o:p></o:p>

i = 0 , 0<o:p></o:p>

i = 1 , 1<o:p></o:p>

i = 2 , 2<o:p></o:p>

i = 3 , 4 // 从这行可以看出：“应被删除的元素”3 被其后的“未被删除的元素”4覆盖<o:p></o:p>

i = 4 , 3<o:p></o:p>

i = 5 , 4 <o:p></o:p>

<o:p></o:p>

所以要彻底删除还应该把后面的残余数据删除掉，这可以通过调用容器的成员函数erase()做到。<o:p></o:p>

例 6：<o:p></o:p>

void main() {<o:p></o:p>

vector<int> vectInt;<o:p></o:p>

int i;<o:p></o:p>

for (i = 0; i < 5; i++ ) {<o:p></o:p>

vectInt.push_back( i );<o:p></o:p>

if ( 3 == i ) {<o:p></o:p>

vectInt.push_back( i );<o:p></o:p>

}<o:p></o:p>

vectInt.erase( remove( vectInt.begin(), vectInt.end(), 3 ), vectInt.end() );<o:p></o:p>

cout << " after deleted , size = " << vectInt.size() << endl;<o:p></o:p>

for ( i = 0; i < vectInt.size();; i++ ) {<o:p></o:p>

cout << "i = " << i << " , " << vectInt[i] << endl;<o:p></o:p>

}<o:p></o:p>

运行结果为：<o:p></o:p>

after deleted , size = 4 // 从这行可以看出，删除后容器的大小变化了<o:p></o:p>

i = 0 , 0<o:p></o:p>

i = 1 , 1<o:p></o:p>

i = 2 , 2<o:p></o:p>

i = 3 , 4<o:p></o:p>

从结果可以看出，所有值为3的元素确实被删除了。<o:p></o:p>

对于vector容器存放其他比较复杂的对象，就可以用remove_if()加函数对象（Function Object）的方法。<o:p></o:p>

如：<o:p></o:p>

例7：<o:p></o:p>

#include <iostream><o:p></o:p>

#include <sstream><o:p></o:p>

#include <string><o:p></o:p>

#include <vector><o:p></o:p>

#include <algorithm><o:p></o:p>

#include <list><o:p></o:p>

using namespace std;<o:p></o:p>

class CTest {<o:p></o:p>

public:<o:p></o:p>

CTest( const string& str, int iPrice ) : m_strName( str ), m_iPrice( iPrice ) { }<o:p></o:p>

void vPrint() { cout << "name=" << m_strName << " price = " << m_iPrice << endl;<o:p></o:p>

}<o:p></o:p>

private:<o:p></o:p>

string m_strName;<o:p></o:p>

int m_iPrice;<o:p></o:p>

// 由于两个函数对象要访问CTest类的private成员，所以设为友员。<o:p></o:p>

friend class CStrFunc;<o:p></o:p>

friend class CIntFunc;<o:p></o:p>

};<o:p></o:p>

// 函数对象，根据string比较<o:p></o:p>

class CStrFunc {<o:p></o:p>

string m_str;<o:p></o:p>

public:<o:p></o:p>

CStrFunc( const string& str ) : m_str( str ) {<o:p></o:p>

}<o:p></o:p>

bool operator() ( const CTest& left ) {<o:p></o:p>

return ( m_str == left.m_strName ) ? true : false;<o:p></o:p>

}<o:p></o:p>

};<o:p></o:p>

// 函数对象，根据int比较<o:p></o:p>

class CIntFunc {<o:p></o:p>

int m_iPrice;<o:p></o:p>

public:<o:p></o:p>

CIntFunc( int iPrice ) : m_iPrice( iPrice ) {<o:p></o:p>

}<o:p></o:p>

bool operator() ( const CTest& left ) {<o:p></o:p>

return ( m_iPrice == left.m_iPrice ) ? true : false;<o:p></o:p>

}<o:p></o:p>

};<o:p></o:p>

void main( ) {<o:p></o:p>

<o:p></o:p>

vector< CTest > vectTest;<o:p></o:p>

int i;<o:p></o:p>

for ( i = 0; i < 5 ; i++ ) {<o:p></o:p>

stringstream stream; // 流格式化符，把int转化为string<o:p></o:p>

stream << i;<o:p></o:p>

string str = stream.str();<o:p></o:p>

CTest clTest( str, i );<o:p></o:p>

vectTest.push_back( clTest );<o:p></o:p>

}<o:p></o:p>

for ( i = 0 ; i < vectTest.size(); i++ ) {<o:p></o:p>

vectTest[ i ].vPrint();<o:p></o:p>

}<o:p></o:p>

// 删除所有m_strName = "3"的元素<o:p></o:p>

vectTest.erase( remove_if( vectTest.begin(), vectTest.end(), CStrFunc( "3" ) ),<o:p></o:p>

vectTest.end() );<o:p></o:p>

cout << "delete 3 after : " << endl;<o:p></o:p>

for ( i = 0 ; i < vectTest.size(); i++ ) {<o:p></o:p>

vectTest[ i ].vPrint();<o:p></o:p>

}<o:p></o:p>

// 删除所有m_iPrice = 2的元素<o:p></o:p>

vectTest.erase( remove_if( vectTest.begin(), vectTest.end(), CIntFunc( 2 ) ),<o:p></o:p>

vectTest.end() );<o:p></o:p>

cout << "delete 2 after : " << endl;<o:p></o:p>

for ( i = 0 ; i < vectTest.size(); i++ ) {<o:p></o:p>

vectTest[ i ].vPrint();<o:p></o:p>

}<o:p></o:p>

手工编写for循环代码删除STL序列式容器中元素的方法，使用STL中通用算法或容器成员函数删除元素的方法，两者之间的比较：<o:p></o:p>

1．前者代码重复。<o:p></o:p>

2．前者容易出错，不够清晰。<o:p></o:p>

3．效率：<o:p></o:p>

0 1 2 3 2 5 6 7<o:p></o:p>

0 1 3 2 5 6 7<o:p></o:p>

0 1 3 5 6 7<o:p></o:p>

用第一种方法删除所有值为2的元素<o:p></o:p>

从上图可以看出，每删除一个元素，后面的所有元素都到往前移动一位，导致一次内存大搬迁。<o:p></o:p>

<o:p></o:p>

0 1 2 3 2 5 6 7<o:p></o:p>

0 1 3 2 5 6 6 7<o:p></o:p>

0 1 3 5 6 7<o:p></o:p>

<o:p></o:p>

用第二种方法删除所有值为2的元素<o:p></o:p>

从上面可以看出，删除时元素2被后面元素覆盖，不会到元素移位和内存大搬迁，残余数据留到末尾一次全部删除，也不会导致内存大搬迁，所以后者的方法要比前者在效率上好很多。

分享到：

STL关联式容器中删除元素的方法和陷阱四 | C++异常中的堆栈跟踪

2003-03-19 09:14
浏览 2074
评论(0)
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

STL序列式容器中删除元素的方法和陷阱二

2.使用STL中通用算法或容器成员函数删除元素的方法

评论

发表评论

相关推荐

最近访客 更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

STL序列式容器中删除元素的方法和陷阱 二

2.使用STL中通用算法或容器成员函数删除元素的方法

评论

发表评论

相关推荐

强烈推荐《大话无线通讯》

手机开发平台指南、教程和资料介绍（修改稿2）

iPhone手机开发平台入门介绍和教程（修改稿）

《Designing Interfaces中文版》学习笔记

iPhone手机开发平台入门介绍和教程

Windows平台上iPhone基于cygwin开发环境的搭建方法

Symbian平台培训教程

手机开发平台指南、教程和资料介绍（修改稿）

C++异常中的堆栈跟踪

STL序列式容器中删除元素的方法和陷阱 三

STL序列式容器中删除元素的方法和陷阱 一

STL关联式容器中删除元素的方法和陷阱 四

地基上的脚印 ----读《编码的奥秘》有感

ruby and ruby on rails

programming

最近访客更多访客>>

STL序列式容器中删除元素的方法和陷阱二

STL序列式容器中删除元素的方法和陷阱三

STL序列式容器中删除元素的方法和陷阱一

STL关联式容器中删除元素的方法和陷阱四