How does a custom compare function in std::map in C++ works?

I was trying to write some code for lexicographical sort and came across this sample code:

#include <cctype>
#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 string& s0, const string& s1) const {

    cout << "in compare\n";
        // construct all lowercase versions of s0 and s1
        string str0(s0.length(),' ');
        string str1(s1.length(),' ');
        transform(s0.begin(), s0.end(), str0.begin(), tolower);
        transform(s1.begin(), s1.end(), str1.begin(), tolower);

        if  (!str0.empty() and !str1.empty() and str0.front()==str1.front()) {
            // do a standard lexicographic sort if the first character is the same
        cout << "s0=" << s0 << " s1=" << s1 << " s0 < s1=" << (s0 < s1)  << std::endl;
            return s0 < s1;
        } else {
        cout << "str0=" << str0 << " str1=" << str1 << " str0 < str1=" << (str0 < str1) << std::endl;
            // otherwise, do a case-insensitive lexicographic sort using the lowercased strings
            return str0 < str1;
        }
    }
};


typedef map<string, int, Compare> word_count;

int main(){
    word_count wc;
   auto words = { "t2 13 121 98", "r1 box ape bit", "b4 xi me nu", "br8 eat nim did", "f3 52 54 31" };

    for (auto word : words) {
        cout << "word=>" << word << '\n';
        wc[word]++;
    }

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

    return 0;
}

The code works pretty much how I want it to work. I am just trying to understand the compare function. On first insert no comparison is one (obviously). On 2nd insert the compare function is called three times. This is the part that I don't understand. The closest I have come to understand this is that it is due to the way map is implemented (red-black tree). One of the link that gave some explanation was a comment here.

Could someone please explain this in detail? Thanks.