c++ map find() to possibly insert(): how to optimize operations?

Question

Hi,

I'm using the STL map data structure, and at the moment my code first invokes find(): if the key was not previously in the map, it calls insert() it, otherwise it does nothing.

map<Foo*, string>::iterator it;
it = my_map.find(foo_obj);   // 1st lookup

if(it == my_map.end()){
  my_map[foo_obj] = "some value";  // 2nd lookup
}else{
  // ok do nothing.
}

I was wondering if there is a better way than this, because as far as I can tell, in this case when I want to insert a key that is not present yet, I perform 2 lookups in the map data structures: one for find(), one in the insert() (which corresponds to the operator[] ).

Thanks in advance for any suggestion.

Answer 1

Normally if you do a find and maybe an insert, then you want to keep (and retrieve) the old value if it already existed. If you just want to overwrite any old value, map[foo_obj]="some value" will do that.

Here's how you get the old value, or insert a new one if it didn't exist, with one map lookup:

typedef std::map<Foo*,std::string> M;
typedef M::iterator I;
std::pair<I,bool> const& r=my_map.insert(M::value_type(foo_obj,"some value"));
if (r.second) { 
    // value was inserted; now my_map[foo_obj]="some value"
} else {
    // value wasn't inserted because my_map[foo_obj] already existed.
    // note: the old value is available through r.first->second
    // and may not be "some value"
}
// in any case, r.first->second holds the current value of my_map[foo_obj]

This is a common enough idiom that you may want to use a helper function:

template <class M,class Key>
typename M::mapped_type &
get_else_update(M &m,Key const& k,typename M::mapped_type const& v) {
    return m.insert(typename M::value_type(k,v)).first->second;
}

get_else_update(my_map,foo_obj,"some value");

If you have an expensive computation for v you want to skip if it already exists (e.g. memoization), you can generalize that too:

template <class M,class Key,class F>
typename M::mapped_type &
get_else_compute(M &m,Key const& k,F f) {
   typedef typename M::mapped_type V;
   std::pair<typename M::iterator,bool> r=m.insert(typename M::value_type(k,V()));
   V &v=r.first->second;
   if (r.second)
      f(v);
   return v;
}

where e.g.

struct F {
  void operator()(std::string &val) const 
  { val=std::string("some value")+" that is expensive to compute"; }
};
get_else_compute(my_map,foo_obj,F());

If the mapped type isn't default constructible, then make F provide a default value, or add another argument to get_else_compute.

Answer 2

There are two main approaches. The first is to use the insert function that takes a value type and which returns an iterator and a bool which indicate if an insertion took place and returns an iterator to either the existing element with the same key or the newly inserted element.

map<Foo*, string>::iterator it;
it = my_map.find(foo_obj);   // 1st lookup

my_map.insert( map<Foo*, string>::value_type(foo_obj, "some_value") );

The advantage of this is that it is simple. The major disadvantage is that you always construct a new value for the second parameter whether or not an insertion is required. In the case of a string this probably doesn't matter. If your value is expensive to construct this may be more wasteful than necessary.

A way round this is to use the 'hint' version of insert.

std::pair< map<foo*, string>::iterator, map<foo*, string>::iterator >
    range = my_map.equal_range(foo_obj);

if (range.first == range.second)
{
    if (range.first != my_map.begin())
        --range.first;

    my_map.insert(range.first, map<Foo*, string>::value_type(foo_obj, "some_value") );
}

The insertiong is guaranteed to be in amortized constant time only if the element is inserted immediately after the supplied iterator, hence the --, if possible.

Edit

If this need to -- seems odd, then it is. There is an open defect (233) in the standard that hightlights this issue although the description of the issue as it applies to map is clearer in the duplicate issue 246.