priority_queue帮助

本文介绍了priority_queue帮助的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 任何人都可以帮助我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（）; } } //不确定我在这做什么，但我正在努力做一个过载 //运算符并让它返回最小时间的优先级。我认为这是我需要帮助的地方。 //甚至不确定这是否可以做。 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 classesand I put them on a priority_queue, but I don''t know how to get them inpriority. The priority is the event w/ the smallest timestamp. // just a wrapper around priority_queuepq = new MyPriorityQueue(); // I generate 10 events w/ a random timestampfor (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 timestampif (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 classesand I put them on a priority_queue, but I don''t know how to get them inpriority. The priority is the event w/ the smallest timestamp.Normally a priority queue with n levels of priority can be modelled by asilgle linked list with a head and n tail pointers. The priority is infact 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 nearlyinfinite number of priority levels. So you need either random access tothe 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 beclose together compared to the queue depth a doubly linked list withlinear search from the back might be sufficient. You can use std::listfor 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 arenot characterized by the time only and giving them a ''greater than''semantic is not meaningful. I would pass a comparer function to theQueue either as template argument at compile time or as funtion pointeras constructor argument at run time.MarcelJoe, G.I. wrote: >Can anyone help me w/ a priority_queue. I''m generating MyEvent classesand I put them on a priority_queue, but I don''t know how to get them inpriority. 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 thanobfuscation. 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 BuxKai-Uwe Bux wrote: Joe, G.I. wrote: >>Can anyone help me w/ a priority_queue. I''m generating MyEvent classesand I put them on a priority_queue, but I don''t know how to get them inpriority. 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 thanobfuscation.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* notMyEvent.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帮助的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！