Joe Gottman
10/25/2008 11:02:00 PM
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