C++ std::map

Maps are associative containers that store elements formed by a combination of a key value and a mapped value, following a specific order. map<Key, Value>
Properties of maps

1. Like Set, Map (ordered or unordered) does not allow duplicate Key
2. Ordered map is sorted by it's Key. It is sorted following a specific strict weak ordering criterion indicated by its internal comparison object std::map::key_comp. So a map of user defined class objects which have no meaning of comparison, will not be sorted.
3. Unordered map is not sorted by Key
4. map is generally slower than unordered_map to access individual elements by their key map[Key]. So if std::find is mostly what you will be doing, unordered_map is better choice.
5. unordered_map is generally less efficient for range iteration through a subset of it's elements than ordered map. So if iteration is mostly what you will be doing, then ordered map is a better choice.
6. Maps are typically implemented as binary search trees.
7. A unique feature of map among associative containers is that they implement the direct access operator (operator[]), which allows for direct access of the mapped value.

Proof of key uniqueness and sorting properties

cout << "Ordered Map" << endl;
cout << "===============================" << endl;
map<int, string> myMap;
myMap.insert(make_pair(33, "Hello"));
myMap.insert(make_pair(11, "Cello"));
myMap.insert(make_pair(11, "Vello"));
myMap.insert(make_pair(44, "Jello"));
myMap.insert(make_pair(22, "Fello"));

for(map<int, string>;::iterator iter = myMap.begin(); iter != myMap.end(); ++iter)
{
    cout << "<Key, Value> = <" << iter->;first << ", " << iter->;second << ">" << endl;
}

cout << endl;
cout << "Unordered Map" << endl;
cout << "===============================" << endl;
unordered_map<int, string> myUnorderedMap;
myUnorderedMap.insert(make_pair(33, "Hello"));
myUnorderedMap.insert(make_pair(11, "Cello"));
myUnorderedMap.insert(make_pair(11, "Vello"));
myUnorderedMap.insert(make_pair(44, "Jello"));
myUnorderedMap.insert(make_pair(22, "Fello"));

for(unordered_map<int, string>::iterator iter = myUnorderedMap.begin(); iter != myUnorderedMap.end(); ++iter)
{
    cout << "<Key, Value> = <" << iter->first << ", " << iter->second << ">" << endl;
}

Output

Ordered Map
===============================
<Key, Value> = <11, Cello>
<Key, Value> = <22, Fello>
<Key, Value> = <33, Hello>
<Key, Value> = <44, Jello>

Unordered Map
===============================
<Key, Value> = <33, Hello>
<Key, Value> = <11, Cello>
<Key, Value> = <44, Jello>
<Key, Value> = <22, Fello>

Find in a map by Key

if(myMap.find("f") != myMap.end()) 
{
    // Found
}
else 
{
    // Not found
}

Find in a map by Value
There are four options

1. Use boost::bimap if boost library is available
2. Create another map with Value as the Key and use map::find on it
3. Use std::find_if with a predicate/functor in which you define some equal to comparison logic
4. Iterate through the whole map to find the value

   for(map<int, string>::iterator iter = myMap.begin(); iter != myMap.end(); ++iter)
   {
       if(iter->second == "Hello")
       {
           // Found
           break;
       }
   }
   

Option 1 & 2 are equivalent. Runtime will be O(log n) for a map and O(1) for an unordered map. Option 2 you are essentially reinventing the boost:bimap. Option 3 & 4 are equivalent. Runtime in both cases is O(n). They both iterate the whole map entry-by-entry until a matching entry is found. Hence, if boost library is not available, go for option 2. Create two maps and implement functionality to keep them synchronized.

Free memory from a map of object pointers

• map or any STL container destroys it's elements while being destroyed itself. If the map had stored some objects, those objects will be destroyed. If it had stored pointers, those pointers will be destroyed, but not the actual objects pointed to by the pointers. So, you have to destroy those instances by yourself explicitly, iterate through std::map elements and call delete on contained pointer.
• std::map::clear() empties out the contents of the map, i.e. all contained pointers will be destroyed. It doesn't do anything with the objects pointed by them, in particular it doesn't delete them. All those objects will stay alive in memory.

Note: Raw pointers do not have ownership of the objects they point to. So when a pointer is destroyed, it will not delete whatever it points to. Generally speaking, when you have a pointer, there is no way to know if:

• It points to a valid object at all (you don't want to call delete on some random garbage in memory),
• The object it points to has been allocated with new (if it has been allocated in another way, it should not be deleted with delete), or
• If there are other pointers that also point to the same object (in which case only one of them should call delete. Which one?)

So even if you wanted to, there is no way to automatically delete an object when a pointer to it is destroyed.