容易的方法来保持stl的最小堆？ [英] easy way to maintain a min heap with stl?

问题描述

对于用户定义的结构体，如我所知，很容易。只是重载运算符<然而，对于int / float等，我真的需要重载operator<为int？
这是我试过的：

for user defined struct, as I understand, it's easy. Just overload the operator <. However, for int/float etc.., do I really need to overload operator < for int? Here is what I tried:

       #include <iostream>
       #include <algorithm>
       #include <vector>
       using namespace std;

       bool comp(const int& a, const int& b)
       {
          return a<b?false:true;
       }

       int main () 
       {
         int myints[] = {10,20,30,5,15};
         vector<int> v(myints,myints+5);
         vector<int>::iterator it;
         make_heap(v.begin(), v.end(), comp);
         cout << "initial min heap   : " << v.front() << endl;
         for (unsigned i=0; i<v.size(); i++) cout << " " << v[i];
         cout<<endl;

         pop_heap (v.begin(),v.end());
         v.pop_back();
         for (unsigned i=0; i<v.size(); i++) cout << " " << v[i];
         cout<<endl;
       }

结果是：

        initial min heap   : 5
        5 10 30 20 15
        30 10 15 20

现在pop_heap，push_heap不会正确维护最小堆？有没有更容易的方法来实现这一点？
谢谢！

now pop_heap, push_heap won't maintain the min-heap correctly? is there any easier way to achieve this? Thanks!

编辑：
对不起，我没仔细检查手册。是的，传递comp到pop_heap或push_heap应该做的伎俩。但是，你是什么意思，我不应该使用外部比较器？如果它是不正确的做法，什么是实现这一目标的常见方式？

sorry, I didn't check the manual carefully. yes, passing comp to pop_heap or push_heap should do the trick. However, what do you mean, I should not use an external comparator? If it's not the right way, what's the common way to achieve this?

推荐答案

您不应该需要重载运算符< 为 int （实际上不能）。如果你使用外部比较器，你应该将相同的 Comparator comp 传递给 pop_head 。

You shouldn't need to overload operator < for int (you can't, actually). If you use an external comparator, you should be passing the same Comparator comp to pop_head as well.

*编辑：*

由于ildjarn指出的那样，你的比较运算符不实施严格的 - 弱排序关系。

As ildjarn pointed out, your comparison operator does not implement a strict-weak-ordering relation.

a < b ? false : true; --> a >= b
b < a ? true : false; --> a > b

这篇关于容易的方法来保持stl的最小堆？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！