Почему + = работает на std :: map keys, у которых нет значений?

Question

Я смотрел на людей, на пути в решена проблема предложил here:

Дан массив встречи интервалов времени, состоящих из времени начала и окончания [[s1, e1], [s2, e2], ... ] (si < ei), найдите минимальное количество конференц-залов.

Одним из решений были сделать следующее:

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

Что увеличивает счетчик каждый раз, когда начинается новая встреча и уменьшает счетчик, каждый раз встреча заканчивается, принимая максимум этого счетчика и предыдущий максимум на каждой итерации.

---

Что мне интересно, хотя это та часть, где отображение происходит инициализация

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

Значения в карте никогда не были установлены, но все же вы все еще можете использовать оператор +=. Я предполагаю, что это заставляет карту создавать 0 в том месте, которое вы затем увеличиваете, но это неопределенное поведение? Также есть ли значение по умолчанию для каждого типа? Например, если бы у меня была карта <int, string>, что бы она поместила в качестве значения по умолчанию? Он просто вызывает конструктор по умолчанию?

В основном, что я хотел бы знать, это внутренности std::map, которые позволяют добавить один к ключу, который еще не существует, и как он варьируется от типа к типу.

---

В качестве примечания:

Если бы я пытался больше писать идиоматических код, я бы поставил

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

, но я предполагаю, что это падение производительности или что-то?

Answer 1

Read the docs:

Возвращает ссылку на значение, которое отображается в качестве ключевой эквивалентного ключа, выполняя вставку, если такой ключ уже не существует.

Вставка просто использует конструктор по умолчанию для ключа, и конструктор по умолчанию для int производит 0.

Ваш «более идиоматических» код в точности противоположна идиоматическое. Вы используете operator[], когда вы хотите автовыобразования, вы используете только count/find, когда вы пытаетесь избежать автоподтверждения.

Если вы исходите из фона Python, это может показаться обратным, но это идиоматический C++. C++ std::map ведет себя как Python defaultdict чем dict; автоматический поиск оператора, избегая автовивитации, требует явных вызовов методов.