SimpleLib

Associative Map Classes

CMap, CIndex and CHashMap provide three different implementations of an associative map. The syntax of these classes is identical and can be easily interchanged. The follow examples use CMap, though the examples equally apply to CIndex and CHashMap.

Special thanks to Nick Maher of GrofSoft for the original red-black tree and hash map implementations used in these classes.

CMap

CMap implements a red-black binary tree associative map, enhanced with a double-linked list between all elements for fast iteration. It also supports pseudo random access allowing easy but fast iteration and inserting and deleting while iterating.

Features of this class include:

  • Reasonably fast insertion
  • Reasonably fast iteration
  • Medium memory overhead for each key/value pair.
  • Pseudo random access

CIndex

CIndex implements an associative map using two vectors - one for the keys and one for the values. Features of this class include:

  • Reasonably fast insert/deletion, though possibly slow with large data sets
  • Very low memory overhead
  • Very fast iteration
  • If you're already using CVector in other parts of your code, using CIndex is less likely to generate additional code as it re-uses the CVector implementation.
  • CIndex provides true random access.

CHashMap

CHashMap implements an associative map using a hash table. It also maintains a double-linked list between all nodes for fast iteration even when sparsely populated. It rehashes when reaching about 70% density. Features include:

  • Extremely fast insertion and deletion.
  • Medium memory overhead per node, high memory overhead when using large sparsly populated hash tables.
  • CHashMap doesn't provide sorted enumeration. Enumeration is in random order.
  • Pseudo random access.

Compared to CIndex and CMap, CHashMap has additional template parameter that can be used to control the hashing algorithm. By default keys are hashed using SuperFastHash.cpp by Paul Hsieh though custom hash routines can be used by implementing a class similar the the SHash classes in SimpleLib.

Examples

// CMap
template <class TKey, class TValue, class TKeySem=SValue, class TValueSem=SValue, class TKeyArg>
class CMap;

// CIndex
template <class TKey, class TValue, class TKeySem=SValue, class TValueSem=SValue, class TKeyArg>
class CIndex;

The first template parameter TKey defines the type of the map's keys.

The second template parameter TValue defines the type of the map's values.

The third and forth parameters TKeySem and TValueSem define the semantic behaviour of the map's keys and values respectively. See Collection Semantic Classes for more.

The final parameter TKeyArg allows use of a different parameter type for key arguments than the type used for key storage. This is typically used with string keys where TKey is declared a string class (eg: CUniString). By declaring TKeyArg as as const wchar_t* a significant performance advantage can be made as it saves allocation of the string buffer in the string class just to do a look up. For optimum performance with string keys declare the class as follows:

CMap<CUniString, int, SValue, SValue, const wchar_t*> mapStringToInts;

Some example map declarations:

// map of ints to int
CMap<int, int> mapInts;		

// map of ints to object
CMap<int, CMyObject> mapObjects;		

// map of ints to object ptrs
CMap<CMyObject*> mapPtrObjects;

// a map of ints to pointers where pointers deleted on removal
CMap<int, CMyObject*, SValue, SOwnedPtr> mapPtrObjects;	

// a map of strings to integers, with case insensitivity on the keys
CMap< CString<char>, int, SCaseInsensitive> mapStrings;

Adding items to a map or index:

mapInts.Add(10, 20);
mapPtrObjects.Add(mapStrings.Add("Apples", 10);

Removing items:

mapStrings.Remove("Apples");

Detaching owned pointers::

CMyObject* pObject=mapPtrObjects.Detach(iKey);

Checking for existance of element:

if (mapStrings.HasKey("Apples"))
{
	// Already contains key
}

Retrieving the value of key can be done using the Find method:

int iValue;
if (mapStrings.Find("Apples", iValue))
{
	// Value found and returned in iValue
}

You can also use the Get method where the second parameter is the value to return if the map doesn't contain the key.

int iValue=mapStrings.Get("Apples", 0);

Iterating a map or index can be done using the GetSize method and the [] operator.

Note that although the following code looks inefficient for a map (as maps don't usually support random access), SimpleLib's map class supports pseudo random access where it intelligently seeks through the linked list to locate an item at a particular location. For normal iteration, this approach works faster than a normal binary tree implementation and effectively boils down to walking a linked list. CIndex supports true random access.

// Print contents of map
for (int i=0; i<mapStrings.GetSize(); i++)
{
	printf("%s=%i\n", mapStrings[i].Key, mapStrings[i].Value);
}

Both CMap and CIndex support insertion and deletion while enumerating:

for (int i=0; i<mapStrings.GetSize(); i++)
{
	if (ShouldDeleteThisItem(mapStrings[i].Key))
	{
		 mapStrings.RemoveAt(mapStrings[i].Key);
		 i--
	}
}

Subscribe for more like this. No spam, just fun tech stuff :)

Or, find me on Twitter: @toptensoftware.