map and hash_map

The STL library provides a template type called map which allows a C++ programmer to create an associative array (i.e). array[key] = value;
However, a map template automatically orders its elements as they're inserted, therefore lookups are a little slower. A hash_map is a template type that allows a programmer to quickly look up a value. The hash_map template uses a hashing algorithm to store values that are inserted into it, hence the elements are NOT sorted. This is OK, if you just want to do quick in-memory lookups, but don't care about the data being sorted. The map type is part of the STL, but hash_map was introduced by SGI and is present in only some implementations of the STL (M$ VC++ 6.0 and .NET do not have it in their default installation). However, two of the well known implementations from SGI (http://www.sgi.com/tech/stl/index.html) and stlport (http://www.stlport.org/) do and can be used as drop in replacements, if your compiler does not support hash maps. See http://www.sgi.com/tech/stl/table_of_contents.html for documentation and sample code using hash_map .