Section: 26.6.15 [alg.search], 26.7.6 [alg.fill], 26.7.7 [alg.generate] Status: CD1 Submitter: Martin Sebor Opened: 2003-09-18 Last modified: 2016-01-28
Priority: Not Prioritized
View all other issues in [alg.search].
View all issues with CD1 status.
Discussion:
The complexity requirements for these function templates are incorrect (or don't even make sense) for negative n:
25.1.9, p7 (search_n):
Complexity: At most (last1 - first1) * count applications
of the corresponding predicate.
25.2.5, p3 (fill_n):
Complexity: Exactly last - first (or n) assignments.
25.2.6, p3 (generate_n):
Complexity: Exactly last - first (or n) assignments.
In addition, the Requirements or the Effects clauses for the latter two templates don't say anything about the behavior when n is negative.
Proposed resolution:
Change 25.1.9, p7 to
Complexity: At most (last1 - first1) * count applications of the corresponding predicate if count is positive, or 0 otherwise.
Change 25.2.5, p2 to
Effects: Assigns value through all the iterators in the range [first, last), or [first, first + n) if n is positive, none otherwise.
Change 25.2.5, p3 to:
Complexity: Exactly last - first (or n if n is positive, or 0 otherwise) assignments.
Change 25.2.6, p1 to (notice the correction for the misspelled "through"):
Effects: Invokes the function object genand assigns the return value of gen through all the iterators in the range [first, last), or [first, first + n) if n is positive, or [first, first) otherwise.
Change 25.2.6, p3 to:
Complexity: Exactly last - first (or n if n is positive, or 0 otherwise) assignments.
Rationale:
Informally, we want to say that whenever we see a negative number we treat it the same as if it were zero. We believe the above changes do that (although they may not be the minimal way of saying so). The LWG considered and rejected the alternative of saying that negative numbers are undefined behavior.