Most efficient way to assign values to maps

Question

Which way to assign values to a map is most efficient? Or are they all optimized to the same code (on most modern compilers)?

   // 1) Assignment using array index notation
   Foo["Bar"] = 12345;

   // 2) Assignment using member function insert() and STL pair
   Foo.insert(std::pair<string,int>("Bar", 12345));

   // 3) Assignment using member function insert() and "value_type()"
   Foo.insert(map<string,int>::value_type("Bar", 12345));

   // 4) Assignment using member function insert() and "make_pair()"
   Foo.insert(std::make_pair("Bar", 12345));

(I know I could benchmark and check compiler output, but this question arose now and the only thing I have close at hand is my mobile phone... hehe)

Answer 1

First, there are semantic differences between [] and insert:

• [] will replace the old value (if any)
• insert will ignore the new value (if an old value is already present)

therefore comparing the two is useless in general.

Regarding the inserts versions:

• std::map<std::string, int>::value_type is std::pair<std::string const, int> so no (important) difference between 3 and 4
• std::make_pair("Bar", 12345) is cheaper than std::pair<std::string, int>("Bar", 12345) because the std::string type is a full fledged class with operations to do on copy and "Bar" is just a string literal (thus just a pointer copy); however since at the end you do need to create the std::string... it will depend on the quality of your compiler

In general, I would recommend:

• [] for updating
• insert(std::make_pair()) for ignoring duplicates

std::make_pair is not only shorter, it also respects the DRY guideline: Don't Repeat Yourself.

---

For completeness though, the fastest (and easiest) would be emplace (C++11 enabled):

map.emplace("Bar", 12345);

Its behavior is that of insert, but it constructs the new element in-place.

Answer 2

1) may be slightly slower than the other methods because std::map::operator[] first default-creates the object if it doesn't already exist, then returns a reference that you can use operator= on to set your desired value, i.e. two operations.

2-4) should be equivalent since map::value_type is a typedef to std::pair for the same types, and therefore make_pair is also equivalent. The compiler should treat these identically.

Also note that performance can be increased further if you need to both check for existence (e.g. to perform special logic depending on whether it exists or not) and then also insert it, by using map::lower_bound to first get a hint to where the element should be, so map::insert does not have to search the whole map again:

 // get the iterator to where the key *should* be if it existed:
 std::map::iterator hint = mymap.lower_bound(key);

 if (hint == mymap.end() || mymap.key_comp()(key, hint->first)) {
     // key didn't exist in map
     // special logic A here...

     // insert at the correct location
     mymap.insert(hint, make_pair(key, new_value));
 } else { 
     // key exists in map already
     // special logic B here...

     // just update value
     hint->second = new_value;
 }