std::stack underflow checking

std::stack underflow checking

Post by Soukhonossenko Kiri » Fri, 14 Feb 2003 05:00:30



Hi!
Could someone explain to me why std::stack<>::top() function doesn't
throw "underflow" exception? Is it right design? Are there other
reasons besides performance?
Thanks, Kirill


      [ about comp.lang.c++.moderated. First time posters: do this! ]

 
 
 

std::stack underflow checking

Post by Ivan Vecerin » Sat, 15 Feb 2003 10:53:49



| Could someone explain to me why std::stack<>::top() function doesn't
| throw "underflow" exception?

What the C++ standard says is that std::stack<>::top() calls the
back() member function of the underlying container:
  value_type&       top()       { return c.back(); }
  const value_type& top() const { return c.back(); }
Because the back() method of some containers could provide its
own handling of the <container empty> case (such as throwing a
exception or returning a default value), it doesn't make sense
for the std::stack wrapper to do additional checks.

std::deque<> being the default container inside std::stack<>,
the question is now:
  Why does the back() method of std::deque (and all other
  standard sequence containers) not check for emptiness?

It's mostly a matter of not wanting to impose a performance
overhead on all library implementations. So the standard leaves the
behavior "undefined". This means that some library implementations
may actually throw an exception if the container is empty (and
some std libs allow this, sometimes in a special "checked" mode).
But portable code cannot rely on such support from the library.

| Is it right design? Are there other reasons besides performance?
   1) Maybe.           2) No.
"You don't pay for what you don't use" was the goal for C++.

--
 Ivan Vecerina, Dr. med.  <>  http://www.post1.com/~ivec
 Soft Dev Manger, xitact  <>  http://www.xitact.com
 Brainbench MVP for C++   <>  http://www.brainbench.com


      [ about comp.lang.c++.moderated. First time posters: do this! ]

 
 
 

std::stack underflow checking

Post by Randy Madd » Sat, 15 Feb 2003 11:25:18



> Hi!
> Could someone explain to me why std::stack<>::top() function doesn't
> throw "underflow" exception? Is it right design? Are there other
> reasons besides performance?
> Thanks, Kirill

23.1/7 says "begin() returns an iterator referring to the first
element in the container.  end() returns an iterator which is
the past-the-end value for the container.  If the container is
empty then begin() == end()."

24.1/5 says "The library never assumes that past-the-end values
are dereferencable.", and, "Dereferencable and past-the-end
values are always non-singular."

23.2.3.3 shows stack::top() implemented as return c.back(),
where c is the container used to instantiate the stack, which by
default is a deque.

23.1.1/12, table 68 illustrates back() as returning *--end().

So it looks like the upshot here is that top() on an empty stack
results in undefined behavior because it dereferences an
iterator that is not dereferencable.

As an interesting side note, the  Musser, Derge and Saini text
"STL Tutorial and Reference Guide, Second Edition" says that
stack::top() "Returns the element most recently pushed on the
stack.", but is silent about an empty stack.  That same text,
however, indicates that deque, list and vector can be used to
implement stack, and the description of back() for each of these
containers explicitly states that back() is undefined if the
container is empty.

I don't know why the explicit language from Musser et al didn't
make it into the Standard, nor why container operations that
return a reference are not defined to throw an exception if the
container is empty, but that's the way it is.  I believe that
you are probably correct that performance is the reason this
behavior exists, but OTOH leaving this check out of the STL just
means that users must do the check in their code instead.  I
don't see a whole lot of performance gain there except for code
that doesn't care about undefined behavior.

M*of the story:  If you don't check for a container being
empty before trying to access its elements then you are just
asking for undefined behavior.

Randy.


      [ about comp.lang.c++.moderated. First time posters: do this! ]

 
 
 

1. Stack Underflow error on some systems

A friend has a Windows program (written in Visual C++) that dies with a
"Stack Underflow" error on some PCs--laptops and 486SXs.

Has anyone seen this type of problem--"works fine on most PCs but fails
with a Stack Underflow error on some systems"?

Any pointers will be greatly appreciated.  Thanks...

-- Naba Barkakati

2. a couple questions about MSDN?

3. Stack Underflow!!!?? Please help!

4. How Many Apple's - keep coming

5. Stack Underflow

6. FS: IDEA Remote Controller Card & Software

7. Adding begin/end to std::queue & std::stack

8. Stratos 2000 ergonomics

9. std::getline(std::istream &, std::string &) and std::ifstream (and using decl.)

10. Why not std::map<std::string, std::string[] > ?

11. Defect Report: std::min and std::max not inheriting std::binary_function

12. std::stack: how to clear?

13. How to push non-sortable objects on std::stack