50分求教高人关于优先队列，为什么结果不正确
有一个如下定义的文件
#ifndef PROTOCOL_DEF_H
#define PROTOCOL_DEF_H
#if ! defined (BUFSIZE)
#define BUFSIZE 1024
#endif
#if ! defined (MAXPRI)
#define MAXPRI 7
#endif
struct Packet
{
unsigned int l_Priority : 5; //the Priority of the Packet
unsigned int CRC : 8;
bool operator < (const Packet & msg) const // for Priority Queue
{
return l_Priority < msg.l_Priority ;
}
};
#endif
这个Packet结构我需要存入一个优先队列，现在目的是当我对优先队列取出或者保存一个上面定义的Packet结构时候，就把当前队列最大的一个具有优先级别的Packet的优先级别打印出来
于是我定义了如下一个类"Test.h"
#include <queue>
typedef std::priority_queue <const Packet*> Msg_Queue;
class Test
{
public:
Test();
virtual ~Test();
int put(Packet*);
Packet* get();
private:
Msg_Queue wait_queue_;
};
下面是实现"Test.cpp"
#include "stdafx.h"
#include "Test.h"
//////////////////////////////////////////////////////////////////////
// Konstruktion/Destruktion
//////////////////////////////////////////////////////////////////////
Test::Test()
{
}
Test::~Test()
{
}
Packet*
Test::get()
{
Packet* msg = 0;
if(!this->wait_queue_.empty())
{
msg = const_cast<Packet*> (this->wait_queue_.top());
this->wait_queue_.pop();
}
if (!this->wait_queue_.empty())
printf("Maximal Priority in this Queue is %d\n", wait_queue_.top()->l_Priority);
else
printf("Maximal Priority in this Queue is %d\n", -1);
return msg;
}
int
Test::put(Packet* msg)
{
this->wait_queue_.push(msg);
printf("Maximal Priority in this Queue is %d\n", wait_queue_.top()->l_Priority);
return 0;
}
然后我在main中实现一个Test类的实例
Test* test = new Test();
把20个具有不同优先级的Packet添加队列中
Packet* p;
for (int i = 0; i <20; i++)
{
p = new Packet();
p->l_Priority = (i + 10)%7;
printf("put msg in queue with priority %d\n", p->l_Priority);
test->put(p);
}
但是结果不大对
然后我把20Packet取出来，每次显示出来的当前队列中最大的优先级别并不正确
求教出现什么问题
问题点数：50、回复次数：4Top
1 楼iicup（双杯献酒）回复于 2004-10-02 07:46:35 得分 5
不要只说不正确。
应该说：
期望得到： xxxxx
实际得到: yyyyy
这样大家才好分析。Top
2 楼isis（isis）回复于 2004-10-02 18:46:42 得分 0
好吧，我通过随机数产生多个带不同的priority的Packet,比如p1带优先4,p2带优先1,p3带优先5,p4带优先8,p5带优先3
然后把p1~p5添入优先队列
p1进入队列后最大优先是4(队列中只有p1)
然后p2进入队列后最大优先是4(队列中有p1,p2)
然后p3进入队列后最大优先是5(队列中有p1,p2,p3)
然后p4进入队列后最大优先是8(队列中有p1,p2,p3,p4)
然后p5进入队列后最大优先是8(队列中有p1,p2,p3,p4,p5)
但是显示的最大优先不是依次的4,4,5,8,8,而是4,4,4,4,4
同样的出队列一个Packet,然后显示当前的优先队列中某个Packet带的最大优先(top())同样不正确
很简单的代码，不知道错在什么地方Top
3 楼fangrk（加把油，伙计！）回复于 2004-10-02 19:47:27 得分 45
给一个示例：
#include <queue>
#include <vector>
#include <functional>
#include <iostream>
using namespace std;
struct Packet
{
unsigned int l_Priority;
unsigned int CRC;
bool operator < (const Packet & msg) const
{
return l_Priority < msg.l_Priority ;
}
};
template<class T,class Comp=less<T> >
struct CompContent
{
bool operator()(const T* A,const T* B) const
{
return CP(*A,*B);
}
private:
Comp CP;
};
typedef std::priority_queue <Packet*,vector<Packet*>, CompContent<Packet> > Msg_Queue;
int main()
{
Msg_Queue MQ;
for (int i = 0; i <20; i++)
{
Packet* pointer=new Packet;
pointer->l_Priority=(i + 10)%7;
MQ.push(pointer);
}
while(! MQ.empty()){
Packet* pointer=MQ.top();
cout<<pointer->l_Priority<<'\t';
MQ.pop();
delete pointer;
}
}
E:\TEMP>cl /GX d.cpp
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 13.10.3077 for 80x86
Copyright (C) Microsoft Corporation 1984-2002. All rights reserved.
d.cpp
Microsoft (R) Incremental Linker Version 7.10.3077
Copyright (C) Microsoft Corporation. All rights reserved.
/out:d.exe
d.obj
E:\TEMP>d
6 6 6 5 5 5 4 4 4 3
3 3 2 2 1 1 1 0 0 0
E:\TEMP>Top
4 楼fangrk（加把油，伙计！）回复于 2004-10-02 20:03:44 得分 0
priority_queue <const Packet*> 实际上是对指针地址的比较，不是指针的内容进行比较。我把上面的特化一下，让它同样适用于一般的对象。
#include <queue>
#include <vector>
#include <functional>
#include <iostream>
using namespace std;
struct Packet
{
unsigned int l_Priority;
unsigned int CRC;
bool operator < (const Packet & msg) const
{
return l_Priority < msg.l_Priority ;
}
bool operator > (const Packet & msg) const
{
return l_Priority > msg.l_Priority ;
}
};
template<class T,class Comp>
struct CompareContent
{
bool operator()(const T& A,const T& B) const
{
return CP(A,B);
}
private:
Comp CP;
};
template<class T,class Comp>
struct CompareContent<T*,Comp>
{
bool operator()(const T* A,const T* B) const
{
return CP(*A,*B);
}
private:
Comp CP;
};
typedef std::priority_queue <Packet*,vector<Packet*>, CompareContent<Packet*,less<Packet> > > Msg_Queue;
int main()
{
Msg_Queue MQ;
priority_queue<Packet,vector<Packet>,CompareContent<Packet,greater<Packet> > > MQ2;
for (int i = 0; i <20; i++)
{
Packet* pointer=new Packet;
pointer->l_Priority=(i + 10)%15;
MQ.push(pointer);
MQ2.push(*pointer);
}
while(! MQ.empty()){
Packet* pointer=MQ.top();
cout<<pointer->l_Priority<<'\t';
MQ.pop();
delete pointer;
}
cout<<"\n***\n";
while(! MQ2.empty()){
cout<<MQ2.top().l_Priority<<'\t';
MQ2.pop();
}
}
E:\TEMP>cl /GX d.cpp
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 13.10.3077 for 80x86
Copyright (C) Microsoft Corporation 1984-2002. All rights reserved.
d.cpp
Microsoft (R) Incremental Linker Version 7.10.3077
Copyright (C) Microsoft Corporation. All rights reserved.
/out:d.exe
d.obj
E:\TEMP>d
14 14 13 13 12 12 11 11 10 10
9 8 7 6 5 4 3 2 1 0
***
0 1 2 3 4 5 6 7 8 9
10 10 11 11 12 12 13 13 14 14
E:\TEMP>
Top
相关问题
关键词
得分解答快速导航
相关链接
广告也精彩
反馈
