c++ - 以下比较器在构建最小堆时如何工作？

Question

我知道如果我使用 STL 构建一个堆，它会生成一个 max_heap。如果我想制作一个 min_heap，我将不得不编写自己的自定义比较器。现在，下面的比较器，

struct greater1{
  bool operator()(const long& a,const long& b) const{
    return a>b;
  }
};

int main() {
  std::vector<long> humble;
  humble.push_back(15);
  humble.push_back(15);
  humble.push_back(9);
  humble.push_back(25);

  std::make_heap(humble.begin(), humble.end(), greater1());
  while (humble.size()) {
    std::pop_heap(humble.begin(),humble.end(),greater1());
    long min = humble.back();
    humble.pop_back();  
    std::cout << min << std::endl;
  }

  return 0;
}

以上代码是我从网上得到的。我只有一个疑问。比较器实际上是如何工作的。据我所知，它不应该是这样的吗return a < b因为我们希望最小元素在前面，然后是堆中较大的元素。为什么是return a > b .这不是说吗，if (a>b) , 然后这将返回 true 和 a会在b之前放入堆中因此一个更大的元素被放在一个更小的元素前面？

Answer 1

我认为您对比较器语义和堆语义之间的联系读得太多了。请记住，容器的内部细节和结构是故意从您那里抽象出来的，因此，当您开始尝试根据您认为 max_heap 的内部结构应该如何看待这一点来合理化时，您得到了带走了。

在标准库中，默认比较器总是 小于。如果特定容器/算法中用于排序的元素之间的关系不是小于，则容器/算法将足够聪明以进行该转换(在这种情况下，在通常的实现中，通过简单地传递以相反的顺序操作数，如 cmp(b,a)!)。但是，从根本上说，它总是以 小于 顺序开始，因为这是一致采用的约定。

因此，要颠倒容器的顺序，您需要一个小于比较器并将其转换为一个大于比较器，无论物理上是什么容器实现的布局可能(在您看来)是这样的。

此外，顺便说一句，为了回应 Croissant 的评论，我会按值获取 long ……事实上，只使用 std::greater 而不是而不是重新创建它。