Set insert doing a weird number of comparisons

Question

I am unable to explain the number of comparisons that std::set does while inserting a new element. Here is an example:

For this code

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

The output is

0
3

Why does inserting a second element require 3 comparisons? o_O

Answer 1

This is a side effect of using a red-black tree to implement std::set, which requires more comparisons initially compared to a standard binary tree.

Answer 2

I don't know the particular as they will depend on your std::set implementation, however determining the equality of two items requires two comparisons, as it is based on the fact that not (x < y) and not (y < x) implies x == y.

Depending on how the tree is optimized, you might thus be paying a first comparison to determine whether it should go left or right, and then two comparisons to check whether it's equal or not.

The Standard has no requirement except that the number of comparisons be O(log N) where N is the number of items already in the set. Constant factors are a quality of implementation issue.