0

std ヒープ関数で迷っています... push_heap は、入力したコンパレーターを尊重していないようです。

編集:エラーの原因となった無意味な operator=() を作成しました。コードのセクションを修正しました....

以下は、簡略化された例です。

#include <vector>
#include <iostream>
#include <algorithm>


using namespace std;

template<class T>
struct lt_entry: public binary_function <T, T, bool>
{
    bool operator()(const T &l, const T &r) const
    {
        cout << l._cost << " < " << r._cost << " ? " << (l._cost < r._cost) << endl;
        return l._cost < r._cost;
    }
};

template<typename T, class Cmp>
struct OrderedVector {
    vector<T> _c;

    inline void insert(T &&t) {
        _c.push_back(move(t));
        push_heap(_c.begin(), _c.end(), Cmp());
        cout << "i is heap: " << is_heap(_c.begin(), _c.end(), Cmp()) << endl;
    }

    inline T extract_min() {
        pop_heap(_c.begin(), _c.end(), Cmp());
        T t = move(_c.back());
        _c.pop_back();
        cout << "e is heap: " << is_heap(_c.begin(), _c.end(), Cmp()) << endl;
        return move(t);
    }

    inline bool empty() const {
        return _c.empty();
    }
};

struct Entry
{
    float _cost;

    Entry(Entry &&ofs) :
        _cost(ofs._cost)
    {
    }

    //This caused the error
    //Entry operator=(Entry &&e) {
    //  return Entry(move(e));
    //}



    Entry& operator=(Entry &&e) {
        _cost = e._cost;
        return *this;
    }


    Entry(float cost) : _cost(cost)
    {
    }
};

typedef  OrderedVector<Entry, lt_entry<Entry> > OrderedContainer;



int main() {

    OrderedContainer h; // Doesn't work, breaks heap on second insertion

    h.insert(Entry(200.1));
    h.insert(Entry(100.1));
    h.insert(Entry(300.1));
}

コンパイラは gcc 4.7.2 で g++ heaps.cpp -std=c++0x -Wall -O3 です。

出力は次のとおりです。

i is heap: 1
200.1 < 100.1 ? 0
200.1 < 100.1 ? 0
i is heap: 1
200.1 < 300.1 ? 1
200.1 < 100.1 ? 0
200.1 < 300.1 ? 1
i is heap: 0 <---- Heap is broken...
4

1 に答える 1

1

Entry の (移動) 代入演算子は、実際には を変更this->cost_したり、何も変更したりしていません*this。実行するすべてのスワップ/移動割り当てmake_heapは何もしません。

于 2012-12-13T18:11:30.310 に答える