Re: priority queue
On Oct 26, 12:02 am, Joe Gottman <jgott...@carolina.rr.com> wrote:
[...]
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_Han=
dling_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).
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34