how portable is end iterator decrement?

by

I think this is the relevant clause:

ISO/IEC 14882:2003 C++ Standard 23.1.1/12 – Sequences

Table 68 lists sequence operations
that are provided for some types of
sequential containers but not others.
An implementation shall provide these
operations for all container types
shown in the “container” column, and
shall implement them so as to take
amortized constant time.

    +----------------------------------------------------------------------------+
    |                                  Table 68                                  |
    +--------------+-----------------+---------------------+---------------------+
    |  expression  |   return type   |     operational     |      container      |
    |              |                 |      semantics      |                     |
    +--------------+-----------------+---------------------+---------------------+
    | a.front()    | reference;      | *a.begin()          | vector, list, deque |
    |              | const_reference |                     |                     |
    |              | for constant a  |                     |                     |
    +--------------+-----------------+---------------------+---------------------+
    | a.back()     | reference;      | *--a.end()          | vector, list, deque |
    |              | const_reference |                     |                     |
    |              | for constant a  |                     |                     |
    ..............................................................................
    .              .                 .                     .                     .
    .              .                 .                     .                     .
    ..............................................................................
    | a.pop_back() | void            | a.erase(--a.end())  | vector, list, deque |
    ..............................................................................
    .              .                 .                     .                     .
    .              .                 .                     .                     .

So for the containers listed, not only should the iterator returned from end() be decrementable, the decremented iterator should also be dereferencable. (Unless the container is empty, of course. That invokes undefined behavior.)

In fact, vector, list and deque implementations that came with the Visual C++ compiler does it exactly like the table. Of course, that’s not to imply that every compiler does it like this:

// From VC++'s <list> implementation

reference back()
    {    // return last element of mutable sequence
    return (*(--end()));
    }

const_reference back() const
    {    // return last element of nonmutable sequence
    return (*(--end()));
    }

Note about the code in the table:

ISO/IEC 14882:2003 C++ Standard 17.3.1.2/6 – Requirements

In some cases the semantic
requirements are presented as C + +
code. Such code is intended as a
specification of equivalence of a
construct to another construct, not
necessarily as the way the construct
must be implemented.

So while it’s true that an implementation may not implement those expressions in terms of begin() and end(), the C++ standard specifies that the two expressions are equivalent. In other words, a.back() and *--a.end() are equivalent constructs according to the above clause. It seems to me that it means that you should be able to replace every instance of a.back() with *--a.end() and vice-versa and have the code still work.

According to Bo Persson, the revision of the C++ standard that I have on hand has a defect with respect to Table 68.

Proposed resolution:

Change the specification in table 68
“Optional Sequence Operations” in
23.1.1/12 for “a.back()” from

*--a.end()

to

{ iterator tmp = a.end(); --tmp; return *tmp; }

and the specification for
“a.pop_back()” from

a.erase(--a.end())

to

{ iterator tmp = a.end(); --tmp; a.erase(tmp); }

It appears that you can still decrement the iterator returned from end() and dereference the decremented iterator, as long as it’s not a temporary.

Leave a Comment

tech