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.

More Related Contents:

  1. Why use iterators instead of array indices?
  2. Why are Standard iterator ranges [begin, end) instead of [begin, end]?
  3. What happens if you call erase() on a map element while iterating from begin to end?
  4. Removing item from vector while iterating?
  5. comparing iterators from different containers
  6. Why use non-member begin and end functions in C++11?
  7. Sorting a vector in descending order
  8. How are iterators and pointers related?
  9. What’s faster, iterating an STL vector with vector::iterator or with at()?
  10. What is the difference between const_iterator and non-const iterator in the C++ STL?
  11. What is an iterator’s default value?
  12. Custom Iterator in C++
  13. Why is “!=” used with iterators instead of “
  14. Can std::begin work with array parameters and if so, how?
  15. std::vector iterator invalidation
  16. Checking if an iterator is valid
  17. How does std::copy work with stream iterators
  18. Why does a push_back on an std::list change a reverse iterator initialized with rbegin?
  19. STL containers element destruction order
  20. Can raw pointers be used instead of iterators with STL algorithms for containers with linear storage?
  21. How to remove constness of const_iterator?
  22. What happens if you increment an iterator that is equal to the end iterator of an STL container
  23. Are const_iterators faster?
  24. How to check that the passed Iterator is a random access iterator?
  25. Do STL iterators guarantee validity after collection was changed?
  26. Incrementing iterators: Is ++it more efficient than it++? [duplicate]
  27. what is the difference between const_iterator and iterator? [duplicate]
  28. How to increment an iterator by 2?
  29. iterator for 2d vector
  30. How can I copy one map into another using std::copy?

Leave a Comment