Section: 23.2.4 [sequence.reqmts] Status: NAD Submitter: Chris Jefferson Opened: 2005-09-14 Last modified: 2016-01-28
Priority: Not Prioritized
View other active issues in [sequence.reqmts].
View all other issues in [sequence.reqmts].
View all issues with NAD status.
Discussion:
Problem: There are a number of places in the C++ standard library where it is possible to write what appear to be sensible ways of calling functions, but which can cause problems in some (or all) implementations, as they cause the values given to the function to be changed in a way not specified in standard (and therefore not coded to correctly work). These fall into two similar categories.
1) Parameters taken by const reference can be changed during execution of the function
Examples:
Given std::vector<int> v:
v.insert(v.begin(), v[2]);
v[2] can be changed by moving elements of vector
Given std::list<int> l:
l.remove(*l.begin());
Will delete the first element, and then continue trying to access it. This is particularily vicious, as it will appear to work in almost all cases.
2) A range is given which changes during the execution of the function: Similarly,
v.insert(v.begin(), v.begin()+4, v.begin()+6);
This kind of problem has been partly covered in some cases. For example std::copy(first, last, result) states that result cannot be in the range [first, last). However, does this cover the case where result is a reverse_iterator built from some iterator in the range [first, last)? Also, std::copy would still break if result was reverse_iterator(last + 1), yet this is not forbidden by the standard
Solution:
One option would be to try to more carefully limit the requirements of each function. There are many functions which would have to be checked. However as has been shown in the std::copy case, this may be difficult. A simpler, more global option would be to somewhere insert text similar to:
If the execution of any function would change either any values passed by reference or any value in any range passed to a function in a way not defined in the definition of that function, the result is undefined.
Such code would have to at least cover chapters 23 and 25 (the sections I read through carefully). I can see no harm on applying it to much of the rest of the standard.
Some existing parts of the standard could be improved to fit with this, for example the requires for 25.2.1 (Copy) could be adjusted to:
Requires: For each non-negative integer n < (last - first), assigning to *(result + n) must not alter any value in the range [first + n, last).
However, this may add excessive complication.
One other benefit of clearly introducing this text is that it would allow a number of small optimisations, such as caching values passed by const reference.
Matt Austern adds that this issue also exists for the insert and
erase members of the ordered and unordered associative containers.
[ Berlin: Lots of controversey over how this should be solved. Lots of confusion as to whether we're talking about self referencing iterators or references. Needs a good survey as to the cases where this matters, for which implementations, and how expensive it is to fix each case. ]
Proposed resolution:
Rationale:
Recommend NAD.
vector::insert(iter, value) is required to work because the standard
doesn't give permission for it not to work.list::remove(value) is required to work because the standard
doesn't give permission for it not to work.vector::insert(iter, iter, iter) is not required to work because
23.2.4 [sequence.reqmts], p4 says so.copy has to work, except where 26.7.1 [alg.copy] says
it doesn't have to work. While a language lawyer can tear this wording apart,
it is felt that the wording is not prone to accidental interpretation.