小明思考

高性能服务器端计算
posts - 70, comments - 428, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

[STL] 循环中erase

Posted on 2006-12-27 18:01 小明 阅读(8929) 评论(12)  编辑 收藏 引用 所属分类: C/C++
sometimes,我们需要手写循环(相对于for_each)来erase容器内某些元素,新手经常会犯一些错误。这里总结一下比较常用的固定写法。

删除所有偶数项,并打印出删除的项

1. vector/queue
正确方法1:
void erase(vector<int> &v)
{
    
for(vector<int>::iterator vi=v.begin();vi!=v.end();)
    {
        
if(*vi % 2 == 0)
        {
            cout 
<< "Erasing " << *vi << endl;
            vi 
= v.erase(vi);
        }
        
else ++vi;
    }
}
正确方法2:
void erase2(vector<int> &v)
{
    
for(vector<int>::reverse_iterator ri=v.rbegin();ri!=v.rend();)
    {
        
if(*ri % 2 == 0)
        {
            cout 
<< "Erasing " << *ri << endl;
            v.erase((
++ri).base());
        }
        
else ++ri;
    }
}

由于方法2是逆向删除,效率较高,推荐!

2.map/list
正确方法
void erase(map<int,int> &m)
{
    
for(map<int,int>::iterator mi=m.begin();mi!=m.end();)
    {
        
if(mi->second % 2 == 0)
        {
            cout 
<< "Erasing " << mi->second << endl;
            m.erase(mi
++);
        }
        
else ++mi;
    }
}

Feedback

# re: [STL] 循环中erase  回复  更多评论   

2006-12-27 19:36 by Dain
还有其他的容器呢

# 我的实现  回复  更多评论   

2006-12-27 21:44 by eXile
// for vector, deque

template <class Container, class T>
inline
void vector_erase(Container & c, T const& t)
{
c.erase(std::remove(c.begin(), c.end(), t), c.end());
}

template <class Container, class Pred>
inline
void vector_erase_if(Container & c, Pred pred)
{
c.erase(std::remove_if(c.begin(), c.end(), pred), c.end());
}

// for list, set, map
template <class Container, class T>
void list_erase(Container & c, T const& t)
{
typename Container::iterator
b = c.begin(), e = c.end(), prev = b;
while (b != e)
{
++b;
if (*prev == t) c.erase(prev);
prev = b;
}
}

template <class Container, class Pred>
void list_erase_if(Container & c, Pred pred)
{
typename Container::iterator
b = c.begin(), e = c.end(), prev = b;
while (b != e)
{
++b;
if (pred(*prev)) c.erase(prev);
prev = b;
}
}

# re: [STL] 循环中erase  回复  更多评论   

2006-12-28 09:41 by 小明
@eXile
如果需要打印出被删除的元素呢?

对于list,如果只要删除某个项,调用list.remove就可以了

# re: [STL] 循环中erase  回复  更多评论   

2006-12-28 12:22 by eXile
1)打印出被删除的元素, 很简单
struct MyPred
{
bool operator()(int n) const
{
if(n%2 == 0) {cout << "Erasing " << n << endl; return true; }
else return false;
}
};

vector<int> v;
vector_erase_if(v, MyPred());
2)list提供了remove方法,但是set,map没有
(实际上这几行代码都是从STL的list源码中抄出来的,主要用于set 和map);

# re: [STL] 循环中erase  回复  更多评论   

2006-12-31 16:41 by pjqblues
逆向删除,效率较高,为什么?????

# re: [STL] 循环中erase  回复  更多评论   

2007-01-04 11:48 by 小明
@pjqblues

逆向删除,移动的项会变少

# re: [STL] 循环中erase  回复  更多评论   

2007-02-13 23:31 by 李锦俊
方法2不错!谢谢。

# re: [STL] 循环中erase  回复  更多评论   

2007-02-14 15:49 by gql
方法2是错的!应该是(ri++).base().
给出的循环删除方法太低效!

# re: [STL] 循环中erase  回复  更多评论   

2007-02-14 16:29 by Kooyu
抱歉,看错了。方法2应该是可以的!

# re: [STL] 循环中erase  回复  更多评论   

2008-07-01 11:58 by 企业即时通讯
MAP,已知KEY,如何删除项?

# re: [STL] 循环中erase  回复  更多评论   

2010-03-03 21:06 by 楚竹荷叶
方法2跑起来会抛异常的!

# re: [STL] 循环中erase  回复  更多评论   

2012-10-25 20:33 by ZHYB
@楚竹荷叶
我也发现了,vector如果只有一个值,逆向删除就会抛出异常,正向删除不会

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理