std::list调用std::remove_if比list::remove到底哪个快?

zuiwei

<<effective stl>> 书上说list用remove_if比remove快，中文版原文是这样的:
去除一个容器中满足一个特定判定式的所有对象：
如果容器是vector、string或deque，使用erase-remove_if惯用法。
如果容器是list，使用list::remove_if。
如果容器是标准关联容器，使用remove_copy_if和swap，或写一个循环来遍历容器元素，当你把迭代器传给erase时记得后置递增它。

×××××××××××××××××××××××××××××××××××××××××
但是问题是既然都是遍历一遍然后删除，凭什么说std::remove_if比list::remove要快?

我测试了一下发现这个说法并不准确。下面这个代码
(1)元素个数是50k和200k的时候，std::remove_if快
(2)元素个数2M/5M个的时候,remove快。

这是为什么?
<<effective stl>>书上的说法是否确切，

1. 
   
2. #include"stdafx.h"
   
3. #include<windows.h>
   
4. #include<algorithm>
   
5. #include<iostream>
   
6. #include<iterator>
   
7. #include<string>
   
8. #include<deque>
   
9. #include<list>
   
10. #include<vector>
    
11. using namespace std;
    
12. int main(void){
    
13. #define LOOP 5000000
    
14.         typedef int valuetype;
    
15.         typedef list<valuetype> li;
    
16.         {
    
17.                 li vli;
    
18.                 for(int i=0;i<LOOP;++i){
    
19.                         vli.push_back(1);
    
20.                         vli.push_back(2);
    
21.                 }
    
22.                 DWORD ret1=GetTickCount();        
    
23.                 vli.remove(2);
    
24.                 DWORD ret2=GetTickCount();        
    
25.                 cout<<"list shrink:"<<ret2-ret1<<endl;
    
26.         }
    
27.         {
    
28.                 li vli;
    
29.                 for(int i=0;i<LOOP;++i){
    
30.                         vli.push_back(1);
    
31.                         vli.push_back(2);
    
32.                 }
    
33.                 DWORD ret1=GetTickCount();        
    
34.                 remove_if(vli.begin(),vli.end(),[=](valuetype i){return i==2;});
    
35.                 DWORD ret2=GetTickCount();        
    
36.                 cout<<"list shrink:"<<ret2-ret1<<endl;
    
37.         }
    
38.         return 0;
    
39. }
    

复制代码

bruceteen

我这人看到烂代码就喜欢改一下，楼主莫怪

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <list>
   
4. #include <ctime>
   
5. using namespace std;
   
6. 
   
7. int main(void)
   
8. {
   
9.     const size_t LOOP = 5000000;
   
10. 
    
11.     typedef list<int> li;
    
12.     {
    
13.         li vli;
    
14.         for( size_t i=0; i<LOOP; ++i )
    
15.         {
    
16.             vli.push_back( i&1 ? 2 : 1 );
    
17.         }
    
18.         clock_t ret1 = clock();
    
19.         vli.remove( 2 );
    
20.         clock_t ret2 = clock();
    
21.         cout << "list shrink:" << ret2-ret1 << endl;
    
22.     }
    
23.     {
    
24.         li vli;
    
25.         for( size_t i=0; i<LOOP; ++i )
    
26.         {
    
27.             vli.push_back( i&1 ? 2 : 1 );
    
28.         }
    
29.         clock_t ret1 = clock();
    
30.         vli.erase( remove(vli.begin(),vli.end(),2), vli.end() );
    
31.         clock_t ret2 = clock();
    
32.         cout << "list shrink:" << ret2-ret1 << endl;
    
33.     }
    
34. 
    
35.     return 0;
    
36. }

复制代码

zuiwei

bruceteen 发表于 2012-04-09 11:20
我这人看到烂代码就喜欢改一下，楼主莫怪

我测试了3个版本，remove,remove_if和erase+remove。发现一个比一个慢:

1. 
   
2. #include"stdafx.h"
   
3. #include<windows.h>
   
4. #include<algorithm>
   
5. #include<iostream>
   
6. #include<iterator>
   
7. #include<string>
   
8. #include<deque>
   
9. #include<list>
   
10. #include<vector>
    
11. using namespace std;
    
12. int main(void){
    
13. #define LOOP 5000000
    
14.         typedef int valuetype;
    
15.         typedef list<valuetype> li;
    
16.         {
    
17.                 li vli;
    
18.                 for(int i=0;i<LOOP;++i){
    
19.                         vli.push_back(1);
    
20.                         vli.push_back(2);
    
21.                 }
    
22.                 DWORD ret1=GetTickCount();        
    
23.                 vli.remove(2);
    
24.                 DWORD ret2=GetTickCount();        
    
25.                 cout<<"list shrink:"<<ret2-ret1<<endl;
    
26.         }
    
27.         {
    
28.                 li vli;
    
29.                 for(int i=0;i<LOOP;++i){
    
30.                         vli.push_back(1);
    
31.                         vli.push_back(2);
    
32.                 }
    
33.                 DWORD ret1=GetTickCount();        
    
34.                 remove_if(vli.begin(),vli.end(),[=](valuetype i){return i==2;});
    
35.                 DWORD ret2=GetTickCount();        
    
36.                 cout<<"list shrink:"<<ret2-ret1<<endl;
    
37.         }
    
38.         {
    
39.                 li vli;
    
40.                 for(int i=0;i<LOOP;++i){
    
41.                         vli.push_back(1);
    
42.                         vli.push_back(2);
    
43.                 }
    
44.                 DWORD ret1=GetTickCount();        
    
45.                 vli.erase(remove(vli.begin(),vli.end(),2),vli.end());
    
46.                 DWORD ret2=GetTickCount();        
    
47.                 cout<<"list shrink:"<<ret2-ret1<<endl;
    
48.         }        return 0;
    
49. }
    

复制代码

list shrink:547
list shrink:610
list shrink:1797

这是为什么呢? 我感觉3个时间应该基本一致才对啊

变异老鼠

第二个忘记 erase 了。

顶楼的代码也是……

zuiwei

变异老鼠 发表于 2012-04-09 15:38
第二个忘记 erase 了。

顶楼的代码也是……

加上了以后，结果也一样啊

变异老鼠

g++ 4.6.3 x86-64
-std=gnu++0x -Wall -Wextra -O2

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <list>
   
4. 
   
5. #include <stdint.h>
   
6. 
   
7. using namespace std;
   
8. 
   
9. inline uint64_t rdtsc()
   
10. {
    
11.     uint32_t eax, edx;
    
12.     asm("rdtsc" : "=a"(eax), "=d"(edx));
    
13.     return ((uint64_t)edx << 32) | eax;
    
14. }
    
15. 
    
16. int main(void){
    
17.     int const LOOP = 50000;
    
18.     typedef int valuetype;
    
19.     typedef list<valuetype> li;
    
20.     {
    
21.         // CPU warming up
    
22.         uint64_t const CLOCKS_TO_WAIT = 1000000000;
    
23.         uint64_t start = rdtsc();
    
24.         while(rdtsc() - start < CLOCKS_TO_WAIT)
    
25.             ;
    
26.     }
    
27.     {
    
28.         li vli;
    
29.         for(int i=0;i<LOOP;++i){
    
30.             vli.push_back(1);
    
31.             vli.push_back(2);
    
32.         }
    
33.         uint64_t ret1 = rdtsc();
    
34.         vli.remove(2);
    
35.         uint64_t ret2 = rdtsc();
    
36.         cout<<"list shrink:"<<ret2-ret1<<endl;
    
37.     }
    
38.     {
    
39.         li vli;
    
40.         for(int i=0;i<LOOP;++i){
    
41.             vli.push_back(1);
    
42.             vli.push_back(2);
    
43.         }
    
44.         uint64_t ret1 = rdtsc();
    
45.         vli.erase(remove_if(vli.begin(),vli.end(),[=](valuetype i){return i==2;}), vli.end());
    
46.         uint64_t ret2 = rdtsc();
    
47.         cout<<"list shrink:"<<ret2-ret1<<endl;
    
48.     }
    
49.     {
    
50.         li vli;
    
51.         for(int i=0;i<LOOP;++i){
    
52.             vli.push_back(1);
    
53.             vli.push_back(2);
    
54.         }
    
55.         uint64_t ret1 = rdtsc();
    
56.         vli.erase(remove(vli.begin(),vli.end(),2),vli.end());
    
57.         uint64_t ret2 = rdtsc();
    
58.         cout<<"list shrink:"<<ret2-ret1<<endl;
    
59.     }
    
60.     return 0;
    
61. }
    

复制代码

list shrink:2559236
list shrink:4978882
list shrink:4897164

zuiwei

变异老鼠 发表于 2012-04-09 17:41
g++ 4.6.3 x86-64
-std=gnu++0x -Wall -Wextra -O2list shrink:2559236
list shrink:4978882

还是remove最快，erase(remove_if)和erase(remove)都很慢

变异老鼠

好吧，忽然发现之前都没看清楚你的问题……

书上说的是：对于 list，用 list::remove_if；对于其他三个容器，用 std::remove_if + std::erase。

这里没有 list::remove 什么事。

如果是 list::remove_if 和 list::remove 相比，只要编译器能把函数对象优化掉，速度应该是差不多的。

std::remove_if 和 std::remove 相比也一样。