Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

c++

map

stl

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.

like image 236
puccio Avatar asked Sep 11 '09 07:09

puccio


People also ask

How does map Find () work?

map find() function in C++ STL Return Value: The function returns an iterator or a constant iterator which refers to the position where the key is present in the map. If the key is not present in the map container, it returns an iterator or a constant iterator which refers to map.

Which method do you use to add an element to a map?

set() The set() method adds or updates an entry in a Map object with a specified key and a value.

How do you add a string to a map?

To insert the data in the map insert() function in the map is used. It is used to insert elements with a particular key in the map container. Parameters: It accepts a pair that consists of a key and element which is to be inserted into the map container but it only inserts the unique key.

How do I add a map to CPP?

The standard solution to insert new elements into a map is using the std::map::insert function. It inserts the specified key-value pair into the map only if the key already doesn't exist. If the key already exists in the map, the element is not inserted.


2 Answers

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.

like image 166
Jonathan Graehl Avatar answered Oct 01 '22 11:10

Jonathan Graehl


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.

like image 38
CB Bailey Avatar answered Oct 01 '22 12:10

CB Bailey