priority_queue帮助 [英] priority_queue help
问题描述
任何人都可以帮助我w / priority_queue。我正在生成MyEvent课程
我把它们放在priority_queue上，但我不知道怎么把它们放在
优先级。优先级是具有最小时间戳的事件。
//只是priority_queue的包装器
pq = new MyPriorityQueue（）;
//我生成10个带有随机时间戳的事件
for（int i = 0; i< 10; i ++）{
MyEvent * event = new MyEvent（）;
event-> set_id（idx ++）;
event-> set_gen_tstamp（）;
pq-> push_event（event）;
}
//现在我需要找到具有最小时间戳的事件
if（pq-> size（）0）{
MyEvent * evnt = pq-> top_event（）;
if （evnt-> is_expired（））{
//做东西......然后删除此事件
pq-> pop_event（）; < br $>
}
}
//不确定我在这做什么，但我正在努力做一个过载
//运算符并让它返回最小时间的优先级。我认为这是我需要帮助的地方。
//甚至不确定这是否可以做。
bool MyEvent :: operator< （const MyEvent * event）
{
if（_timestamp< event-> _timestamp（））
返回true;
}
返回false;
}
Joe，GI schrieb：
任何人都可以帮助我w / priority_queue。我正在生成MyEvent课程
我把它们放在priority_queue上，但我不知道怎么把它们放在
优先级。优先级是具有最小时间戳的事件。
通常，具有n个优先级的优先级队列可以通过带有头尾指针的
silgle链表进行建模。优先级在
事实中，插入操作在队列中的正确位置应用。
在这种情况下，Put和get是O（1）。
但是，如果您将时间索引作为优先级，那么您将拥有几乎无限数量的优先级。所以你需要随机访问队列元素来进行二进制搜索。 std :: deque就是这样一个容器。
或者，如果插入的队列元素的时间戳可能与队列深度相比很可能是一个双重链表用
后面的线性搜索可能就足够了。你可以为此目的使用std :: list
。
//不确定我在这里做什么，但我正在尝试重载
//运算符并让它返回最小时间的优先级。我认为这是我需要帮助的地方。
//甚至不确定这是否可以做。
bool MyEvent :: operator< （const MyEvent * event）
{
if（_timestamp< event-> _timestamp（））
返回true;
}
返回false;
}
我不会超载比较运算符在这里，因为事件只是时间的特征并且给它们一个''大于''
语义是没有意义的。我会将比较器函数传递给
队列，在编译时作为模板参数或作为函数指针
作为运行时的构造函数参数。
Marcel
Joe，GI写道：
>
任何人都可以帮助我w / priority_queue。我正在生成MyEvent课程
我把它们放在priority_queue上，但我不知道怎么把它们放在
优先级。优先级是具有最小时间戳的事件。
//只是priority_queue的包装器
pq = new MyPriorityQueue（）;
a）除了
混淆之外，标准模板的包装没有其他用途。
b）为什么new（）？
//我生成10个带有随机时间戳的事件
for（ int i = 0; i< 10; i ++）{
MyEvent * event = new MyEvent（）;
event-> set_id（idx ++）;
event-> set_gen_tstamp（）;
pq-> push_event（event）;
}
好的：你的优先级队列有value_type = MyEvent *。
//现在我需要找到事件w /最小时间戳
if（pq-> size（）0）{
MyEvent * evnt = pq-> top_event（）;
if（evnt-> is_expired（））{
如果有一段时间不应该这样吗？
//做的事情...然后删除此活动
pq-> pop_event（）;
}
}
//不确定我在做什么，但我正在尝试做一个超载
//运算符并让它返回最小时间的优先级。我认为这是我需要帮助的地方。
//甚至不确定这是否可以做。
bool MyEvent :: operator< （const MyEvent * event）
{
if（_timestamp< event-> _timestamp（））
返回true;
}
返回false;
}
a）这是一个类型不匹配。你的队列是在MyEvent *而不是MyEvent上模板化的。
b）你不能重载运算符<对于指针类型。
c）最好的办法是定义一个仿函数类：
struct MyEventPointerCompare {
bool operator（）（MyEvent * lhs，MyEvent * rhs）const {
return（lhs-> _timestamp< rhs-> _timestamp）;
}
};
现在你可以拥有
std :: priority_queue< MyEvent *，MyEventPointerCompare the_queue;
Best
Kai-Uwe Bux
Kai-Uwe Bux写道：
Joe，GI写道：
>>
任何人都可以帮助我w / priority_queue。我正在创建MyEvent课程并且我把它们放在priority_queue上，但我不知道如何优先考虑它们。优先级是具有最小时间戳的事件。
//只是priority_queue的包装器
pq = new MyPriorityQueue（）;
a）除了
混淆之外，标准模板的包装没有其他用途。
b）为什么新的（）？
> //我为随机时间戳生成了10个事件（int i = 0; i< 10; i ++）{
MyEvent * event = new MyEvent（）;
event-> ; set_id（idx ++）;
event-> set_gen_tstamp（）;
pq-> push_event（event）;
}
好的：你的优先级队列有value_type = MyEvent *。
> //现在我需要找到具有最小时间戳的事件
if（pq-> size（）0）{
MyEvent * evnt = pq-> top_event（）;
if（evnt-> is_expired（））{
如果有一段时间不应该这样吗？
> //做东西...然后删除这个事件
pq-> pop_event（）;
}
}
//不确定是什么我在这里，但我正在尝试重载
//运算符并让它返回最小时间的优先级。我认为这是我需要帮助的地方。
//甚至不确定这是否可以做。
bool MyEvent :: operator< （const MyEvent * event）
{
if（_timestamp< event-> _timestamp（））
返回true;
}
返回false ;
}
a）这是一种类型不匹配。你的队列是在MyEvent上模板化的*不是
MyEvent。
b）你不能重载运算符<对于指针类型。
c）最好的办法是定义一个仿函数类：
struct MyEventPointerCompare {
bool operator（）（MyEvent * lhs，MyEvent * rhs）const {
return（lhs-> _timestamp< rhs-> _timestamp）;
}
};
现在你可以拥有
std :: priority_queue< MyEvent *，MyEventPointerCompare the_queue;
哎呀，我忘记了容器：
std :: priority_queue< MyEvent *，
std :: vector< MyEvent *>，
MyEventPointerCompare the_queue;
Best
Kai-Uwe Bux
Can anyone help me w/ a priority_queue. I''m generating MyEvent classes
and I put them on a priority_queue, but I don''t know how to get them in
priority. The priority is the event w/ the smallest timestamp.
// just a wrapper around priority_queue
pq = new MyPriorityQueue();
// I generate 10 events w/ a random timestamp
for (int i = 0; i < 10; i++) {
MyEvent *event = new MyEvent();
event->set_id(idx++);
event->set_gen_tstamp();
pq->push_event(event);
}
// Now I need to find the event w/ the smallest timestamp
if (pq->size() 0) {
MyEvent *evnt = pq->top_event();
if (evnt->is_expired()) {
// do stuff ... then remove this event
pq->pop_event();
}
}
// Not sure what I''m doing here, but I''m trying to do an overload
// operator and have it return the priority of the smallest time. I
// think this is where I need help.
// Not even sure if this is the thing to do.
bool MyEvent::operator < (const MyEvent *event)
{
if (_timestamp < event->_timestamp())
return true;
}
return false;
}
Hi,
Joe, G.I. schrieb:Can anyone help me w/ a priority_queue. I''m generating MyEvent classes
and I put them on a priority_queue, but I don''t know how to get them in
priority. The priority is the event w/ the smallest timestamp.Normally a priority queue with n levels of priority can be modelled by a
silgle linked list with a head and n tail pointers. The priority is in
fact applied by the insert operation at the right place in the queue.
Put and get are O(1) in this case.
However, if you take a time index as priority you have an nearly
infinite number of priority levels. So you need either random access to
the queue elements to do a binary search. std::deque is such a container.
Or if the time stamps of the inserted queue elements are likely to be
close together compared to the queue depth a doubly linked list with
linear search from the back might be sufficient. You can use std::list
for that purpose.
// Not sure what I''m doing here, but I''m trying to do an overload
// operator and have it return the priority of the smallest time. I
// think this is where I need help.
// Not even sure if this is the thing to do.
bool MyEvent::operator < (const MyEvent *event)
{
if (_timestamp < event->_timestamp())
return true;
}
return false;
}I would not overload the comparsion operators here, since the events are
not characterized by the time only and giving them a ''greater than''
semantic is not meaningful. I would pass a comparer function to the
Queue either as template argument at compile time or as funtion pointer
as constructor argument at run time.
Marcel
Joe, G.I. wrote:
>
Can anyone help me w/ a priority_queue. I''m generating MyEvent classes
and I put them on a priority_queue, but I don''t know how to get them in
priority. The priority is the event w/ the smallest timestamp.
// just a wrapper around priority_queue
pq = new MyPriorityQueue();a) There is no other use for a wrapper of a standard template than
obfuscation.
b) Why the new() ?
// I generate 10 events w/ a random timestamp
for (int i = 0; i < 10; i++) {
MyEvent *event = new MyEvent();
event->set_id(idx++);
event->set_gen_tstamp();
pq->push_event(event);
}Ok: your priority queue has value_type = MyEvent*.
// Now I need to find the event w/ the smallest timestamp
if (pq->size() 0) {
MyEvent *evnt = pq->top_event();
if (evnt->is_expired()) {Shouldn''t that if be a while ?
// do stuff ... then remove this event
pq->pop_event();
}
}
// Not sure what I''m doing here, but I''m trying to do an overload
// operator and have it return the priority of the smallest time. I
// think this is where I need help.
// Not even sure if this is the thing to do.
bool MyEvent::operator < (const MyEvent *event)
{
if (_timestamp < event->_timestamp())
return true;
}
return false;
}a) This is a type mismatch. Your queue is templated on MyEvent* not MyEvent.
b) You cannot overload operator< for pointer types.
c) Your best bet is to define a functor class:
struct MyEventPointerCompare {
bool operator() ( MyEvent* lhs, MyEvent* rhs ) const {
return ( lhs->_timestamp < rhs->_timestamp );
}
};
Now you can have
std::priority_queue< MyEvent*, MyEventPointerCompare the_queue;
Best
Kai-Uwe Bux
Kai-Uwe Bux wrote:
Joe, G.I. wrote:
>>
Can anyone help me w/ a priority_queue. I''m generating MyEvent classes
and I put them on a priority_queue, but I don''t know how to get them in
priority. The priority is the event w/ the smallest timestamp.
// just a wrapper around priority_queue
pq = new MyPriorityQueue();
a) There is no other use for a wrapper of a standard template than
obfuscation.
b) Why the new() ?
> // I generate 10 events w/ a random timestamp
for (int i = 0; i < 10; i++) {
MyEvent *event = new MyEvent();
event->set_id(idx++);
event->set_gen_tstamp();
pq->push_event(event);
}
Ok: your priority queue has value_type = MyEvent*.
> // Now I need to find the event w/ the smallest timestamp
if (pq->size() 0) {
MyEvent *evnt = pq->top_event();
if (evnt->is_expired()) {
Shouldn''t that if be a while ?
> // do stuff ... then remove this event
pq->pop_event();
}
}
// Not sure what I''m doing here, but I''m trying to do an overload
// operator and have it return the priority of the smallest time. I
// think this is where I need help.
// Not even sure if this is the thing to do.
bool MyEvent::operator < (const MyEvent *event)
{
if (_timestamp < event->_timestamp())
return true;
}
return false;
}
a) This is a type mismatch. Your queue is templated on MyEvent* not
MyEvent.
b) You cannot overload operator< for pointer types.
c) Your best bet is to define a functor class:
struct MyEventPointerCompare {
bool operator() ( MyEvent* lhs, MyEvent* rhs ) const {
return ( lhs->_timestamp < rhs->_timestamp );
}
};
Now you can have
std::priority_queue< MyEvent*, MyEventPointerCompare the_queue;Oops, I forgot about the container:
std::priority_queue< MyEvent*,
std::vector< MyEvent*>,
MyEventPointerCompare the_queue;
Best
Kai-Uwe Bux
这篇关于priority_queue帮助的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
