CArray CMap CList详解.doc

CArray,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。数组类变量类型变量数值范围头文件CArray通过模板类的参数类型设定各种类型 Afxtempl.hCByteArray8位无符号整数BYTE类型0255 Afxcoll.hCArray16位无符号整数WORD类型065535 Afxcoll.hCDArray32位无符号整数DWORD类型04294967295 Afxcoll.hCUIntArray32位无符号整数UINT类型04294967295 Afxcoll.hCStringArrayCString字符串string字符串 Afxcoll.hCObArrayCObject类及其派生类 Afxcoll.hCPtrArrayvoid*类型指针 Afxcoll.h应用例子1：CArray m_Array;该语句定义一个CArray数组对象，模板类CArray有两个参数，第一个参数为数组元素的类型，该例中是CPoint，即m_Array是CPoint数组；第二个参数为引用类型，一般有两种选择，一种选择与第一个参数类型相同，它意味着数组对象作为参数传递时，传递的是数组对象。第二种选择是第一个参数类型的引用，它意味着数组对象作为参数传递时，传递的是数组对象的指针。因此，尤其对于较复杂的数组结构类型，推荐使用引用传递，节约内存同时加快程序运行速度，正如本例使用的是CPoint&。、注：CArray myArray; /对于基本类型如int,char和float一般要用参数传递m_Array.SetSize(10,10);SetSize函数设定数组的大小，该函数有两个参数，第一个参数设定数组的大小；第二个参数设定数组增长时内存分配的大小，缺省值是1，使用缺省值可以保证内存分配得更加合理。本例中第二个参数是10，意即增加一个数组元素会分配10个元素大小的内存供数组使用。您可以随时使用SetSize函数设定数组的大小，如果第一个参数值小于数组已有成员数量，多于第一个参数值的成员将被截去并释放相应内存。在使用CArray数组前，最好先使用SetSize确定其大小并申请存储空间。如果不这样做，向数组中增加元素时，需要不断地移动和拷贝元素造成运行的低效率和内存碎块。应用例子2：void CArrayDlg:OnArrayCstring() CArray 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); 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_stringx);其中，m_stringx是数组类对操作符的重载，数组类CArray允许使用操作符，类似于的常规数组。m_stringx也可以用m_string.GetAt(x)替代。m_string.RemoveAt(2);RemoveAt只有一个参数，即元素序号值。该函数根据元素序号值删除相应元素值，后面的元素会自动前移。最后再说明一点：RemoveAt，InsertAt函数操作时会使得数组元素移位，运行时间大于SetAt，RemoveAll，Add函数。2.双链表-CList特点：插入删除很快。但是通过索引访问很慢，因为通过索引访问的时候，实际上是链表头开始计算个数的。所以在遍历链表的时候不要这样写：for(int i=0; ilist.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重复时就可以用二叉树代替链表。CListCarray链表#include #include #include void main() CList m_Array; /定义链表对象/ CArray m_Array; CPoint pt(1,1); m_Array.AddTail(pt); for(int i=1;i5;i+) for(int j=1;j7;j+) pt.x = pt.y = j*10; m_Array.AddTail(pt); pt.x = pt.y = i*100; m_Array.AddHead(pt); POSITION position,startAfterPT; pt.x = pt.y = 30; startAfterPT = m_Array.FindIndex(12); position = m_Array.Find(pt,star