When I went to run this code and iterated through my map I noticed that the value associated with key "MyKey" was actually "MyValue1"!!! What the heck is going on? Well, the insert() routine is a little tricky here (evil if you ask me). If you are inserting a new item into the map, everything works fine. If you are attempting to overwrite an existing item, it sees that it is there and doesn't update it. Nice... So, I tried the use of operator[] to update my map and this worked. Here's what the second iteration (no pun intended) of the code looked like:

typedef std::map<std::wstring, std::wstring> MyMap;
typedef std::pair<std::wstring, std::wstring> MyMapEntry;

// Insert a value with key "MyKey".
MyMap theMap;
theMap[L"MyKey"] = L"MyValue1";

// Update the value associated with key "MyKey."
theMap[L"MyKey"] = L"MyValue2";

So, now that it is working I should just let it go right? Wrong. I remembered a Scott Meyer's article awhile back where he mentioned how each of the mechanisms for inserting/updating items in a map can affect efficiency based on how you use them. Here's the basic gist of things:

• insert should only be used to insert new items into a map.
• operator[] should only be used to update existing items.

But this is obviously a royal pain because how do you know if an item is already in a map without searching for it first? It can't be more efficient to search for an item first and then decide how to insert/update it? This is where lower_bound comes into play. This routine will return an iterator to the first element in a container with a key that is equal to or greater than a given key. Once you get an iterator to that point in the map you can determine if the key really exists by invoking key_comp. If the key matches, you know you've found your existing item and you can update it. If the key doesn't match you now have an iterator to where that item SHOULD be inserted into the map. So this "search" operation is not wasted after all. You can use this location "hint" to insert your new item into the map. Meyers also mentioned that insert will run in amortized constant-time because of the hint. So here's how you would write the earlier example given what we know now:

typedef std::map<std::wstring, std::wstring> MyMap;
typedef std::pair<std::wstring, std::wstring> MyMapEntry;

// Insert a value with key "MyKey".
MyMap theMap;
theMap.insert(MyMapEntry(L"MyKey", L"MyValue1"));

// Assume you don't know whether an item has already been inserted
// after this point *grin*
MyMap::iterator iter = theMap.lower_bound(L"MyKey");
if ((theMap.end() != iter) && 
     !(theMap.key_comp()(L"MyKey", iter->first)))
{
    iter->second = L"MyValue2";
}
else
{
    theMap.insert(iter, MyMapEntry(L"MyKey", L"MyValue2"));
}

Now the example above is pretty simple but when you have code that performs a number of insertions in numerous locations, it is easy to not know whether an item exists in a map. You could write a template function as well (which is what I did). Until next time...

- Gilemonster