Механизм вызова компактора для std::map

Question

Я проводил некоторые тесты по использованию определенного пользователем типа данных в качестве ключа на карте. Я заметил, что вызов функции сравнения в случае карты не является фиксированным, это зависит от того, какой контент вы вставляете. Это всего лишь наблюдение. Ниже приведен код

class User
{
public:
    int age;
    int mark;
    std::string name;
    User(int age, int mark, std::string name):age(age),mark(mark),name(name)
    {
    }
    ~User()
    {
    }
    bool operator< (const User& obj) const
    {
            std::cout<<"Called.\n";
            if(this->age < obj.age)
                    return true;
            else
                    return false;
    }
};
class ComparatorUser
{
public:
    bool operator() (const User & lhsUser, const User& rhsUser) const
    {
            std::cout<<"called functor.\n";
            return (lhsUser.age < rhsUser.age);
    }
};
int main()
{
    std::map<User, int, ComparatorUser> userMap;
    userMap.insert(std::make_pair(User(10, 100, "Sagar"), 1));
    userMap.insert(std::make_pair(User(20, 50, "harry"), 2));
    userMap.insert(std::make_pair(User(30, 50, "harry"), 2));
}

 O/P:
 smadala@gateway2:Map$ ./a.out
 called functor.
 called functor.
 called functor.
 called functor.
 called functor.
 called functor.
 called functor.

Когда я изменяю элемент вставки, как показано ниже, количество сравнений уменьшается:

 int main()
 {
    std::map<User, int, ComparatorUser> userMap;
    userMap.insert(std::make_pair(User(20, 100, "Sagar"), 1));
    userMap.insert(std::make_pair(User(10, 50, "harry"), 2));
    userMap.insert(std::make_pair(User(100, 50, "harry"), 3));
 }
 O/P:
 smadala@gateway2:Map$ ./a.out
 called functor.
 called functor.
 called functor.
 called functor.
 called functor.

Сложность вставки std::map равна O(log(n)). Так, как я могу вычислить количество сравнений, так как оба элемента номера дела для вставки одинаковы, но порядок вставки отличается?