Issue 1205: Some algorithms could more clearly document their handling of empty ranges

1205. Some algorithms could more clearly document their handling of empty ranges

Section: 26 [algorithms] Status: C++11 Submitter: Alisdair Meredith Opened: 2009-09-13 Last modified: 2016-01-28

Priority: Not Prioritized

View other active issues in [algorithms].

View all other issues in [algorithms].

View all issues with C++11 status.

Discussion:

There are a number of algorithms whose result might depend on the handling of an empty range. In some cases the result is not clear, while in others it would help readers to clearly mention the result rather than require some subtle intuition of the supplied wording.

[alg.all_of]

Returns: true if pred(*i) is true for every iterator i in the range [first,last), ...

What does this mean if the range is empty?

I believe that we intend this to be true and suggest a non-normative note to clarify:

Add to p1 [alg.all_of]:

[Note: Returns true if [first,last) is empty. — end note]

[alg.none_of]

Returns: true if pred(*i) is false for every iterator i in the range [first,last), ...

What does this mean if the range empty?

I believe that we intend this to be true and suggest a non-normative note to clarify:

Add to p1 [alg.none_of]:

[Note: Returns true if [first,last) is empty. — end note]

[alg.any_of]

The specification for an empty range is actually fairly clear in this case, but a note wouldn't hurt and would be consistent with proposals for all_of/none_of algorithms.

Add to p1 [alg.any_of]:

[Note: Returns false if [first,last) is empty. — end note]

26.6.8 [alg.find.end]

what does this mean if [first2,last2) is empty?

I believe the wording suggests the algorithm should return last1 in this case, but am not 100% sure. Is this in fact the correct result anyway? Surely an empty range should always match and the naive expected result would be first1?

My proposed wording is a note to clarify the current semantic:

Add to p2 26.6.8 [alg.find.end]:

[Note: Returns last1 if [first2,last2) is empty. — end note]

I would prefer a normative wording treating empty ranges specially, but do not believe we can change semantics at this point in the process, unless existing implementations actually yield this result:

Alternative wording: (NOT a note)

Add to p2 26.6.8 [alg.find.end]:

Returns first1 if [first2,last2) is empty.

26.6.9 [alg.find.first.of]

The phrasing seems precise when [first2, last2) is empty, but a small note to confirm the reader's understanding might still help.

Add to p2 26.6.9 [alg.find.first.of]

[Note: Returns last1 if [first2,last2) is empty. — end note]

26.6.15 [alg.search]

What is the expected result if [first2, last2) is empty?

My proposed wording is a note to clarify the current semantic:

Add to p2 26.6.15 [alg.search]:

[Note: Returns last1 if [first2,last2) is empty. — end note]

Again, I would prefer a normative wording treating empty ranges specially, but do not believe we can change semantics at this point in the process, unless existing implementations actually yield this result:

Alternative wording: (NOT a note)

Add to p2 26.6.15 [alg.search]:

Returns first1 if [first2,last2) is empty.

26.8.5 [alg.partitions]

Is an empty range partitioned or not?

Proposed wording:

Add to p1 26.8.5 [alg.partitions]:

[Note: Returns true if [first,last) is empty. — end note]

26.8.7.2 [includes]

Returns: true if every element in the range [first2,last2) is contained in the range [first1,last1). ...

I really don't know what this means if [first2,last2) is empty. I could loosely guess that this implies empty ranges always match, and my proposed wording is to clarify exactly that:

Add to p1 26.8.7.2 [includes]:

[Note: Returns true if [first2,last2) is empty. — end note]

26.8.8.3 [pop.heap]

The effects clause is invalid if the range [first,last) is empty, unlike all the other heap alogorithms. The should be called out in the requirements.

Proposed wording:

Revise p2 26.8.8.3 [pop.heap]

Requires: The range [first,last) shall be a valid non-empty heap.

[Editorial] Reverse order of 26.8.8.3 [pop.heap] p1 and p2.

26.8.9 [alg.min.max]

minmax_element does not clearly specify behaviour for an empty range in the same way that min_element and max_element do.

Add to p31 26.8.9 [alg.min.max]:

Returns make_pair(first, first) if first == last.

26.8.11 [alg.lex.comparison]

The wording here seems quite clear, especially with the sample algorithm implementation. A note is recommended purely for consistency with the rest of these issue resolutions:

Add to p1 26.8.11 [alg.lex.comparison]:

[Note: An empty sequence is lexicographically less than any other non-empty sequence, but not to another empty sequence. — end note]

[ 2009-11-11 Howard changes Notes to Remarks and changed search to return first1 instead of last1. ]

[ 2009-11-11 Moved to Tentatively Ready after 5 positive votes on c++std-lib. ]

Proposed resolution:

Add to [alg.all_of]:

Remarks: Returns true if [first,last) is empty.

Add to [alg.any_of]:

Remarks: Returns false if [first,last) is empty.

Add to [alg.none_of]:

Remarks: Returns true if [first,last) is empty.

Add to 26.6.8 [alg.find.end]:

Remarks: Returns last1 if [first2,last2) is empty.

Add to 26.6.9 [alg.find.first.of]

Remarks: Returns last1 if [first2,last2) is empty.

Add to 26.6.15 [alg.search]:

Remarks: Returns first1 if [first2,last2) is empty.

Add to 26.8.5 [alg.partitions]:

Remarks: Returns true if [first,last) is empty.

Add to 26.8.7.2 [includes]:

Remarks: Returns true if [first2,last2) is empty.

Revise p2 26.8.8.3 [pop.heap]

Requires: The range [first,last) shall be a valid non-empty heap.

[Editorial]

Reverse order of 26.8.8.3 [pop.heap] p1 and p2.

Add to p35 26.8.9 [alg.min.max]:

template<class ForwardIterator, class Compare>
  pair<ForwardIterator, ForwardIterator>
    minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
Returns: make_pair(m, M), where m is the first iterator in [first,last) such that no iterator in the range refers to a smaller element, and where M is the last iterator in [first,last) such that no iterator in the range refers to a larger element. Returns make_pair(first, first) if first == last.

Add to 26.8.11 [alg.lex.comparison]:

Remarks: An empty sequence is lexicographically less than any other non-empty sequence, but not less than another empty sequence.