Re: priority queue
vaclavpich@atlas.cz wrote:
Hi all,
I want to now your opinion on interface of my priority_queue. I now
std has very good a priority_queue. But I couldn't use std. So I had
to write my.
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// example :
// this class has the same interface like std::priority_queue
template<
class _Ty, // type to store
class _Predicate = Less<_Ty>, // comparator
class _Container = Array<_Ty> //
class StlPriorityQueuePolicy
{
_Container m_Cont;
public:
// common interface :
push(const _Ty& val)
_Ty& top();
void pop();
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// class has only push and pop methods
template<
class _Ty, // type to store
class _Predicate = Less<_Ty>, // comparator
class _Container = Array<_Ty> //
class PushPopPriorityQueuePolicy : protected
StlPriorityQueuePolicy<_Ty, _Predicate, _Container >
{
typedef StlPriorityQueuePolicy<_Ty, _Predicate, _Container >
base;
public:
// common interface :
push(const _Ty& val){
base::push(val);
}
_Ty pop(){
if(base::is_empty()) throw exception;
_Ty elem = base::top();
base::pop();
return elem;
}
};
template<
class _Ty,
class _Predicate = Less<_Ty>,
class _Container = Array<_Ty>,
template<class, class, class> _PriorityQueuePolicy =
StlPriorityQueuePolicy<>
class PriorityQueue : public _PriorityQueuePolicy< _Ty, _Predicate,
_Container> {};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
I'm not sure that this is very clever interface. Maybe is complicated
to use.A lot of people know how to use std::priority_queue.It is good
but I prefer the second policy. I know about one disadvantige of
PushPopPriorityQueuePolicy. Pop method has to create an element which
return. In the other hand PushPopPriorityQueuePolicy is very simple to
use.
If you know better way to implement priority queue please can you show
me how.
Thank you.
The main problem is that it is impossible to make the pop() function
exception-safe. pop() returns the top object by value, so it has to
call a copy constructor inside the return statement. If that copy
constructor throws (for instance if you have a priority_queue<string>)
then even if you catch the exception and successfully deal with its
underlying cause, you can't recover the element returned by pop() since
it has already been removed from your priority_queue. What the standard
does is define two member functions: top() which returns a reference or
const reference to the top element and cannot throw; and pop() which
erases the top element and returns void.
Joe Gottman