AR7 - 1 year ago 63
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?

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.