priority queue

[vaclavpich]

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:riority_queue
template<
class _Ty, // type to store
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 PushPopPriorityQueuePolicy : protected
StlPriorityQueuePolicy<_Ty, _Predicate, _Container >
{
typedef StlPriorityQueuePolicy<_Ty, _Predicate, _Container >
base;
public:
// common interface :
push(const _Ty& val){
base:ush(val);
}
_Ty pop(){
if(base::is_empty()) throw exception;
_Ty elem = base::top();
base:op();
return elem;
}
};

template<
class _Ty,
class _Predicate = Less<_Ty>,
class _Container = Array<_Ty>,
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:riority_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.

 

[Joe Gottman]

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:riority_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:ush(val);
}
_Ty pop(){
if(base::is_empty()) throw exception;
_Ty elem = base::top();
base:op();
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:riority_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

 

[James Kanze]

[...]

The main problem is that it is impossible to make the pop()
function exception-safe.

For certain types. And a certain definition of "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.

It's important to realize the limitations of this idiom,
but it's also important to realize that they don't always apply.
Tom Cargill's article ("Exception Handling: a False Sense of
Security",
http://www.informit.com/content/images/020163371x/supplements/Exception_Handling_Article.html)
was important in making us realize the limitations, but as David
Abrahams points out in a footnote to "Exception-Safety in
Generic Components"
(http://www.boost.org/community/exception_safety.html),
"Probably the greatest impediment to a solution in Cargill's
case was an unfortunate combination of choices on his part: the
interface he chose for his container was incompatible with his
particular demands for safety. By changing either one he might
have solved the problem." The key is matching the interface to
the requirements. Is strong exception safety a requirement?
(It's rarely really necessary.) Do we need to support objects
whose copy constructor may throw? (Almost all of my queues only
contain pointers, and the copy constructor of a pointer can
never throw.)(

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.

What the standard does is overreact to a perceived problem.
There's nothing wrong with a pop which returns the value if the
copy constructor can't throw, or if you don't need the strong
exception safety guarantee (if e.g. the queue is going to be
destroyed as a result of stack unwinding due to the exception).