CMap

The following is an example of using CMap.

typedef CMap <int, int, CString, CString&> CIntegerMap;

    CIntegerMap m_IntegerMap;
    CString String;
    int Index;
m_IntegerMap.SetAt(Index, CString(String));
Position = m_IntegerMap.GetStartPosition();
while (Position!=NULL) {
	m_IntegerMap.GetNextAssoc(Position, Index, String);
	m_Outputfile.WriteString(String);
	String.Format(" %i\n", Index);
	m_Outputfile.WriteString(String);
	}
m_IntegerMap.RemoveAll();

Hash Keys

The default hash key for CMap is a DWORD, so unless you override CMap's HashKey function, the hash key cannot be more than four bytes. Microsoft Knowledge Base article Q158541 ("PRB: C2440 Error When Using CMap and User Defined Key Type") provides a sample of CMap with a HashKey override to allow use of a user-defined class for a key.

Explanation

For those unfamiliar with "hash" keys and tables in the context of collections and databases, if you were to look up "hash" in the dictionary you might find it defined as being an act of making a mess of something. In the context of collections and databases a hash is roughly a messed up version of the key, but the algorithm for generating a hash value for a key is highly specific and is intended to make the lookup more efficient. Most algorithms do not guarantee that there will always be a one-to-one correspondence of hash value to key value, but lookup algorithms that use hash values will do additional searches when required for a hash. The idea is that a hash value can narrow the search to a few possibilities. For example, if a filing cabinet shelf were to hold only a few items, then finding an item using a hash key would only require a calculation using the key of the item to find and then the result of that calculation would be the shelf number to look in. Depending on the algorithms, though, there might be an additional table that maps hash key values to shelf numbers, but the idea is that searching that table is more efficient than searching shelves.

Obviously other search algorithms are often more efficient, but hash key searches have advantages.

Sample

The following is a modified version of the class shown in the KB article referenced above.

class CStringObject : public CObject {
public:
	CString m_String;

public:
	CStringObject() {};
	CStringObject(LPCSTR String) : m_String(String) {};

// Copy constructor required by CMap.
CStringObject(const CStringObject& n) {
	m_String = n.m_String;
	}

// Operator= is required by CMap.
CStringObject& operator=(const CStringObject& n) {
	m_String = n.m_String;
	return *this;
	}

BOOL AFXAPI operator==(const CStringObject& n) const {
	return m_String == n.m_String;
	}
};

template<>inline UINT AFXAPI HashKey(CStringObject& key) {
return HashKey((LPCTSTR)key.m_String);
}

typedef CMap<CStringObject, CStringObject&, CStringObject, CStringObject&> CStringMap;

The following is a sample use of the CStringMap class.

	CStringObject KeyString, DataString, One("One"), Two("Two");
	CStringMap StringMap;
	POSITION Position;
StringMap[One] = CStringObject("First");
StringMap[Two] = CStringObject("Second");
Position = StringMap.GetStartPosition();
while (Position!=NULL) {
	StringMap.GetNextAssoc(Position, KeyString, DataString);
	cout << (LPCSTR)KeyString.m_String << ' ' << (LPCSTR)DataString.m_String << '\n';
	}
cout << (LPCSTR)StringMap[One].m_String << '\n';
StringMap.RemoveAll();

See my Visual C++ Programmer Stuff page for more C++ stuff.