为什么我的比较器在插入一组时会被调用两次？

Question

我试图了解比较器在 cpp 中是如何工作的。因此，当我插入

s1

时，不会调用比较器运算符，这是有道理的。但是当插入

s2

时，比较器运算符被调用两次。为什么？ 当我检查时，我发现两次调用比较器的第一个参数都是

s2

，而第二个参数是

s1

。谁能给我解释一下吗？

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

Answer 1

这似乎取决于实现。

如果你在 gcc 上运行你的代码，你会得到双重调用，如果你用 clang 运行它，你不会：

https://godbolt.org/z/z7xMKaqqf

（MSVC 执行两次调用，但参数已切换）

Answer 2

std::set

容器是一个关联容器，用于存储唯一键，这些键根据比较对象进行排序。它是作为自平衡二叉搜索树（BST）实现的。

这意味着一个插入操作需要执行两个子操作：

• 找到新钥匙要插入的位置
• 检查key是否已经存在

最后一个子操作是保证不插入重复键所必需的。事实上，比较器需要调用两次才能确定两个键是否相等。

equiv(a, b) == !comp(a, b) && !comp(b, a)

在您的示例中，第一个插入操作不执行任何查找或检查，因为

s1

被插入到空集合中。但是，第二次插入操作需要调用比较器以获取是否应将

s2

添加为根的左子节点或右子节点，然后再次调用比较器以检查

s2

是否为相当于

s1

。