Set the insert by making a weird amount of comparisons

Question

I can not explain the number of comparisons that std :: set makes when 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; } 

Output signal

 0 3 

Why does inserting the 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 than a standard binary tree.

Answer 2

I do not know the specific ones, since they will depend on your implementation of std::set , however, two comparisons are required to determine the equality of two elements, since 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 can thus make the first comparison to determine whether it should go left or right, and then two comparisons to check whether it is equal or not.

The standard has no requirement, except that the number of comparisons is O (log N), where N is the number of elements already in set . Constant factors are the quality of the implementation problem.