Just encountered decrement of end()
iterator in my company source codes and it looks strange for me. As far as I remember this was working on some platforms, but not for the others. Maybe I'm wrong, however I couldn't find anything useful in standard about that. Standard only says that end()
returns an iterator which is the past-the-end value, but is it guaranteed to be decrementable? How does code like that match the standard?
std::list<int>::iterator it = --l.end();
Thanks in advance.
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.
Decrementing an iterator in C++ All containers in C++ do not support all iterators. We can only decrement random access iterators and bidirectional iterators. But we cannot decrement forward iterators, input iterators, and output iterators.
Description. The C++ function std::vector::end() returns an iterator which points to past-the-end element in the vector container. The past-the-end element is the theoretical element that would follow the last element in the vector.
Obviously if the iterator is advanced past the last element inside the loop the comparison in the for-loop statement will evaluate to false and the loop will happily continue into undefined behaviour.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With