19

私が理解しているように、ユーザー定義の構造体の場合は簡単です。演算子 < をオーバーロードするだけです。ただし、int/float などの場合、int の演算子 < をオーバーロードする必要はありますか? これが私が試したものです：

       #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 は最小ヒープを正しく維持しませんか? これを達成する簡単な方法はありますか？ありがとう！

編集：申し訳ありませんが、マニュアルを注意深く確認していませんでした。はい、comp を pop_heap または push_heap に渡すとうまくいくはずです。しかし、外部コンパレータを使用しないでくださいとはどういう意味ですか? それが正しい方法ではない場合、これを達成するための一般的な方法は何ですか?

4

3 に答える 3

31

std::greater<int>()コンパレータとして使用します（、、、のすべてmake_heapに対して）。重要なのは、関数ではなくファンクタークラスであるため、そのインスタンスが必要です。push_heappop_heap()std::greater<int>

于 2011-10-07T00:19:53.000 に答える
9

operator <forをオーバーロードする必要はありませintん (実際にはできません)。外部コンパレータを使用する場合は、同じComparator compものpop_headも同様に渡す必要があります。

* 編集： *

ildjarn が指摘したように、比較演算子は厳密-弱-順序関係を実装していません。

a < b ? false : true; --> a >= b
b < a ? true : false; --> a > b
于 2011-10-07T00:00:57.377 に答える