colorful

zc qq:1337220912

 

STL的remove函数和list的remove成员函数

http://www.cnblogs.com/kinuxroot/archive/2013/01/25/stl_remove_problem.html

今天看书刚刚看的,就记录下来吧。这可能是老生常谈了,权且作为一个警醒的例子吧。

大家都知道STL有两个非常重要的组成部分,容器和算法。

算法就是一个个的函数,通过迭代器和容器关联在一起,完成一些工作。

算法和容器的分离为程序设计提供了很大的灵活性,但是也带来了一些负面效果,下面我讲的这个问题就是一个例子。

STL的算法里有一个remove函数,而list自身也有一个remove函数,功能都是一样的,移除某一个元素,那我们应该使用哪一个呢?

看一下下面这段程序

复制代码
 1     list<int> numbers;  2   3     for ( int number = 0; number <= 6; number ++ ) {  4         numbers.push_front(number);  5         numbers.push_back(number);  6     }  7   8     copy(numbers.begin(), numbers.end(),  9             ostream_iterator<int>(cout, " ")); 10     cout << endl; 11  12     // remove algorithm will remove element but not erase the element from container 13     // it will return the logical desination of container 14     list<int>::iterator endOfNumbers = remove(numbers.begin(), numbers.end(), 3); 15  16     copy(numbers.begin(), numbers.end(), 17             ostream_iterator<int>(cout, " ")); 18     cout << endl;
复制代码

输出是什么呢?

第一行肯定是6 5 4 3 2 1 0 0 1 2 3 4 5 6,那么第二行会输出什么?

如果是没有仔细看过STL的人肯定会认为remove(number.begin(), numbers.end(), 3)会移除所有值为3的元素。所以输出是:6 5 4 2 1 0 0 1 2 4 5 6。

但是,我们看一下它真正的输出:

6 5 4 2 1 0 0 1 2 4 5 6 5 6

你可能会非常惊讶,为什么最后会多出5和6两个数呢?

我们来讲一下remove算法的原理。

remove算法工作时并不是直接把元素删除,而是用后面的元素替代前面的元素,也即是说如果我对1234这个序列remove 2,返回的序列是 1344(3被复制到2的位置,4被复制到3的位置)。

这样上面的例子就好解释了,那两个3的元素并没有被移除,而是用后面的元素覆盖了前面的元素。多出的那两个数没有被移除掉而已。

那么我们应该如何真正完成移除呢?remove函数会返回一个迭代器,那个迭代器是这个序列的逻辑终点,也即是我代码里的endOfNumbers,它指向倒数第二个5上。

于是我们要利用list的erase函数完成元素移除

numbers.erase(endOfNumbers, numbers.end());

这样我们就完成了我们的工作,稍稍有点曲折……

其实我们可以把这两步放在一起,比如如果我想接着移除所有值为2的元素

numbers.erase(remove(numbers.begin(), numbers.end(), 2), numbers.end());

这样我们就可以一步到位了。

但是这样好么?

不好。

大家会发现,remove函数的原理是复制而不是指针的移动(因为函数操纵的是迭代器,而C++的迭代器没有定义删除操作),这样会带来一个问题:我们使用list是因为它的修改的效率非常高,改变一下指针就可以了。而这里我们复制了元素,如果在vector中,可能还是高效的,因为vector无论如何都要复制,而对于list就不是如此了,会极度降低我们的效率。

那我们怎么办呢?

答案是使用list自己的remove函数

numbers.remove(1);

我们可以这样删除所有值为1的元素。

也即是说,如果要删除list中的元素,我们应该使用list的remove成员函数,而不是remove算法

小结

我们都知道,STL是一个效率、复用性、灵活性折衷的产物,其中效率至关重要,所以STL已经禁止了一些效率低的操作(比如list的随机访问),而鼓励你去使用其它的容器。

但是,在算法中,为了灵活性,STL还是会牺牲一些东西,比如我们这个例子。

个人觉得,STL作为C++标准库的一个组成部分,特点和C++本身一模一样,强大而复杂,有些地方难以理解,很多细节需要学习注意,我们要学会避免陷入某些陷阱之中,比如这个例子就是一个效率陷阱。

其它更多的陷阱是错误处理方面的,STL本身并没有规定过多的错误处理,大部分的错误处理都交给了我们,理由很简单:性能至上,如果一个东西自身没有错误检查,我们可以包装一个带错误检查的类;但是如果这个东西自身就带了错误检查,那么我们就没有任何方法提升它的效率了。这也是很多C和C++库的设计原则。

所以,很多时候,需要我们深入细节,然后再决定到底怎么做。因为C++就是如此:有很多路可以走,需要我们自己选择最好的一条路。

分类: C++

posted on 2015-10-14 15:50 多彩人生 阅读(442) 评论(1)  编辑 收藏 引用 所属分类: boost

评论

# re: STL的remove函数和list的remove成员函数[未登录] 2015-10-14 17:27 chipset

remove函数并不是真正删除,而是取代,然后调析构,built-in类型没有析构函数结果就发现只是向前移动了一下,仅覆盖而已。
复制元素并非就一定不高效,对于built-in类型,复制比修改指针高效,毕竟程序设计里小对象比大对象常见的多。再说了,大对象哪里有动不动就拷贝的,那是设计失误。
vector的删除和插入都建议在尾进行,否则效率低下,因此就没有.pop_front这种货。  回复  更多评论   


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


导航

统计

常用链接

留言簿(3)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜