|
|
A map is a collection that associates arbritrary key value pairs. This differs significantly from the most of other collection classes, which use positioning, or just existence to store elements. Maps store values assicated with a key value, which can then be retreived using the key. Thus maps are an ordered (sorted), associative collection. As key-value pairs are inserted into the map, they are kept in a sorted order. Key collisions (a key collision occurs when an attempt is made to insert a key-value pair into a map when the key already exists in the map) are resolved by re-setting the value for the existing pair (thus invoking T::operator==()). The use of c_map_pair is enforced so c_map can conform to the c_collection interface for add(), and other member functions that take a singular value. It also provides a convinient methodology for traversal and value extraction. Maps can be traversed in order, or in reverse order. Because the sorting is performed during the insertion process, ordered traversal is very fast. Value retreival by key is much more efficient than with the non-associative collection object, as the map is implemented as a binary tree, so a significantly smaller portion of the key set must be searched on average. A few things should be kept in mind when using maps, if your data is already sorted, the map will be extrememly inefficient in both insertion, and key traversal. You will obtain much better performance if your data set is at least marginaly randomized. |
|
|
void make_me_a_match( void ) { c_map<c_string,c_string> mr_matchmaker; mr_matchmaker.add( c_string("Bob"), c_string("Jane") ); mr_matchmaker.add( c_string("Joe"), c_string("Joan") ); mr_matchmaker.add( c_string("Don"), c_string("Bess") ); mr_matchmaker.add( c_string("Dan"), c_string("Niki") ); mr_matchmaker.add( c_string("Sue"), c_string("Bill") ); c_map_pair<c_string,c_string> match; match.m_key = "Joe"; if( mr_matchmaker.find(match) ) { cout << match.m_key "'s match is: " << pair.m_value << endl; } else { cout << match.m_key << " has no match, bummer!" << endl; } } |