使用用户定义的对象实现最小优先级队列（C++ STL）

Question

我正在实施 Prims 算法。我有一个边向量及其权重。问题是，插入后，队列不会根据边的权重保持递增顺序。

相关代码如下：-

struct weightcomp // To be used solely for priority Queue...
{
    bool operator()(Edge &E1, Edge &E2)
    {
        if(E1.weight > E2.weight)
            return true;
    }
};

std::priority_queue<Edge,std::vector<Edge>,weightcomp> PQ; // Priority Queue for Edges

void visit(std::vector<Edge> &PMST, int i) // PMST = Vector of edges and i = name of node
{
    for(auto iter = PMST.begin();iter != PMST.end();++iter)
    {
        if((*iter).u == i || (*iter).v == i)
        {
            PQ.push((*iter));
            (*iter).del = true;  // Mark the vectors elements to be removed.
        }
    }

    PMST.erase(std::remove_if(PMST.begin(),PMST.end(),[](Edge e){ return e.del;}),PMST.end()); // Delete the marked elements
}

我在实施中遗漏了什么？

Answer 1

您有未定义的行为，因为您的比较并不总是 return 一个值。你需要符合

的东西

bool operator()(const Edge &E1, const Edge &E2) const
{
    return E1.weight > E2.weight;
}

我在哪里引用了参数 const 因为比较不应该修改它们，而运算符 const 因为它不会改变仿函数的状态。

使用用户定义的对象实现最小优先级队列（C++ STL）

Implementing Min priority Queue(C++ STL) using user-defined objects

stl

priority-queue

c++11