如何从列表中删除具有相应优先级队列的元素？

Question

我有一个std ::对象列表，比如兔子。每只兔子都有两个属性：身份证和体重。在这个列表中，兔子是按ID排列的。 然后我使用std :: priority_queue来存储指向该兔子列表的指针，按照权重的顺序。

现在我打算使用此priority_queue删除priority_queue和原始列表中最轻的N个兔子。 问题是：如何在原始列表中删除？
示例代码：

#include <queue> 
using namespace std; 
list<Rabbit> rabbitArmy; 
priority_queue<Rabbit, vector<Rabbit*>, CompareWeight> rabbitSortByWeight; 


for (int i = 0; i < 999; i++) { 

    ..... 

    // each rabbit has different ID and Weight, codes omitted 
    Rabbit rabbit(randomID, randomWeight); 
    rabbitArmy.push_back(rabbit); 
    rabbitSortByWeight.push(&rabbitArmy.back()); 
} 


// Now I'll delete N lightest rabbits in the priority_queue 
for (int i = 0; i < N; i++) 

    rabbitSortByWeight.pop(); 

什么原单？顺便说一句，如果我有一个列表，那么我想把它放在priority_queue中，有没有比推动元素一个接一个更好的方法？

Answer 1

因此，这里是为什么Arch的代码是不是很工作，而我想，这可能是更好的只是展示给OP。缺少的链接是等于operator ==()从std :: list <>中删除。没有这个std::list<T>::remove()没有办法比较发送的对象是否是正在检查的对象。

#include <iostream> 
#include <iterator> 
#include <list> 
#include <vector> 
#include <queue> 
#include <iomanip> 
#include <ctime> 
using namespace std; 

// my rabbit (I don't have yours). 
struct Rabbit 
{ 
    Rabbit(int weight=0, int size=0) 
     : weight(weight), size(size) {}; 

    int weight; 
    int size; 

    // needed for std::list<>::remove() 
    bool operator ==(const Rabbit& other) 
    { 
     return weight == other.weight 
      && size == other.size; 
    } 
}; 

// write to output stream 
std::ostream& operator <<(std::ostream& os, const Rabbit& rabbit) 
{ 
    os << '[' << setw(2) << rabbit.weight << ',' << setw(2) << rabbit.size << ']'; 
    return os; 
} 

// functor for comparing two rabbits by address 
struct CompareRabbitPtrs 
{ 
    bool operator()(const Rabbit* left, const Rabbit* right) 
    { 
     return right->weight < left->weight || 
       (right->weight == left->weight && right->size < left->size); 
    } 
}; 

// some typedefs to make life a little easier. first the list 
typedef std::list<Rabbit> RabbitList; 

// now the priority_queue 
typedef std::priority_queue<Rabbit*, std::vector<Rabbit*>, CompareRabbitPtrs> RabbitQueue; 

int main() 
{ 
    // seed RNG 
    std::srand((unsigned)time(0)); 

    RabbitList rabbits; 
    RabbitQueue rq; 

    // load up your rabbits. 
    for (int i=1;i<12;++i) 
    { 
     rabbits.push_back(Rabbit(std::rand() % 10 + 3,std::rand() % 20 + 5)); 
     rq.push(&rabbits.back()); 
    } 

    // show rabbits 
    std::copy(rabbits.begin(), rabbits.end(), 
       ostream_iterator<Rabbit>(cout,"\n")); 
    cout << endl; 

    // remove top N rabbits, in this case 2 
    for (int i=0;i<2;++i) 
    { 
     rabbits.remove(*rq.top()); 
     rq.pop(); 
    } 

    // show rabbits again. 
    std::copy(rabbits.begin(), rabbits.end(), 
       ostream_iterator<Rabbit>(cout,"\n")); 

    return 0; 
} 

样品试验输出

[11,17] 
[ 6,17] 
[ 8,11] 
[12,14] 
[ 7, 8] 
[ 6,19] 
[11,16] 
[10,19] 
[ 6,21] 
[10,14] 
[ 7,13] 

[11,17] 
[ 8,11] 
[12,14] 
[ 7, 8] 
[11,16] 
[10,19] 
[ 6,21] 
[10,14] 
[ 7,13] 

Answer 2

为什么不简单使用top方法std::priority_queue来获取要弹出的元素的值并使用std :: list的remove方法？

作为示例（假设队列存储的指针到列表中的元素：

myList.remove(*(myQueue.top()); 

或（如果该队列也存储的参考文献）：

myList.remove(myQueue.top()); 

Answer 3

有两种方法我解决此问题

该示例假设Rabbit类与公众id成员

1.我只是把我所有的兔子都放在一个列表中，然后把兔子放在原地。如果兔子已经以特定的顺序列入名单 - 这可能是一个问题。

std::list<Rabbit> l; 
for(int i=0; i<10; i++) 
    l.push_back(Rabbit(rand() % 10)); 

auto comp = [](const Rabbit& a, const Rabbit& b) -> bool{ return a.id > b.id; }; 
l.sort<decltype(comp)>(comp); 

int numToRemove = 3; 
for(int i=0; i<numToRemove; i++) l.pop_back(); 

这将删除3个最低id的兔子。

2.我会完全跳过这个列表，直接使用priority_queue。这样，当你将兔子弹出时，所有东西都会被排序。请注意，priority_queue还有其他限制，可能不适合您的需要。

auto comp = [](Rabbit* a, Rabbit* b) { return a->id > b->id; }; 
std::priority_queue<Rabbit*, std::vector<Rabbit*>, decltype(comp)> q(comp); 

for(int i=0; i<10; i++) 
    q.push_back(new Rabbit(rand() % 10)); 

int numToRemove = 3; 
for(int i=0; i<numToRemove; i++) 
{ 
    delete q.top();; 
    q.pop(); 
}