关于C++ set自定义comparator调用次数差异的技术咨询

场景1：升序比较器的情况 #

代码 #

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

输出 #

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 

疑问：明明set按升序排序，但比较器被调用3次，且参数顺序反复变化，第一次a=10、第二次a=1、第三次又回到a=10，这是为什么？

场景2：降序比较器的情况 #

代码 #

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

输出 #

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

疑问：此时比较器仅被调用2次，和升序情况的调用次数不同，如何解释？

解答 #

C++的std::set底层基于红黑树实现，插入元素时需要通过比较器完成两个核心逻辑：确定元素的插入位置，以及判断元素是否重复（若cmp(a,b)和cmp(b,a)都为false，则认为a、b等价，不会插入重复元素）。比较器的调用次数和参数顺序完全由红黑树的插入、平衡调整逻辑决定，不同比较规则会触发不同的执行路径。

升序比较器（return a < b）的调用逻辑 #

1. 插入1：树为空，直接插入，无比较器调用。
2. 插入10：
   • 第一次调用cmp(10, 1)：返回false（10不小于1），说明10不能放在1的左侧，需要进一步确认位置。
   • 第二次调用cmp(1, 10)：返回true（1小于10），说明1应放在10左侧，同时证明两者不等价（可插入），确定10要放在1的右侧。
   • 第三次调用cmp(10, 1)：红黑树插入后需要做平衡调整，调整过程中再次触发比较，确认节点位置关系。

降序比较器（return a > b）的调用逻辑 #

1. 插入1：树为空，直接插入，无比较器调用。
2. 插入10：
   • 第一次调用cmp(10, 1)：返回true（10大于1），说明10优先级更高，应放在1的左侧。
   • 第二次调用cmp(10, 1)：平衡调整过程中再次触发比较，但这次调整逻辑不需要额外的反向验证，因此仅调用两次。

关键总结 #

• 比较器的调用次数、参数顺序属于标准库底层实现细节，不同编译器（GCC/Clang/MSVC）的红黑树实现可能存在差异，不要依赖这些细节编写代码。
• 只要保证自定义比较器符合严格弱序规则（即满足非自反性、非对称性、传递性等要求），std::set就能正常工作，无需关心具体调用次数。

内容的提问来源于stack exchange，提问作者Turing101