2

ウサギなどのオブジェクトの std::list があります。各うさぎには、ID と体重の 2 つのプロパティがあります。そして、このリストでは、うさぎは 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

この問題にアプローチする方法は 2 つあります。

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 に答える