设置插入进行奇怪的比较

Question

我无法解释插入新元素时std :: set所做的比较次数.这是一个例子:

对于此代码

struct A {
    int i = 0;
    bool operator()(int a, int b)
    {
        ++i;
        return a < b;
    }
};

int main()
{    
    A a;

    set<int, A> s1(a);

    s1.insert(1);    
    cout << s1.key_comp().i << endl;

    s1.insert(2);    
    cout << s1.key_comp().i << endl;
}

输出是

0
3

为什么插入第二个元素需要进行3次比较？O_O

Answer 1

这是使用红黑树来实现的副作用std::set，与标准二叉树相比，它最初需要更多的比较。