Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

how portable is end iterator decrement?

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.

like image 689
ledokol Avatar asked Mar 16 '11 07:03

ledokol


People also ask

Can you decrement iterator end?

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.

Can you decrement end iterator C++?

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.

What is end () iterator?

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.

What happens if you increment the iterator past the end?

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.


1 Answers

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.

like image 192
In silico Avatar answered Oct 08 '22 10:10

In silico