2364. deque and vector pop_back don't specify iterator invalidation requirements

Section: 23.3.5.4 [deque.modifiers], 23.3.11.5 [vector.modifiers] Status: C++17 Submitter: Deskin Miller Opened: 2014-02-17 Last modified: 2017-07-30

Priority: 0

View other active issues in [deque.modifiers].

View all other issues in [deque.modifiers].

View all issues with C++17 status.

Discussion:

I think it's obvious that vector::pop_back invalidates the path-the-end iterator, but I cannot find language that says so to my satisfaction in the Standard. N3797 23.2.4 [sequence.reqmts] Table 101 lists a.pop_back() semantics as "Destroys the last element", but nowhere do I see this required to invalidate the end iterator (or iterators previously referring to the last element). [container.reqmts.general]/11 states "Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container." 23.3.11.5 [vector.modifiers]/3 says that each flavor of vector::erase "Invalidates iterators and references at or after the point of the erase", but pop_back isn't discussed, and it wasn't specified in terms of erase.

Similarly for std::deque, 23.2.4 [sequence.reqmts] Table 101 and [container.reqmts.general]/11 both apply. Yet 23.3.5.4 [deque.modifiers] likewise doesn't discuss pop_back nor pop_front. Furthermore paragraph 4 fails to specify the iterator-invalidation guarantees when erasing the first element but not the last.

Both std::vector and std::deque are in contrast to std::list, which says in 23.3.9.4 [list.modifiers]/3 regarding pop_back (as well as all forms of erase, pop_front, and clear) "Effects: Invalidates only the iterators and references to the erased elements."

[2014-06-16 Jonathan comments and improves wording]

I believe this reflects our preferred form discussed earlier, specifically putting the signatures with the erase signatures, so that the full specification of erase() applies to the pop_xxx() functions. This covers the case for deque where pop_front() erases the only element (which is both the first and last element).

Open question: the "erase" wording talks about "An erase operation" — are pop_front and pop_back clearly covered by "erase operations"? I believe so, as 23.3.5.1 [deque.overview]/1 and other places talk about "insert and erase operations" which covers push/pop functions too. I've added a note which could be used to clarify that if desired.

This wording is relative to N3936.

1. Change 23.3.5.4 [deque.modifiers] as indicated:

   iterator erase(const_iterator position);
   iterator erase(const_iterator first, const_iterator last);
   

   -4- Effects: An erase operation that erases the last element of a deque invalidates only the past-the-end iterator and all iterators and references to the erased elements. An erase operation that erases the first element of a deque but not the last element invalidates only iterators and references to the erased elements. An erase operation that erases neither the first element nor the last element of a deque invalidates the past-the-end iterator and all iterators and references to all the elements of the deque.

   -5- […]

   -6- […]

   void pop_front();
   void pop_back();
   

   -?- Effects: pop_front invalidates iterators and references to the first element of the deque. pop_back invalidates the past-the-end iterator, and all iterators and references to the last element of the deque.

2. Change 23.3.11.5 [vector.modifiers] as indicated:

   -5- […]

   void pop_back();
   

   -?- Effects: Invalidates the past-the-end iterator, and iterators and references to the last element of the vector.

[2014-06-21 Rapperswil]

Tony van Eerd: Would be good to define "an erase operation is ..." somewhere.

AM: The containers clause is known to be suboptimal in many ways.

Looks good

[Urbana 2014-11-07: Move to Ready]

Proposed resolution:

This wording is relative to N3936.

1. Change 23.3.5.4 [deque.modifiers] as indicated:

   iterator erase(const_iterator position);
   iterator erase(const_iterator first, const_iterator last);
   void pop_front();
   void pop_back();
   

   -4- Effects: An erase operation that erases the last element of a deque invalidates only the past-the-end iterator and all iterators and references to the erased elements. An erase operation that erases the first element of a deque but not the last element invalidates only iterators and references to the erased elements. An erase operation that erases neither the first element nor the last element of a deque invalidates the past-the-end iterator and all iterators and references to all the elements of the deque. [Note: pop_front and pop_back are erase operations — end note]

2. Change 23.3.11.5 [vector.modifiers] as indicated:

   iterator erase(const_iterator position);
   iterator erase(const_iterator first, const_iterator last);
   void pop_back();
   

   -3- Effects: Invalidates iterators and references at or after the point of the erase.