使用对象的优先级队列的C++

我想创建一个对象的优先级队列，特别是对（int，int）。队列应该包含分配给它们的优先级。使用对象的优先级队列的C++

#include <iostream> 
#include <queue> 

using namespace std;  

class saPair{ 
public: 
    int s; 
    int a; 
    double priority; 
    saPair(int s, int a, double priority){ 
     this->s = s; 
     this->a = a; 
     this->priority = priority; 
    } 
}; 

// the priority menmber variable determines the priority in the queue 
// highest priority pair of (int, int) stays on the top 
bool operator< (const saPair& x, const saPair& y) { 
    return x.priority < y.priority; 
} 


int main() 
{ 
    priority_queue<saPair> pq; 
    pq.push(saPair(0,0, 0.3)); 
    pq.push(saPair(0,1, 0.1)); 
    pq.push(saPair(0,3, 0.5)); 
    pq.push(saPair(0,3, 5)); 

    cout << pq.top().a << endl; 
    pq.pop(); 
    cout << pq.top().a << endl; 
    pq.pop(); 
    cout << pq.top().a << endl; 


}

正如您所看到的，对（0,3）具有最高的优先级，因此它保持在最高位置。但是我的实现的问题是，如果我以不同的优先级再次添加（0,3）对，我会向队列中添加一个新元素，而不是替换已存在的（0,3）对的优先级。

我觉得我为我的要求选择了错误的数据结构。我试图通过定义一个新的saPair（int，int）类来为映射获取关键值，该类具有操作超载的运算符<。但即使这似乎并没有正常工作..

关于如何进行的任何建议？或修改

来源

2017-04-03 emperorspride188

它是一个队列，所以没有关于唯一性的要求。也许你想要的是一套？！ – Arash

是的。没有办法直接使用队列。我正在寻找一种替代数据结构。这感觉就像是一种常见的数据结构，但我无法找到一个简单的解决方案。一个对象，以及分配给该对象的相应优先级。按优先级顺序对对象进行排序。我需要一个满足这一点的数据结构。 – emperorspride188

看起来您需要对您的容器进行多键访问：您希望按照优先级对其进行排序（或者至少按照priority_queue中的优先级对二进制堆进行排序），并且希望对值为独特的，所以你也需要一对值查找。

标准库中没有默认的解决方案，但是制作自己的应用程序不应该太难。

我建议简单地存储一个额外的std::set<saPair>来检查是否已经在你的容器中。通过这种方式，您可以保持priority_queue的原样，并且不需要太多的努力来实施。

不要忘记将operator<加到saPair虽然（或者用std::pair代替它），否则std::set将无法使用它。

另一种选择是每次添加时手动检查您的priority_queue。虽然渐近地比std::set解决方案更差，但实际上这可能会更快，并且会为您节省一些空间。不过，我认为如果您使用std::set，代码将会更清晰。

另一种解决方案是boost::multi_index，它允许您轻松构建任何你想要的多索引容器。不过，我认为它不会让你利用这个事实，即你不需要按优先级进行强排序，所以它不会有像priority_queue那样的线性连续布局。

来源

2017-04-03 05:45:46 Ap31

使用对象的优先级队列的C++

回答

相关问题