Как std :: map использует пользовательскую функцию сравнения в C ++ (или как часто она вызывается)?

Question

Я пытался написать код для лексикографической сортировки и наткнулся на этот пример кода:

#include <cstring>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <vector>

using std::string;
using std::transform;
using std::map;
using std::cout;

struct Compare {
    bool operator() (const int& s0, const int& s1) const {
        cout << "in compare: s0=" << s0 << " s1=" << s1 << "\n";

        return s0 < s1;
    }
};

typedef map<int, int, Compare> num_count;

int main(){
   num_count nc;
   auto nums = { 4, 2, 5, 1, 6 };

    for (auto num : nums) {
        cout << "num=>" << num << '\n';
        nc[num]++;
    }

    for(auto elem : nc)
        cout << elem.first << '\n';

    return 0;
}

ссылка на wandbox

Код работает в значительной степени, как Я хочу, чтобы это сработало. Я просто пытаюсь понять функцию сравнения. На первой вставке нет сравнения один (очевидно). На 2-й вставке функция сравнения вызывается три раза. Это та часть, которую я не понимаю. Самое близкое, что я понял, это то, что это связано с тем, как реализована карта (красно-черное дерево). Одной из ссылок, которая дала некоторые пояснения, был комментарий здесь .

Может кто-нибудь объяснить это подробно? Спасибо.