I tested the performance of SortMap vs. HashMap vs. std::unordered_map. I found (as expected) that SortMap performance, which uses a sorted array, is comparable to hash-maps for small lists (< 50 items or so).

A secondary, though also important, result is that all three methods perform at the million-calls per second range.

Results

36 items, 20 million lookups:

SortMap:              625 ms
HashMap:              609 ms
std::unordered_map:   734 ms

120 items, 20 million lookups:

SortMap:            1,046 ms
HashMap:              610 ms
std::unordered_map:   656 ms

1,000 items, 20 million lookups:

SortMap:            1,344 ms
HashMap:              672 ms
std::unordered_map:   812 ms

Code

#include <unordered_map>
#include <string>
#include "Foundation.h"

int main (int argc, char* argv[])
	{
	int i;

	TArray<CString> Ports;
	Ports.Insert(CString("Aeon.command"));
	Ports.Insert(CString("Anacreon.command"));
	Ports.Insert(CString("Celestial.command"));
	Ports.Insert(CString("DrHouse.command"));
	Ports.Insert(CString("Esper.command"));
	Ports.Insert(CString("Exarch.command"));
	Ports.Insert(CString("Hexe.command"));
	Ports.Insert(CString("Hyperion.command"));
	Ports.Insert(CString("Trans.command"));

	for (i = 0; i < 241; i++)
		Ports.Insert(strPattern("%c%c%c %c%c%c %c%c%c", 
				mathRandom('A', 'Z'), mathRandom('a', 'z'), mathRandom('a', 'z'), 
				mathRandom('A', 'Z'), mathRandom('a', 'z'), mathRandom('a', 'z'), 
				mathRandom('A', 'Z'), mathRandom('a', 'z'), mathRandom('a', 'z')));

	TArray<CString> Addresses;
	for (i = 0; i < Ports.GetCount(); i++)
		{
		CString sModule = ((i % 2) == 0 ? CString("CentralModule") : CString("AeonDb"));
		CString sMachine = (((i / 4) % 2) == 0 ? CString("Morgaine-1238ef") : CString("Seldon-94fe6a"));

		Addresses.Insert(Ports[i]);
		Addresses.Insert(strPattern("%[email protected]~/~", Ports[i]));
		Addresses.Insert(strPattern("%[email protected]~/%s", Ports[i], sModule));
		Addresses.Insert(strPattern("%[email protected]%s/%s", Ports[i], sMachine, sModule));
		}

	//	SortMap

	TSortMap<CString, void *> SortMap;
	for (i = 0; i < Addresses.GetCount(); i++)
		SortMap.Insert(Addresses[i], NULL);

	//	HashMap

	THashMap<CString, void *> HashMap(4096);
	for (i = 0; i < Addresses.GetCount(); i++)
		HashMap.Insert(Addresses[i], NULL);

	//	std::map

	std::unordered_map<std::string, void *> StdMap;
	for (i = 0; i < Addresses.GetCount(); i++)
		StdMap.insert(std::pair<std::string, void*>(std::string((LPSTR)Addresses[i]), NULL));

	CString sT1 = CString("this is a test that will not be found");
	CString sT2 = CString("Trans.command");
	std::string stdT1 = std::string((LPSTR)sT1);
	std::string stdT2 = std::string((LPSTR)sT2);

	//	SortMap timings

	const int iLoops = 10000000;
	DWORD dwStart = ::GetTickCount();
	for (i = 0; i < iLoops; i++)
		{
		void **pFound = SortMap.GetAt(sT1);
		if (pFound == NULL)
			pFound = SortMap.GetAt(sT2);
		if (pFound == NULL)
			printf("SortMap: Not found\n");
		}
	DWORD dwTime = ::GetTickCount() - dwStart;
	printf("SortMap: %d ms\n", dwTime);

	//	HashMap timings

	dwStart = ::GetTickCount();
	for (i = 0; i < iLoops; i++)
		{
		void **pFound = HashMap.GetAt(sT1);
		if (pFound == NULL)
			pFound = HashMap.GetAt(sT2);
		if (pFound == NULL)
			printf("HashMap: Not found\n");
		}
	dwTime = ::GetTickCount() - dwStart;
	printf("HashMap: %d ms\n", dwTime);

	//	std::map timings

	dwStart = ::GetTickCount();
	for (i = 0; i < iLoops; i++)
		{
		std::unordered_map<std::string, void *>::const_iterator found = StdMap.find(stdT1);
		if (found == StdMap.end())
			found = StdMap.find(stdT2);
		if (found == StdMap.end())
			printf("StdMap: Not found\n");
		}
	dwTime = ::GetTickCount() - dwStart;
	printf("StdMap: %d ms\n", dwTime);

	return 0;
	}