ATL container - catlmap, crbmap

Preface

Writing Windows When it comes to programming , Use ATL The container in is very convenient , There are very few relevant information on the Internet , Here I would like to make a summary , Hope to help friends in need ！

brief introduction

The header file is <atlcoll.h>

because CAtlMap and CRBMap The operation of is very similar , So let's talk about it here

CAtlMap Is based on Hashtable The container of , Be similar to STL Medium hash_map or unordered_map, When there is no hash In case of conflict, the search time complexity is O(1), Otherwise, the worst is O(n), Due to the large array opened inside, it takes up more space , So when only a few elements need to be stored , Please consider using CSimpleMap class .

CRBMap It's a container based on red black tree , Be similar to STL Medium map, Its insertion 、 lookup 、 The time complexity of deletion is approximately O(logn)

Common methods

CAtlMap

    IsEmpty() 			 Determine whether it is null 
    GetCount()  		 Get the number of elements 
    GetAt()				 Get key value pairs through iterators 
    GetKeyAt()			 Get the key value through the iterator 
    GetNext()			 Get the next iterator 
    GetStartPosition()	 Get the start iterator 
    GetValueAt()		 Get... Through iterators value
    Lookup() 			 lookup key Where the iterator 
    RemoveAll()			 Remove all elements 
    RemoveAtPos()		 Delete elements through iterators 
    RemoveKey()			 Delete the element according to the key value 
    SetAt()				 Storage elements , Existence covers 
    SetValueAt()		 Set the value through the iterator 


CRBMap

     And CAtlMap The operation is basically the same , There are only a few differences ：
     No, GetStartPosition() While using GetHeadStation() Replace 
     No, RemoveAtPos() While using RemoveAt() Replace 
    

CAtlMap Sample code

#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;
	// Get the start iterator 
	for (POSITION pos = atlMap.GetStartPosition();pos;)
	{
		CMyMap::CPair *pair = atlMap.GetNext(pos); // You can see GetNext Source code , This function will pos Point to the next node , But it returns the value of the current node 
		printf("%d=>%s\n", pair->m_key, pair->m_value.GetBuffer(0));
	}
	printf("#########################\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
	// Bottom based hash surface 
	CMyMap atlMap;

	// insert data 
	atlMap.SetAt(8, "nihao");
	atlMap.SetAt(88, "asd");
	atlMap.SetAt(888, "fff");
	// Duplicate data coverage 
	atlMap.SetAt(888, "ff");
	// Print 
	PrintMap(atlMap);
	// lookup 
	CMyMap::CPair* p = atlMap.Lookup(888);
	if (NULL != p)
	{
		printf("find %d=>%s\n", p->m_key, p->m_value.GetBuffer(0));
		// Modified value 
		p->m_value = "test";
	}
	else
	{
		printf("no find\n");
	}
	// Print 
	PrintMap(atlMap);
	// Delete some key
	atlMap.RemoveKey(99); // Delete a key value that does not exist 
	atlMap.RemoveKey(88);
	PrintMap(atlMap);
	// Use traversal to empty , Low efficiency 
	POSITION pos;
	while ((pos = atlMap.GetStartPosition()) != NULL)
	{
		// Get key value pairs through iterators , Print key value pairs to be deleted 
		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);
	// One time emptying 
	atlMap.RemoveAll();
}

Output

CRBMap Sample code

#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;
	// Get the start iterator 
	for (POSITION pos = rbMap.GetHeadPosition(); pos;)
	{
		CMyMap::CPair* pair = rbMap.GetNext(pos); // Get the value of the current node , return pos Your next position 
		printf("%d=>%s\n", pair->m_key, pair->m_value.GetBuffer(0));
	}
	printf("#########################\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
	// The bottom is based on the red and black trees 
	CMyMap rbMap;

	// insert data 
	rbMap.SetAt(8, "nihao");
	rbMap.SetAt(88, "asd");
	rbMap.SetAt(888, "fff");
	// Duplicate data coverage 
	rbMap.SetAt(888, "ff");
	// Print 
	PrintMap(rbMap);
	// lookup 
	CMyMap::CPair* p = rbMap.Lookup(888);
	if (NULL != p)
	{
		printf("find %d=>%s\n", p->m_key, p->m_value.GetBuffer(0));
		// Modified value 
		p->m_value = "test";
	}
	else
	{
		printf("no find\n");
	}
	// Print 
	PrintMap(rbMap);
	// Delete some key
	rbMap.RemoveKey(99); // Delete a key value that does not exist 
	rbMap.RemoveKey(88);
	PrintMap(rbMap);
	// Use traversal to empty 
	POSITION pos;
	while ((pos = rbMap.GetHeadPosition()) != NULL) // The efficiency is too low , Each deletion may lead to changes in the internal structure of the red black tree 
	{
		// Get key value pairs through iterators , Print key value pairs to be deleted 
		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);
	// One time emptying 
	rbMap.RemoveAll();
}

Output

Conclusion

Basically, the commonly used functions are reflected in the code , Refer to the code for details ！