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)

Solution 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.

Solution 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;
 }

Solution 3

Even though there has been a couple of good answers already I thought I might as well do a quick benchmark. Ran each one 5 million times and used c++11's chrono to measure the time it took.

Heres the code:

#include <string>
#include <map>
#include <chrono>
#include <cstdio>

// 5 million
#define times 5000000

int main()
{
    std::map<std::string, int> foo1, foo2, foo3, foo4, foo5;
    std::chrono::steady_clock::time_point timeStart, timeEnd;
    int x = 0;

    // 1) Assignment using array index notation
    timeStart = std::chrono::steady_clock::now();
    for (x = 0; x <= times; x++)
    {
        foo1[std::to_string(x)] = 12345;
    }
    timeEnd = std::chrono::steady_clock::now();
    printf("1) took %i milliseconds\n", (unsigned long long)std::chrono::duration_cast<std::chrono::milliseconds>(timeEnd-timeStart).count());

    // 2) Assignment using member function insert() and STL pair
    timeStart = std::chrono::steady_clock::now();
    for (x = 0; x <= times; x++)
    {
        foo2.insert(std::pair<std::string, int>(std::to_string(x), 12345));
    }
    timeEnd = std::chrono::steady_clock::now();
    printf("2) took %i milliseconds\n", (unsigned long long)std::chrono::duration_cast<std::chrono::milliseconds>(timeEnd-timeStart).count());

    // 3) Assignment using member function insert() and "value_type()"
    timeStart = std::chrono::steady_clock::now();
    for (x = 0; x <= times; x++)
    {
        foo3.insert(std::map<std::string, int>::value_type(std::to_string(x), 12345));
    }
    timeEnd = std::chrono::steady_clock::now();
    printf("3) took %i milliseconds\n", (unsigned long long)std::chrono::duration_cast<std::chrono::milliseconds>(timeEnd-timeStart).count());

    // 4) Assignment using member function insert() and "make_pair()"
    timeStart = std::chrono::steady_clock::now();
    for (x = 0; x <= times; x++)
    {
        foo4.insert(std::make_pair(std::to_string(x), 12345));
    }
    timeEnd = std::chrono::steady_clock::now();
    printf("4) took %i milliseconds\n", (unsigned long long)std::chrono::duration_cast<std::chrono::milliseconds>(timeEnd-timeStart).count());

    // 5) Matthieu M.'s suggestion of C++11's emplace
    timeStart = std::chrono::steady_clock::now();
    for (x = 0; x <= times; x++)
    {
        foo5.emplace(std::to_string(x), 12345);
    }
    timeEnd = std::chrono::steady_clock::now();
    printf("5) took %i milliseconds\n", (unsigned long long)std::chrono::duration_cast<std::chrono::milliseconds>(timeEnd-timeStart).count());

    return 0;
}

The output for 5 million iterations is:

1) took 23448 milliseconds
2) took 22854 milliseconds
3) took 22372 milliseconds
4) took 22988 milliseconds
5) took 21356 milliseconds

GCC version:

g++ (Built by MinGW-builds project) 4.8.0 20121225 (experimental)

My machine:

Intel i5-3570k overclocked at 4.6 GHz

EDIT1: Fixed the code and redid the benchmark.

EDIT2: Added Matthieu M.'s suggestion for C++11's emplace and he is right, emplace is fastest

Solution 4

Your first possibility: Foo["Bar"] = 12345; has somewhat different semantics than the others -- it'll insert a new object if none exists (like the others) but overwrite the current contents if none exists (where the others using insert will fail if that key is already present).

As far as speed goes, it has the potential to be slower than the others. When you're inserting a new object, it has create a pair with the specified key and a default-constructed value_type, then assign the correct value_type afterwards. The others all construct the pair the correct key and value and insert that object. Being fair, however, my experience is that the difference is rarely significant (with older compilers, it was more significant, but with newer ones pretty minimal).

The next two are equivalent to each other. You're just using two different ways to name the same type. By run-time, there's no difference between them at all.

The fourth uses a template function (make_pair) that theoretically could involve an extra level of function call. I'd be quite surprised to see a real difference from this though, except (possibly) if you were careful to ensure that the compiler did absolutely no optimization (especially inlining) at all.

Bottom line: The first will often be a little slower than the rest (but not always and not by much). The other three will almost always be equal (as in: normally expect any reasonable compiler to produce identical code for all three) even though there's theoretical justification for the fourth being slower.

View more solutions

Comments

[Matthieu M.]

How is 3) faster than 2) ?

[PaperBirdMaster]

They're equivalent (as said in other answers) I've only focused on wich one is the best... so i guess that I've missed this point on my answer.

[inquam]

I'm well aware of the fact that []will replace any existing value. The same holds true for this notation on most data structures. So I was thinking a clean map and just inserting a single value. But since the others actually do keep track of whether or not an old value exists I would guess that there must be some additional code generated for that purpose. Thus making them different from [].

[Matthieu M.]

@inquam: [] is prone to be a little slower because it involves building an empty value and immediately discarding it... however this is only a problem if building the empty value is slow in the first place (obviously).

[GManNickG]

@inquam: A typical implementation for insert will: 1) use internal find functions to get the tree node, if any 2) if it exists, return that else 3) use the result of the find to insert the new value and return that. An implementation for operator[] will do the exact same thing except 3) inserts a default constructed value and returns that. (You then overwrite whatever was returned.)

[Grizzly]

std::map<std::string, int>::value_type is std::pair<const std::string, int>, not std::pair<std::string, int>. Therefore only 3) has a type which can be directly inserted without an additional type conversion (or the overhead of []). This overhead might be removed by the compiler, but in general I wouldn't count on it.

[Grizzly]

2,3,4 could be equal, provided a good optimizer. However in the non optimized case 3) should be the fastest, since 2) and 4) both incur an additional type conversion to std::pair<const std::string, int>.

[Matthieu M.]

Neat... but wrong. Note that the insert versions here will never actually insert, whereas the [] version always assign. So this is screwed to begin with...

[Matthieu M.]

@Grizzly: if we go this road, emplace is even better -> in-place construction only when necessary.

[Edward A]

@Matthieu M. Changed the code a bit to insert at different point each time, is this any better?

[Grizzly]

@MatthieuM.: That is of course always the preferable options, but that wasn't one of the options given in the question ;). Besides at least gcc doesn't have a working emplace for associative containers yet, so it might not be an option.

[Grizzly]

I think the code still has two problems: 1) You should probably clear the map between the loops, since the way it is now only the first loop will actually insert anything 2) creating a stringstream is pretty expensive, so this might influence the measurements. std::to_string might be a less impact option (I'm not entirely sure if that has an impact considering the final mapsize, but better be sure).

[Edward A]

@Grizzly Modified it to reflect your suggestions and redid the test.

[David Rodríguez - dribeas]

@Grizzly: It does not really matter whether 3 has a type that exactly matches the type stored in the map, but rather what the cost of insertion is, and that is mentioned in the answer. As a matter of fact the lack of conversion might actually be counter productive, as you can move out of a non-const std::string, but I am not sure whether you are allowed to move out of a const std::string, and that could imply that 3) might have a higher cost in a C++11 compiler.

[Josh Albert]

I'm not sure I trust this method of testing. I get that 2) is fastest with 9946 ms and 5) longest with 14557 ms. 1,3,4) are all about 10000 ms, same as 2).

[Manohar Reddy Poreddy]

Should there be ! before mymap.key_comp()(key, hint->first) ?

[Anders Johansson]

@ManoharReddyPoreddy no; mymap.key_comp()(key, hint->first) checks whether key is less than hint->first. If true, that means key was not present (since lower_bound returns an iterator to the first element not less). false would mean that key is identical to hint->first.

[Manohar Reddy Poreddy]

It's bit confusing. lower_bound can give >=, not < does not imply == or !=, so, wouldn't you require mymap.key_comp()(key, hint->first) && mymap.key_comp()(hint->first, key) or similar?

[Anders Johansson]

I agree it's confusing at first. Like you say, lower_bound returns an iterator to an existing element that is either equal to or larger than the supplied key meaning hint->first < key would always be false; there's no need to check this. Instead, just checking key < hint->first allows us to confirm if the returned iterator is equal ((key < hint->first) == false) or larger ((key < hint->first) == true), i.e. whether key already exists in the map or not. This covers all cases.

[Manohar Reddy Poreddy]

Actually I lost context in last few days since I am working on other things. I quickly checked, none of the top 5 links have used it as a value to compare, but as a range in while cplusplus.com/reference/map/map/key_comp tutorialspoint.com/cpp_standard_library/… , I am not saying you wrong, but I can't see what you are saying clearly.

[Raffaello]

the problem of this testing is the CPU caching too. the latest would be "always" perform slightly better than the first one. you should run those in different processes to benchmark better.