Hi,

are there some rules for bidirectional iterators pointing to
container.end() ? Is it explicitely stated, that they could be
decremented (incremented) ?

If they cannot, then there are troubles with some algorightms, like:

copy_backward(src.begin(), src.end(), dst.end());

If they can, then there are serious performance problems. Eg. list
container implemented as double-linked list of items with NULLs as
'sentinels'. To handle end() operator++/--, iterator of list grows in
size and complexity, because it has to store the reference to its
container, and it has to test NULLs in
operator++/--. So such an iterator is much less efficient than one not
testing for .end().

Mirek
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Mirek Fidler <cxl@usa.net> writes:

> are there some rules for bidirectional iterators pointing to
> container.end() ? Is it explicitely stated, that they could be
> decremented (incremented) ?

Well, bidirectional iterator requirements
[lib.bidirectional.iterators]/1 have the following requirements for
the expression '--r':

pre: there exists s such that r == ++s.
post: s is dereferenceable.
      --(++r) == r.
      --r == --s implies r == s.
      &r == &--r.

The precondition means that _if_ you can reach the container.end() using
incrementation, then you must be able to decrement it. But it doesn't
say you can always do it. There are at least two possiblities when
you might not be able to do it:
  1) When the whole container is empty, that is, when
     container.begin() == container.end().

  2) When the container.end() returns a distinct object not reachable
     using ++r (I'm not sure if this is the same as a "singular"
     value for the iterator). This usually means there is no sense in
     talking about the "end" of the container, for example,
     if the container is circular without any distinguished "last"
     element.

For incrementation, container.end() is incrementable iff it's
dereferenceable, because precondition for ++r is that r is
dereferenceable. However, there is no way of knowing whether this is the
case using only the requirements for bidirectional iterators.
[lib.iterator.requirements]/5:

"The library never assumes that past-the-end values are dereferenceable."

> If they can, then there are serious performance problems. Eg. list
> container implemented as double-linked list of items with NULLs as
> 'sentinels'.

This means you shouldn't implement an STL double-linked list with NULLs
as "pointers to sentinel" - instead use a normal sentinel node in the
list (and preferably use circular lists).
--
   Esa Pulkkinen                        | C++ programmers do it virtually
   E-Mail:  esap@cs.tut.fi              | everywhere with class, resulting
   WWW   :  http://www.cs.tut.fi/~esap/ | in multiple inheritance.
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Mirek Fidler (cxl@usa.net) wrote:
: Hi,

: are there some rules for bidirectional iterators pointing to
: container.end() ? Is it explicitely stated, that they could be
: decremented (incremented) ?

Howdy,

According to the December 1996 ANSI draft standard, along with
the specifications of the forward iterator (i.e. bidirectional
iterator "inherits" the functionality of forward iterator),
--r, r--, and *r-- is supported.
Here's something from the draft that might make it a little more clearer:

 +------------------------------------------------------------------------+
  |expression   return type       operational       assertion/note        |
  |                                semantics      pre/post-condition      |
  +-----------------------------------------------------------------------+
  |--r        X&                              pre: there exists s such    |
  |                                           that r == ++s.              |
  |                                           post: s is dereferenceable. |
  |                                           --(++r) == r.               |
  |                                           --r == --s implies r == s.  |
  |                                           &r == &--r.                 |
  +-----------------------------------------------------------------------+
  |r--        convertible to     { X tmp = r;                             |
  |           const X&             --r;                                   |
  |                                return tmp;                            |
  |                              }                                        |
  +-----------------------------------------------------------------------+
  |*r--       convertible to T                                            |
  +-----------------------------------------------------------------------+

Hope this helps!
--
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]