Posts Tagged ‘STL map’

Boss around map insertions

Posted: June 13, 2011 in Optimization Pills
Tags: ,

This pill deals with maps, [from the reference] kind of associative container that stores elements formed by the combination of a key value and a mapped value.

In a map , the key value is generally used to uniquely identify the element, while the mapped value is some sort of value associated to this key. Types of key and mapped value may differ. For example, a typical example of a map is a telephone guide where the name is the key and the telephone number is the mapped value.

Internally, the elements in the map are sorted from lower to higher key value following a specific strict weak ordering criterion set on construction.

As associative containers, they are especially designed to be efficient accessing its elements by their key (unlike sequence containers, which are more efficient accessing elements by their relative or absolute position).

We could spend hours on end talking about maps, but this time we are interested in one of the simplest operation: insertion. Particularly, you said me you’re confused by the existence of at least two ways to insert new elements in a map: the subscript operator [] and the method insert.

The good news is they both perform a proper insertion, the bad news is that you should choose carefully among them when efficiency is important.

Part of this discussion is inspired by Meyers’ Effective STL (item 24).

Let’s suppose we have a map <K, V> myMap. What about this expression?


myMap[k] = v;

It checks to see if k is already in the map. If not, it’s added, along with v as its corresponding value. If k is already in the map, its associated value s updated to v. Then, first the method returns a reference to the value object associated with k, then it assigns v to the object to which the reference refers. Simple, but what if k is not in the map?

In this unlucky case, it creates a new value (and a new key too) from scratch by using the value type’s default constructor. We first default construct a new V, then we immediately assign it a new value. Now it should be clear why this approach may degrade performance.

We’d better off replacing our use of operator[] and assignment with a straightforward call to insert:

myMap.insert(std::map<K,V>::value_type(k,v));

This has precisely the same ultimate effect as the code above, except it typically saves you three function calls: one to create the temporary default-constructed V object, one to destruct that temporary, and one to V’s assignment operator. What if your V object is, for example, a complete 3D model (mesh, textures, materials, etc)?! Just say no to operator[] and save your clock and cache!

On the other hand, the call to insert requires an argument of type std::map<K,V>::value_type (for example, pair<K,V>), so when we call insert, we must construct and destruct an object of that type. This is not good when performances affect us during an update. But remember we can employ the subscript operator because it uses no pair object, so it does not cost us neither a pair destructor nor constructor.

Efficiency considerations thus lead us to conclude that insert is preferable to operator[] when adding an element to a map, and both efficiency and aesthetics dictate that operator[] is preferable when updating the value of an element that’s already in the map.

Meyers wrote a useful function providing the best of both worlds, something that sounds like efficient add-or-update:

template< typename MapType, // type of map
          typename KeyArgType, // type of Key
          typename ValueArgtype> // type of Value

typename MapType::iterator efficientAddOrUpdate(MapType& m,
                                                const KeyArgType& k,
                                                const ValueArgtype& v)
{
     typename MapType::iterator Ib = m.lower_bound(k); // find where k is or should be

     if ( Ib != m.end() && // if Ib points to a pair
          !(m.key_comp()(k, Ib->first))) { // whose key is equivalent to k...

          Ib->second = v; // update the pair's value        

          return Ib; // and return an iterator to that pair
     }
     else {
          typedef typename MapType::value_type MVT;

          return m.insert(Ib, MVT(k, v)); // add pair(k, v) to m and return an iterator
                                          // to the new map element

     }
}

The insert branch is interesting because it uses the “hint” form of insert. Ib identifies the correct insertion location for a new element with key equivalent to k, and the Standard guarantees that if the hint is corrent, the insertion will occur in constant, rather than logarithmic, time.

Don’t forget to perform an equivalence test (not equality) and remember that the correct comparison function is available via map::key_comp.

Keep in mind what happens behind the scenes of operator[] and insert. Choose your friend according to the context you’re facing with!