A coder’s eye view of STL map
Associative containers provide efficient storage and retrieval mechanism for data based on keys. Most introductory STL tutorials scathe the surface of maps. Lot of map related innards are either misunderstood or overlooked by novice programmers.
The [] operator
The following piece of code stores the employee number-employee name relationship indexed by employee number in an STL map.
typedef map<long, string, less<long> > EmployeeTable;
EmployeeTable emp_table;
// add some values
Now, we want to do some operations with the data in the employee table. We add an add_employee() and a modify_employee() which take employee table as the function argument.
void operate_on_employee_table( int index, EmployeeTable& e) // <--(1)
{
// do something
string employee = e[index]; // <-- (2)
// use employee thus obtained
}
After several lines of coding and testing, the program seems to work fine in spite of inherent bugs, till the user gets spurious values added to the table and some employee names modified as well!
Let us dissect (2) first. The [] operator is a convenient feature of maps, provided it is used carefully. It comes as a surprise to many that the [] actually inserts an entry into the map if it does not exist, and overwrites the entry if it already exists.
Assuming we write like this:
emp_table[7200] = “Joe”;
it gets translated to this:
(*((emp_table.insert(value_type(7200, data_type()))).first)).second = “Joe”;
Now that involves some explanation. What happens here is emp_table uses 7200 and inserts it in the map and returns an iterator which points to that index. No wonder the [] operator is a const member function of the map. The common method used to avoid this mistake is to minimize the use of [] operator and go for alternatives.
An entry in emp_table should be fetched by using find.
typedef EmployeeTable::iterator EmpTableIter;
EmpTableIter iter;
Iter = emp_table.find(7100);
if(emp_table.end() == iter)
{
// not found
}
// an employee is present with ID 7100
cout<<(*Iter).second<<” has ID 7100.”;
Insertions should be done by insert only. It is a defensive coding practice to check what we have inserted also. Any call to a map’s insert will return a pair<iterator, bool>. The iterator points to the element inserted, and bool will be true or false depending on whether any existing entry will be overwritten or not.
emp_table.insert(pair<long, string> ( 7300, “Eddie”));
pair<EmployeeTable::iterator, bool> result = emp_table.insert(make_pair(7300, “Eric”));
// result.second will be false
the above line of code will do the job well.
Another safe practice would be to pass the emp_table as a const argument to any function(refer to (1) in the above code). This will produce any compile time error on accidental insertion. As Stroustrup put it, C makes it easy to shoot yourself in the foot. C++ makes it harder, but when you do, it blows away your whole leg.
Multimaps and operator[]
Multimap is a multiple associative container, meaning, there can be more than one value with the same key. A typical example would be a case where we have to store phone numbers. The multimap is indexed by name, where the same person can have more than one contact number.
struct cmp_fn {
bool operator()(const string& s1, const string& s2) const {
return (s1 < s2);
}
};
typedef multimap<string, long, cmp_fn> Directory;
Directory d;
d[“Fred”] = 234677; // wrong. Won’t compile
The last line would yield a compilation error because of the fact that an operator[] is not defined for multimaps. This might seem weird at first. Assuming that we do define a [] for multimaps and the above line validates, we now add a couple of more phone numbers to Mr. Fred here.
d[“Fred”] = 456678;
d[“Fred”] = 456679;
Now that [] can be used for lookup also, what would d[“Fred”] yield if we call it on the right hand side? Say,
long freds_no = d[“Fred”]; // which number would freds_no point to??
Searching in multimaps can be accomplished by using lower_bound() and upper_bound() calls. A lower_bound(k) returns an iterator to the first element in the multimap whose key is k. No prizes for guessing upper_bound(k) returns an iterator pointing to the last element with the same key!
Directory::iterator LB = d.lower_bound(“Fred”);
Directory::iterator UB = d.lower_bound(“Fred”);
If(LB == UB)
{
// only one entry for key “Fred”
}
else
{
for(Directory::iterator i = LB; i != UB; ++i)
{
// work with i
}
}
Another frequently used method is equal_range(). equal_range(k) returns a pair<iterator1, iterator2> where iterator1 and iterator2 point to the first and last elements whose key is k respectively.
pair<Directory::iterator, Directory::iterator> range = d.equal_range(“Fred”);
if(range.first == range.second)
// and the implementation follows like previous approach
operator[] is a handy convenience when at safe hands. It can cause untold misery if mishandled.
Attachments
Source Files Sample Code