AR7 AR7 - 1 month ago 5
C++ Question

Why does += work on std::map keys that don't have values?

I was looking at the way's people solved the problem proposed here:


Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.


One of the solutions was to do the following:

#include <map>
#include <vector>
#include <algorithm>

using std::max;
using std::map;
using std::vector;

struct Interval {
int start;
int end;
Interval() : start(0), end(0) {}
Interval(int s, int e) : start(s), end(e) {}
};

int minMeetingRooms(vector<Interval>& intervals) {
map<int, int> changes;
for (auto i : intervals) {
changes[i.start] += 1;
changes[i.end] -= 1;
}
int rooms = 0, maxrooms = 0;
for (auto change : changes)
maxrooms = max(maxrooms, rooms += change.second);
return maxrooms;
}


Which increments a counter every time a new meeting starts and decrements a counter every time a meeting ends, taking the max of that counter and the previous max on every iteration.




What I'm curious about though is the part where the map is intialized

for (auto i : intervals) {
changes[i.start] += 1;
changes[i.end] -= 1;
}


The values in the map have never been set, but yet you can still use the
+=
operator. I assume this causes the map to create a
0
in that place, which you then increment, but is this undefined behavior? Also is there a default value for every type? For example, if I had a map of
<int, string>
would what it put as the default value? Does it just call the default constructor?

Basically what I'd like to know is the internals of
std::map
which allow for one to add to a key that doesn't yet exists, and how it varies from type to type.




As a side note:

If I were trying to write more idiomatic code, I would have put

if (changes.find(i.start) == changes.end()) changes[i.start] = 0
if (changes.find(i.end) == changes.end()) changes[i.end] = 0


but I'm guessing it's a performance hit or something?

Answer

Read the docs:

Returns a reference to the value that is mapped to a key equivalent to key, performing an insertion if such key does not already exist.

The insertion just uses the default constructor for the key, and the default constructor for int produces 0.

Your "more idiomatic" code is exactly the opposite of idiomatic. You use operator[] when you want autovivification, you only use count/find when you are trying to avoid autovivification.

If you come from a Python background this may seem backwards, but it's idiomatic C++. C++ std::map behaves more like a Python defaultdict than dict; operator lookup auto-vivifies, avoiding autovivification requires explicit method calls.