ATL容器——CAtlMap,CRBMap

前言

在编写Windows程序的时候，使用ATL中的容器非常方便，而网上相关的资料非常少，在此我做些总结，希望能帮助到需要的朋友！

简介

头文件为<atlcoll.h>

由于CAtlMap和CRBMap的操作非常相似，所以在此就一并讲了

CAtlMap是基于哈希表的容器，类似于STL中的hash_map或unordered_map，当没有hash冲突的时候查找时间复杂度为O(1)，否则最坏为O(n)，由于内部开辟了大数组占用空间较多，所以当只需要存储少量元素时，请考虑改用 CSimpleMap 类。

CRBMap是基于红黑树的容器，类似于STL中的map，其插入、查找、删除的时间复杂度近似为O(logn)

常用方法

CAtlMap

    IsEmpty() 			判断是否为空
    GetCount()  		获取元素个数
    GetAt()				通过迭代器获取键值对
    GetKeyAt()			通过迭代器获取键值
    GetNext()			获取下个迭代器
    GetStartPosition()	获取起始迭代器
    GetValueAt()		通过迭代器获取value
    Lookup() 			查找key所在迭代器
    RemoveAll()			清除所有元素
    RemoveAtPos()		通过迭代器删除元素
    RemoveKey()			根据键值删除元素
    SetAt()				存储元素，存在则覆盖
    SetValueAt()		通过迭代器来设置值


CRBMap

    与CAtlMap的操作基本一样，只有少数几个区别：
    没有GetStartPosition()而用GetHeadStation()替换
    没有RemoveAtPos()而用RemoveAt()替换
    

CAtlMap示例代码

#include <atlcoll.h>
#include <atlstr.h>

using namespace ATL;

typedef CAtlMap<int, CString> CMyMap;

void PrintMap(CMyMap& atlMap)
{
	printf("#########################\n");
	printf("Count=%d\n", atlMap.GetCount());
	int nKey;
	CString strVal;
	//获取起始迭代器
	for (POSITION pos = atlMap.GetStartPosition();pos;)
	{
		CMyMap::CPair *pair = atlMap.GetNext(pos); //可以查看GetNext的源码，该函数将pos指向下个节点，但返回的是当前节点的值
		printf("%d=>%s\n", pair->m_key, pair->m_value.GetBuffer(0));
	}
	printf("#########################\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
	//底层基于hash表
	CMyMap atlMap;

	//插入数据
	atlMap.SetAt(8, "nihao");
	atlMap.SetAt(88, "asd");
	atlMap.SetAt(888, "fff");
	//重复数据覆盖
	atlMap.SetAt(888, "ff");
	//打印
	PrintMap(atlMap);
	//查找
	CMyMap::CPair* p = atlMap.Lookup(888);
	if (NULL != p)
	{
		printf("find %d=>%s\n", p->m_key, p->m_value.GetBuffer(0));
		//修改值
		p->m_value = "test";
	}
	else
	{
		printf("no find\n");
	}
	//打印
	PrintMap(atlMap);
	//删除某个key
	atlMap.RemoveKey(99); //删除一个不存在的键值
	atlMap.RemoveKey(88);
	PrintMap(atlMap);
	//使用遍历法清空，效率较低
	POSITION pos;
	while ((pos = atlMap.GetStartPosition()) != NULL)
	{
		//通过迭代器获取键值对，打印要删除的键值对
		CMyMap::CPair* p = atlMap.GetAt(pos);
		if (p != NULL)
		{
			printf("remove %d=>%s\n", p->m_key, p->m_value.GetBuffer(0));
		}
		atlMap.RemoveAtPos(pos);
	}
	PrintMap(atlMap);
	//一次性清空
	atlMap.RemoveAll();
}

输出

CRBMap示例代码

#include <atlcoll.h>
#include <atlstr.h>

using namespace ATL;

//typedef CAtlMap<int,CString> CMyMap;
typedef CRBMap<int, CString> CMyMap;

void PrintMap(CMyMap& rbMap)
{
	printf("#########################\n");
	printf("Count=%d\n", rbMap.GetCount());
	int nKey;
	CString strVal;
	//获取起始迭代器
	for (POSITION pos = rbMap.GetHeadPosition(); pos;)
	{
		CMyMap::CPair* pair = rbMap.GetNext(pos); //获取当前节点的值，返回pos的下个位置
		printf("%d=>%s\n", pair->m_key, pair->m_value.GetBuffer(0));
	}
	printf("#########################\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
	//底层基于红黑树
	CMyMap rbMap;

	//插入数据
	rbMap.SetAt(8, "nihao");
	rbMap.SetAt(88, "asd");
	rbMap.SetAt(888, "fff");
	//重复数据覆盖
	rbMap.SetAt(888, "ff");
	//打印
	PrintMap(rbMap);
	//查找
	CMyMap::CPair* p = rbMap.Lookup(888);
	if (NULL != p)
	{
		printf("find %d=>%s\n", p->m_key, p->m_value.GetBuffer(0));
		//修改值
		p->m_value = "test";
	}
	else
	{
		printf("no find\n");
	}
	//打印
	PrintMap(rbMap);
	//删除某个key
	rbMap.RemoveKey(99); //删除一个不存在的键值
	rbMap.RemoveKey(88);
	PrintMap(rbMap);
	//使用遍历法清空
	POSITION pos;
	while ((pos = rbMap.GetHeadPosition()) != NULL) //效率实在是太低，每次删除都可能会导致红黑树内部结构的变化
	{
		//通过迭代器获取键值对，打印要删除的键值对
		CMyMap::CPair* p = rbMap.GetAt(pos);
		if (p != NULL)
		{
			printf("remove %d=>%s\n", p->m_key, p->m_value.GetBuffer(0));
		}
		rbMap.RemoveAt(pos);
	}
	PrintMap(rbMap);
	//一次性清空
	rbMap.RemoveAll();
}

输出

结语

基本上常用的功能在代码里都体现了，具体参考代码吧！