Sunday, March 9, 2008

Associative Container - MAP

http://www.cprogramming.com/tutorial/stl/stlmap.html

STL Maps -- Associative Arrays
Suppose that you're working with some data that has values associated with strings -- for instance, you might have student usernames and you want to assign them grades. How would you go about storing this in C++? One option would be to write your own hash table. This will require writing a hash function and handling collisions, and lots of testing to make sure you got it right. On the other hand, the standard template library (STL) includes a templated class to handle just this sort of situation: the STL map class, which conceptually you can think of as an "associative array" -- key names are associated with particular values (e.g., you might use a student name as a key, and the student's grade as the data).

In fact, the STL's map class allows you to store data by any type of key instead of simply by a numerical key, the way you must access an array or vector. So instead of having to compute a hash function and then access an array, you can just let the map class do it for you.

To use the map class, you will need to include and maps are part of the std namespace. Maps require two, and possibly three, types for the template:

std::map

Notice that the comparison function is in brackets, indicating that it is optional so long as your key_type has the less-than operator, <, defined -- so you don't need to specify a comparision function for so-called primitive types such as int, char, or even for the string class. Moreover, if you overloaded the < char=""> grade_list;

Now, to actually store or access data in the map, all you need to do is treat it like a normal array and use brackets. The only difference is that you no longer use integers for the index -- you use whatever data type was used for the key.

For instance, following the previous example, if we wanted to assign a grade of 'B' to a student named "John", we could do the following:

grade_list["John"] = 'B';

If we later decided that John's grades had improved, we could change his grade in the same fashion:

grade_list["John"] = 'B';
// John's grade improves
grade_list["John"] = 'A';

So adding keys to a map can be done without doing anything special -- we just need to use the key and it will be added automatically along with the corresponding data item. On the other hand, getting rid of an element requires calling the function erase, which is a member of the map class:

erase(key_type key_value);

For instance, to erase "John" from our map, we could do the following:

grade_list.erase("John");

If we're curious, we could also check to see how many values the map contains by using the size function, which is also a member of the map class and other containers:

int size();

For instance, to find the size of our hypothetical class, we could call the size function on the grade list:

std::cout<<"The class is size "<< grade_list;
grade_list["John"] = 'A';
if(grade_list.find("Tim") == grade_list.end())
{
std::cout<<"Tim is not in the map!"<::iterator iterator_name;

where parameters are the parameters used for the container class this iterator will be used for. This iterator can be used to iterate in sequence over the keys in the container. Ah, you ask, but how do I know the key stored in the container? Or, even better, what exactly does it mean to dereference an iterator over the map container? The answer is that when you dereference an iterator over the map class, you get a "pair", which essentially has two members, first and second. First corresponds to the key, second to the value. Note that because an iterator is treated like a pointer, to access the member variables, you need to use the arrow operator, ->, to "dereference" the iterator.

For instance, the following sample shows the use of an iterator (pointing to the beginning of a map) to access the key and value.

std::map grade_list;
grade_list["John"] = 'A';
// Should be John
std::cout<first<<second<

Finally, you might wonder what the cost of using a map is. One issue to keep in mind is that insertion of a new key (and associated value) in a map, or lookup of the data associated with a key in a map, can take up to O(log(n)) time, where n is the size of the current map. This is potentially a bit slower than some hash tables with a good hashing function, and is due to the fact that the map keys are stored in sorted order for use by iterators.

Summary

The Good

* Maps provide a way of using "associative arrays" that allow you to store data indexed by keys of any type you desire, instead of just integers as with arrays.
* Maps can be accessed using iterators that are essentially pointers to templated objects of base type pair, which has two members, first and second. First corresponds to the key, second to the value associated with the key.
* Maps are fast, guaranteeing O(log(n)) insertion and lookup time.

The Gotchas

* Checking for whether an element is in a map requires using the find function and comparing the returned iterator with the iterator associated with the end of the map.
* Since maps associate a key with only one value, you need to use a multimap (or make the type of the data a container) if you must associate multiple pieces of data with one key.
Posted by at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)