CArray：增加元素非常快, 查询元素慢(循环方式)

CMap：增加元素很慢,查询元素非常快(Lookup方法)【随机地频繁地访问元素时,建议使用CMAP】
CList：插入删除很快。但是通过索引访问很慢

1. 数组--CArray
   访问方法及效率和普通的数组一样，比普通数组强大的功能是可以改变数组的大小。
    Array采用队列方式存储数据，因而其内部数据元素是以物理方式顺序排列的， 所以检索、顺序执行GetAt()等函数的速度是相当快的。但是由于每次队列长度变化后，数据都要重新申请内存、拷贝内存、释放内存，因而 Insert/Add/RemoveAt()的速度都很慢。如果你使用的数据元素尺寸相当大，而且数组的操作相当复杂，频繁使用InsertAt /SetAt/RemoveAt等，应该考虑使用CList来代替。但是如果考虑Array中存储指针而不是数据本身，效率也可以接受。
   特点：通过索引(数组下标)访问的速度很快，但是插入删除操作很慢，因为插入删除操作时，是需要移动元素的。
   访问方法：通过索引访问，普通的数组怎么用，它就可以怎么用。

MFC数组类CArray的使用的操作详解

MFC的数组类支持的数组类似于常规数组，可以存放任何数据类型。常规数组在使用前必须将其定义成能够容纳所有可能需要的元素，即先确定大小，而MFC数组类创建的对象可以根据需要动态地增大或减小，数组的起始下标是0，而上限可以是固定的，也可以随着元素的增加而增加，数组在内存中的地址仍然是连续分配的。
　　MFC定义了数组模板类CArray，并针对各种常用变量类型定义了CByteArray，CArray，CUIntArray，CDArray，CStringArray，CObArray，CPtrArray。

应用例子1：

CArray <CPoint,CPoint&> m_Array;

　　该语句定义一个CArray数组对象，模板类CArray有两个参数，第一个参数为数组元素的类型，该例中是CPoint，即m_Array是CPoint数 组；第二个参数为引用类型，一般有两种选择，一种选择与第一个参数类型相同，它意味着数组对象作为参数传递时，传递的是数组对象。第二种选择是第一个参数类型的引用，它意味着数组对象作为参数传递时，传递的是数组对象的指针。因此，尤其对于较复杂的数组结构类型，推荐使用引用传递，节约内存同时加快程序运行速度，正如本例使用的是CPoint&。、

注：

CArray<int,   int>   myArray;   //对于基本类型如int,char和float一般要用参数传递

m_Array.SetSize(10,10);

　　SetSize函数设定数组的大小，该函数有两个参数，第一个参数设定数组的大小；第二个参数设定数组增长时内存分配的大小，缺省值是－1，使用缺省值可以保证内存分配得更加合理。本例中第二个参数是10，意即增加一个数组元素会分配10个元素大小的内存供数组使用。 
　　您可以随时使用SetSize函数设定数组的大小，如果第一个参数值小于数组已有成员数量，多于第一个参数值的成员将被截去并释放相应内存。
　　在使用CArray数组前，最好先使用SetSize确定其大小并申请存储空间。如果不这样做，向数组中增加元素时，需要不断地移动和拷贝元素造成运行的低效率和内存碎块。

应用例子2：

void CArrayDlg::OnArrayCstring()

 {     
      CArray<CSTRING,CSTRING&> m_string;

      CString sztiger("tiger"); 

      CString szbear("bear");   

      CString szdog("dog");

      m_string.SetAtGrow(0,sztiger);

      m_string.SetAtGrow(2,szdog);       

      m_string.InsertAt(1,szbear);

}

代码简要说明：

m_string.SetAtGrow(2,szdog); edu-cn.com

　　SetAtGrow有两个参数，第一个参数决定数组元素的序号值，第二个参数是元素的值。该函数根据序号值设置相应数组元素的值，功能与SetAt相近，不同之处是使用该函数设置元素值时，如果序号值大于数组的上界，数组会自动增长。
　　编译运行程序，细心的读者您可能会看到，第一行字符是“tiger”，第二行字符是“bear”，这是我们预料之中的，但第三行是空串，第四行是“dog”。空串是怎样造成的呢？细分析下面三行代码就可以知道：

m_string.SetAtGrow(0,sztiger);m_string.SetAtGrow(2,szdog);m_string.InsertAt(1,szbear);

第一行设定元素0为“tiger”，这是没有疑义的。
第二行设定元素2为“dog”，但是在设定元素2的同时自动将元素1填充为空串。
第三行插入“bear”为元素1，同时原来的元素1和元素2后移为元素2和元素3。

怎么样，这回明白了吧。

m_string.InsertAt(1,szbear);

　　InsertAt函数在指定序号处插入相应元素，该函数在执行过程中，插入点后面的元素会自动后移。dc.TextOut(10,displayPos,m_string[x]);其中，m_string[x]是数组类对操作符[]的重载，数组类CArray允许使用[]操作符，类似于的常规数组。m_string[x]也可以用m_string.GetAt(x)替代。

m_string.RemoveAt(2); 

RemoveAt只有一个参数，即元素序号值。该函数根据元素序号值删除相应元素值，后面的元素会自动前移。


　　最后再说明一点：RemoveAt，InsertAt函数操作时会使得数组元素移位，运行时间大于SetAt，RemoveAll，Add函数。

2. 双链表--CList
   
   特点：插入删除很快。但是通过索引访问很慢，因为通过索引访问的时候，实际上是链表头开始计算个数的。所以在遍历链表的时候不要这样写：
      for(int i=0; i<list.GetCount(); ++i)
      {
           POSITION pos = list.FindIndex(i);
           Item item = list.GetAt(pos);
           ...
       }
    访问方法：通过POSITION变量访问，它实际上就是双链表节点的指针。我觉得这种访问方法比加个什么iterator要好，因为很多时候我们都是在对链表进行插入删除操作，这个时候一个iterator的功能有限。

3. 散列(hash)表--CMap    

    特点：通过散列算法将key计算一个索引值，基本上就是一个空间换时间的应用。对于重复的key，它和大多数的hash表结构一样，采用了一个链表。所以，如果key重复比较多的话，他的查找还是很慢的。
    访问方法：也是用POSITION变量。不过需要注意的是，通过CMap提供的遍历函数得到的元素的顺序恰好和添加的顺序相反。

4. 二叉树--无对应类
    特点：一个排序二叉树的查找就是一个天生的二分法。所以，如果向二叉树中添加元素时需要进行比较的话，最好直接创建成二叉排序树，这样查找起来很快。例如，CMap在key重复时就可以用二叉树代替链表。