0

我迷失在标准堆函数上......似乎 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 回答