C++向std::set插入元素时自定义比较器被调用两次的原因

你测试使用的复现代码如下：

#include <set>
#include <iostream>
#include <string>

using std::string;

// Student Class
class student {
public:
    // To store Name and Roll Number
    string name;
    int rollnum;

    // Overloaded Constructor
    student(string name, int rollnum)
    {
        this->name = name;
        this->rollnum = rollnum;
    }
};

// Comparator Class to compare 2 objects
class studentcompare {
public:
    // Comparator function
    bool operator()(const student& a,
                    const student& b) const
    {
        std::cout << a.name << "::" << b.name << std::endl;
        return a.name < b.name;
    }
};

// Driver Code
int main()
{
    // Object of class student
    student s1("Raj", 23);
    student s2("Prerna", 24);

    std::set<student, studentcompare> s;
    s.insert(s1);
    s.insert(s2);
    return 0;
}

插入首元素无比较调用的原因 #

std::set是基于红黑树实现的有序唯一容器，元素按传入的比较器规则排序。空集合插入第一个元素时，红黑树不存在任何已有节点，既不需要通过比较确定插入位置，也不需要做重复元素校验，直接构造根节点即可，因此比较器的operator()不会被调用，符合预期。

插入第二个元素触发两次同参数比较的原因 #

首先明确两个基础规则：

• std::set不使用==判断元素重复，而是通过比较器结果做等价判定：如果comp(a,b)和comp(b,a)均返回false，就认定a和b等价，拒绝重复插入。
• C标准仅要求set插入操作的时间复杂度为O(log n)，没有对比较器的调用次数、调用顺序做强制规定，具体行为由STL实现决定，不同版本的libstdc、libc++、MSVC STL，甚至同一实现在debug/release不同编译配置下，比较次数都可能存在差异。

你观察到的两次调用均为s2作为第一参数、s1作为第二参数，是对应STL实现的正常执行逻辑：

1. 第一次调用是插入流程的位置查找步骤：当前红黑树只有根节点s1，比较s2和s1的大小，由于"Prerna" < "Raj"返回true，直接判定s2应该放在s1的左子树位置。同时根据严格弱序的公理，只要比较器是合法的，此时comp(s1, s2)必然返回false，两个元素不等价，不需要再做反向比较就能确定s2不是重复元素。
2. 第二次调用是STL内部实现带来的额外操作：老版本GCC libstdc++、部分版本MSVC STL在找到空的插入位点后，会额外执行一次同参数比较，用来校验插入位置的合法性，避免比较器不符合严格弱序要求时损坏红黑树结构；也有部分实现是因为代码逻辑复用（插入校验逻辑和遍历查找逻辑共用同一段比较代码），自然产生了这次重复比较。

这种额外的同参数比较不属于bug，只要你的比较器满足严格弱序要求，完全不会影响set的排序结果和功能正确性。

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