c++ - 将对象插入 vector 然后将 vector 插入堆时堆无效

Question

我在这里尝试使用 class Bar 来存储 Foo 的有序数组，它的成员 var 如下所示。

我期待这样的输出 3,4,5 但我得到了 5,3,4。

我正在使用我自己的比较函数(强制性的，因为我的 Foo struct 有更多数据)并且在推回 vector 后，我将 vector 推回堆并重新排序。

我在这里错过了什么？

我想要的是将一个 Foo 对象插入我的队列，并自动重新排序。

struct Foo
{
    int var;
    //etc.
};

struct compare
{
   bool operator()(const Foo& s1, const Foo& s2)
   {
       return s1.var < s2.var;
   }
};

class Bar
{
private:
    std::vector<Foo> m_vector;
public:
    Bar() 
    {
        std::make_heap(m_vector.begin(), m_vector.end(), compare());
    }

    ~Bar() {}

    void push (const Foo& t)
    {
        m_vector.push_back(t);
        std::push_heap(m_vector.begin(),m_vector.end(), Comp());
    }

    void pop()
    {
        m_vector.pop_back();
    }

    void dump(void)
    {
        printf ("\n Dumping:");
        for(int i = 0; i < m_vector.size() ; i++)
        {
            printf ("%d ", m_vector.at(i).var);
        }
        printf ("\n");
    }
};

int main() 
{
    Bar myBar;

    myBar.dump();

    Foo t1;
    t1.var = 3;

    myBar.push(t1); 
    myBar.dump();

    Foo t2;
    t2.var = 4;

    myBar.push(t2); 
    myBar.dump();

    Foo t3;
    t3.var = 5;

    myBar.push(t3); 
    myBar.dump();

    return 0;
}

Answer 1

如果您以相反的顺序获取对象，那么您应该切换比较信号:

bool operator()(const Foo& s1, const Foo& s2)
{
   return s1.var > s2.var;
}

但是，您似乎没有正确理解堆。堆不保留已排序的对象，而只是部分排序。请注意，它们仍会按顺序弹出对象，但您需要实际弹出它们，只是迭代堆不会这样做。

请注意下图中数组根本没有排序。但是，当呈现为树时，堆确实拥有一个重要的属性:每个节点都小于其所有后代。这就是部分排序 的意思。对象未排序，但它们以一种可以有效排序的方式相互关联。

为了让你的元素重新排序，你需要弹出它们。

编辑:顺便说一句，您应该使用 std::pop_heap，而不是 std::vector::pop_back。原因经过前面的解释应该就清楚了