unordered map - Using The [] Operator Efficiently With C++ unordered_map

Question

Firstly could someone clarify whether in C++ the use of the [] operator in conjunction with an unordered_map for lookups wraps a call to the find() method, or is using the [] operator quicker than find()?

Secondly, in the following piece of code I suspect in cases where the key is not already in the unordered_map I am performing a second look up by way of the line map[key] = value in order to replace the default value created there by using the [] operator when a key is not present.

Is that true, and if so is there a way (perhaps by use of pointers or something) that I might only perform one look up in any case (perhaps by storing the address of where to place a value/read a value from) and still achieve the same functionality? Obviously this would be a useful efficiency improvement if so.

Here is the modified code excerpt:

    int stored_val = map[key]; // first look up. Does this wrap ->find()??

    // return the corresponding value if we find the key in the map - ie != 0
    if (stored_val) return stored_val;

    // if not in map
    map[key] = value; 
       /* second (unnecessary?) look up here to find position for newly 
          added key entry */

   return value;

question from:https://stackoverflow.com/questions/6897737/using-the-operator-efficiently-with-c-unordered-map

Answer 1

operator[] will insert an entry for you with a default-constructed value, if one isn't already there. It is equivalent to, but will probably be implemented more efficiently than:

iterator iter = map.find(key);

if(iter == map.end())
{
    iter = map.insert(value_type(key, int())).first;
}

return *iter;

operator[] can be quicker than doing the work manually with find() and insert(), because it can save having to re-hash the key.

One way you can work around having multiple lookups in your code is to take a reference to the value:

int &stored_val = map[key];

// return the corresponding value if we find the key in the map - ie != 0
if (stored_val) return stored_val;

// if not in map
stored_val = value;

return value;

Note that if the value doesn't exist in the map, operator[] will default-construct and insert one. So while this will avoid multiple lookups, it might actually be slower if used with a type that is slower to default-construct + assign than to copy- or move-construct.

With int though, which cheaply default-constructs to 0, you might be able to treat 0 as a magic number meaning empty. This looks like it might be the case in your example.

If you have no such magic number, you've got two options. What you should use depends on how expensive it is for you to compute the value.

First, when hashing the key is cheap but computing the value is expensive, find() may be the best option. This will hash twice but only compute the value when needed:

iterator iter = map.find(key);

// return the corresponding value if we find the key in the map
if(iter != map.end()) return *iter;

// if not in map
map.insert(value_type(key, value));

return value;

But if you've got the value already, you can do it very efficiently -- perhaps slighty more efficiently than using a reference + magic number as above:

pair<iterator,bool> iter = map.insert(value_type(key, value));
return *iter.first;

If the bool returned by map.insert(value_type) is true, the item was inserted. Otherwise, it already existed and no modifications were made. The iterator returned points to the inserted or existing value in the map. For your simple example, this may be the best option.