2

I am trying to understand the behavior of this following piece of code.

#include <iostream>
#include <string>
#include <set>
using namespace std;
 
struct cmp {
    bool operator() (int a, int b) const {
        cout<<"This is a-->"<<a<<" "<<endl;
        cout<<"This is b-->"<<b<<" "<<endl;
        return a < b;
    }
};
 
int main() {
    set<int, cmp> s;
 
    s.insert(1);
    s.insert(10);
    //s.insert(11);
    //s.insert(100);
 
    for (int x : s)
        cout << x << ' ';
 
    return 0;
}

The output that I am getting for this is

This is a-->10 
This is b-->1 
This is a-->1 
This is b-->10 
This is a-->10 
This is b-->1 
1 10

I understand what this code does is that it sorts the elements of the set in ascending order but why is the comparator is being called 3 times? And why in the first case a is 10 but in the second case a is 1 and again in the third case it is 10?

And when I modify the code slightly to store the elements in the decreasing order, like below

#include <iostream>
#include <string>
#include <set>
using namespace std;
 
struct cmp {
    bool operator() (int a, int b) const {
        cout<<"This is a-->"<<a<<" "<<endl;
        cout<<"This is b-->"<<b<<" "<<endl;
        return a > b;
    }
};
 
int main() {
    set<int, cmp> s;
 
    s.insert(1);
    s.insert(10);
    //s.insert(11);
    //s.insert(100);
 
    for (int x : s)
        cout << x << ' ';
 
    return 0;
}

Then why is the comparator function is being called only twice as seen in the output?

This is a-->10 
This is b-->1 
This is a-->10 
This is b-->1 
10 1

It will be of great help if anyone can shed some light on this.

JaMiT
  • 14,422
  • 4
  • 15
  • 31
Turing101
  • 347
  • 3
  • 15
  • Comparitors can be called multiple times by the runtime (usually a debug version) to check to see if your comparitor follows a strict-weak-order. – PaulMcKenzie Jan 04 '23 at 09:57
  • There's no simple explanation, you need to look at the details of your `std::set` implementation (which is likely to be very complex). – john Jan 04 '23 at 10:04
  • How many times a comparator is called during the operations shown in your examples is completely up to the implementation. It may additionally depend on the optimizations active during compilation (also implementation defined). – nada Jan 04 '23 at 10:05
  • 1
    The equality check is done via `!comp(a, b) && !comp(b, a)` where `comp` is the comparator instance. This should explain 2 of the 3 comparisons... – fabian Jan 04 '23 at 10:05
  • @nada I don't think it's completely up to the implementation, they must still follow the complexity constraints (logarithmic in this case). – john Jan 04 '23 at 10:07
  • @john Of course, but still, different versions of different compilers on different settings will most definitely give different results. – nada Jan 04 '23 at 10:08
  • Possibly relevant: [What kind of tree implementation is STL set?](https://stackoverflow.com/q/10375334/580083), [What is the underlying data structure of a STL set in C++?](https://stackoverflow.com/q/2558153/580083), [Does any std::set implementation not use a red-black tree?](https://stackoverflow.com/q/26550276/580083), [Red–black tree](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree). – Daniel Langr Jan 04 '23 at 10:12
  • Does this answer your question? [Set insert doing a weird number of comparisons](https://stackoverflow.com/questions/22957117/set-insert-doing-a-weird-number-of-comparisons) – JaMiT Jan 04 '23 at 12:38
  • The set is a [red-black tree](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree). It guarantees that all three major operations (insert / find / erase) are _logarithmic_ w.r.t. the current size of the set, but there is no firm specification when it comes to multiplicative, not to mention additive constants. So it is perfectly reasonable to expect additional comparisons as the tree is traversed, dynamically rebalanced etc., including a bit of “asymmetry” etc. In summary, what you are seeing is not surprising and (IMO) not worth further investigation. – Andrej Podzimek Jan 04 '23 at 15:47

0 Answers0