Clist的RemoveAll()函数速度很慢

Question

       CList<CPoint,CPoint&> listPoint;
 
for (int i = 0; i < 500000; i ++)
{
   listPoint.AddTail(CPoint(i,i));
 } listPoint.RemoveAll();     本人程序中用到大量数据，但是我用的是Clist存储，因为设计到修改插入某个数据，但是有时候又要清空链表，所以就用RemoveAll()函数，但是发现RemoveAll()函数速度很慢，例如上面的程序要四五秒的时间，那位有自己写的链表速度比较快的，并且使用上和clist一样给我发一个，不胜感激！邮箱[email protected]

Answer 1

如果插入和删除节点不是很频繁的话， 建议使用CArray
CList以链表的方式存储节点，因此插入和删除只需维护链表信息，而无需移动数据，但是寻址比较繁琐
CArray是以块方式存储节点，就类似于数组，寻址和全部释放的操作非常快，但是插入和删除将产生比较大的数量搬移问题，提高CArray插入的效率的方式就是先分配一个较大的空间，然后再操作可以对比下运行速度  {   
    CArray<POINT,POINT&> listPoint;
    listPoint.SetSize(500000);
    DWORD dw1, dw2, dw3;
    dw1 = GetTickCount();
    for (int i = 0; i < 500000; i ++)
    {
      POINT pt ={i, i};
      listPoint[i] = pt;
    }
    dw2 = GetTickCount();
    listPoint.RemoveAll();
    dw3 = GetTickCount();    TRACE(_T("T1=%ld T2=%ld\n"), dw2-dw1, dw3-dw2);
  }

Answer 2

慢是由for语句引起的并不是removeAll

Answer 3

偶坚信RemoveAll的速度一定比你Add的快

Answer 4

我起初也是认为是多次for循环引起的时间长，但是测试结果却真是删除慢DWORD dw1, dw2, dw3;
dw1 = GetTickCount();
CList<CPoint,CPoint&> listPoint;  
for (int i = 0; i < 500000; i ++)
{
  listPoint.AddTail(CPoint(i,i));
}
dw2 = GetTickCount();
listPoint.RemoveAll() 
dw3 = GetTickCount();
TRACE(_T("T1=%ld T2=%ld\n"), dw2-dw1, dw3-dw2);
结果T1=328 T2=4195于是我大概看了一下CList的实现代码，它插入的时候一次分配10个单元，这样后续的9个节点插入速度就很快， 而删除则是逐个进行的

Answer 5

谢谢大家的积极响应，特别是1楼兄弟，的确CArray很快，这个我也测试过，但是我有很多的算法用的是CList改动起来很麻烦，另外有很多地方涉及到修改某个元素，所以不能用CArray，谢谢！