关于list和vector的一点点试验

免费打工仔

在我的游戏中存在一个Actor_t的类
他的实例是一个角色，角色维护它自己的任务(Active_t)数组
我选择list（链表）作为动态数组，因为考虑到经常要删除任务
所以list快一些。

角色update时候需要找到这里已经执行完成的任务，并移出数组

所以我们要遍历数组 删除元素。

但因为list是强迭代器，就是在更改数组时候迭代器仍然有效
vector是弱迭代器，在更改数组时候，迭代器会失效
其实说白了 list是链表 vector是数组 而已

在这里写两个数组，删除数组里的偶数，看看两种容器的区别

1. 
   
2. vector<int> l;
   
3. l.push_back(1);
   
4. l.push_back(2);
   
5. l.push_back(3);
   
6. l.push_back(4);
   
7. l.push_back(5);
   
8. l.push_back(6);
   
9. l.push_back(7);
   
10. l.push_back(8);
    
11. vector< int >::iterator it;
    
12. 
    
13. for(it=l.begin();it!=l.end();++it)
    
14. {
    
15.         while(*it%2==0)
    
16.         {       
    
17.                 l.erase(it);       
    
18.                 if(it==l.end())
    
19.                         break;
    
20.         }
    
21.                
    
22.                 if(it==l.end())
    
23.                         break;
    
24. }
    
25. 
    

复制代码

[em16] [em16] [em16] [em16] [em16]

1. 
   
2. list<int> l;
   
3. l.push_back(1);
   
4. l.push_back(2);
   
5. l.push_back(3);
   
6. l.push_back(4);
   
7. l.push_back(5);
   
8. l.push_back(6);
   
9. l.push_back(7);
   
10. l.push_back(8);
    
11.        
    
12. list< int >::iterator it,it2;
    
13. for(it=l.begin();it!=l.end();++it)
    
14. {
    
15.         for(it2=it;*it%1==0;it2=it)
    
16.         {       
    
17.                 it++;
    
18.                 l.erase(it2);
    
19.                 if(it==l.end())
    
20.                         break;
    
21.         }
    
22.        
    
23.                 if(it==l.end())
    
24.                         break;
    
25. }
    

复制代码

最后试验了一下multimap，在同一个key下可以和list一样处理（可能就是
list实现的吧），但是不敢试验所有的key,因为如果是红黑树实现的话
删除了一个key可能树会改变，迭代器具体指哪里？

1. 
   
2. multimap<int, int> m;
   
3.         m.insert(pair<int,int>(1,1));
   
4.         m.insert(pair<int,int>(1,2));
   
5.         m.insert(pair<int,int>(1,3));
   
6.         m.insert(pair<int,int>(1,4));
   
7.         m.insert(pair<int,int>(1,5));
   
8.         m.insert(pair<int,int>(1,6));
   
9.         m.insert(pair<int,int>(1,7));
   
10.         m.insert(pair<int,int>(1,8));
    
11. 
    
12.         multimap<int,int>::_Pairii it;
    
13.         multimap<int,int>::iterator it2;
    
14.         it=m.equal_range(1);
    
15.         for(;it.first!=it.second;++it.first)
    
16.         {
    
17.                 for(it2=it.first;it.first->second%2==0;it2=it.first)
    
18.                 {
    
19.                         it.first++;
    
20.                                
    
21.                     m.erase(it2);
    
22.                         if(it.first==it.second)
    
23.                                 break;
    
24.                
    
25.                 }
    
26.                 if(it.first==it.second)
    
27.                                 break;
    
28.         }
    
29. 
    

复制代码

flyv

...........................

tarkey

list,vector的插入的时间复杂度是O(1)，查找和删除都是O(n)
map的插入，查找，删除则都是O(1)，效率一眼就看出来了。
比较严格的环境下，可以考虑用O(logn)或者O(1)的算法，而不要考虑O(n)的算法，试想你有100000个用户，每次发个消息都要根据ID来找实体的话，用O(n)的算法是要死人的。

另外map无法实现顺序遍历，而且一般也不需要对其进行遍利操作。

kypck

"list,vector的插入的时间复杂度是O(1)，查找和删除都是O(n)
map的插入，查找，删除则都是O(1)，效率一眼就看出来了。"
呵呵，这到是第一次听说。这样说好歹也得带几个条件啊，建议多看几本STL（如Effective STL）在来“指导”别人吧。

tarkey

楼上的去看看什么叫big-oh吧

kypck

哦！那你就基于big-Oh原则来解释一下你关于那几个container算法复杂程度的说法，同时说明STL的版本和使用的情况，我洗耳恭听？

tarkey

举个很简单的例子：
f(x) = 16
这种情况叫const，不管x如何变，其函数返回值永远是一个常量，这种在big-oh里面表示为O(1)
f(x) = 16*x 或者 f(x) = 16 + x
在用big-oh来表示的时候，都是O(n)，因为无论x如何变，函数值都只跟x的一次方相关
f(x) = log(2, x) 或者 f(x) = log(n, x)
都属于O(logn)，最典型的例子就是折半查找，或者说二叉数查找。
其他经常用到的还有O(nlogn), O(n^2), O(n^3)

那么如何测试f(x)呢，比如说有个循环：
for(i=0;i<x;i++) foo();
很明显，这个算法的复杂度就是O(x)，因为其函数可以衡量为f(x)
而
for(i=0;i<x;i++)
if(x % 2 == 0) foo();
else {
    foo1();
    foo2();
    foo3();
}
这样的复杂度虽然也是O(x)，但是其函数则是f(x) = x/2 + 3*x/2 = 2*x

不管是什么版本的STL，list的实现永远是用的链表，不管是单向链表也好，双向链表也好，插入的时间复杂度都是O(1)，即插入的时候不需要访问链表内的其他元素，而删除和查找则是O(n)，因为worest case情况下，是需要对整个链表进行遍利的。vector的实现原理跟list一样，都是链表。只有map的实现原理是用的hash表。

kypck

哦！谢谢你的关于Big-Oh的讲解。
不过照你的说法，我还有些问题不明白啊：1、vector的插入为什么是O(1)？ 2、list的删除为什么是O(n)？3、哪个版本的STL实现vector用的是链表啊？4、哪个版本的STL实现map,multimap,set用的是hash表？

tarkey

自己去看看数据结构的书吧。
基本的数据结构就那几种，线性表，链表，树，图，HASH表

kypck

昏，我真是服了你了。
刚毕业的吧，看来你在大学基础的东西里学的还不错，不过你真该好好看看STL的书。不太确定的东西就不要想当然，因为很多人会根据你的发贴量而相信了你所说的，这样会被误导的。