c++ 为什么我的比较器在插入集合时被调用两次?

w41d8nur  于 9个月前  发布在  其他
关注(0)|答案(2)|浏览(98)

我想看看比较器在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;
}

字符串

sgtfey8w

sgtfey8w1#

这似乎取决于实施。
如果你在gcc上运行代码,你会得到双重调用,如果你用clang运行它,你不会:
https://godbolt.org/z/z7xMKaqqf
(and MSVC执行两次调用,但参数已切换)

x8diyxa7

x8diyxa72#

std::set容器是一个关联容器,存储唯一键,这些键根据严格的弱排序标准进行排序。它被实现为自平衡二叉搜索树(BST)。
这意味着插入操作需要执行两个子操作:

  • 找到新钥匙要插入的位置;
  • 检查密钥是否已存在。

最后一个子操作是保证不插入重复的键所必需的。实际上,为了确定两个键是否等价,需要调用比较器两次。

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

字符串
在您的示例中,第一个插入操作不执行任何查找或检查,因为s1插入到空集合中。第二个插入操作需要调用比较器,以便得到s2是否应该作为左孩子或右孩子被添加。然后再调用一次比较器,以检查s2是否等价于s1

相关问题