如何從列表中刪除具有相應優先級隊列的元素？

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(); 
}