2

我有一个 std::list 对象，比如兔子。每只兔子都有两个属性：ID 和重量。在这个列表中，兔子按照 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中，有没有比一个接一个地推送元素更好的方法？

4

3 回答 3

2

为什么不简单地使用top方法std::priority_queue来获取即将被弹出的元素的值，并使用std::list的remove方法呢？

例如（假设队列存储指向列表元素的指针：

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

或（如果队列还存储引用）：

myList.remove(myQueue.top());
于 2013-02-14T06:31:28.710 回答
1

所以这就是 Arch 的代码不能正常工作的原因，我认为最好将它展示给 OP。缺少的链接是从 std::list<> 中删除的相等性。 operator ==()没有它就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]
于 2013-02-14T07:54:49.343 回答
0

有两种方法可以解决这个问题。

该示例假设一个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();

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

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();
}
于 2013-02-14T07:05:00.067 回答