780. std::merge() specification incorrect/insufficient

Section: 26.8.6 [alg.merge] Status: C++11 Submitter: Daniel Krügler Opened: 2008-01-25 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [alg.merge].

View all issues with C++11 status.

Discussion:

Though issue 283 has fixed many open issues, it seems that some are still open:

Both 25.3.4 [lib.alg.merge] in 14882:2003 and 26.8.6 [alg.merge] in N2461 have no Requires element and the Effects element contains some requirements, which is probably editorial. Worse is that:

• no assignment requirements are specified (neither implicit nor explicit).
• the effects clause just speaks of "merges", which is badly worded near to a circular definition.
• p. 2 mentions a range [first, last), which is not defined by the function arguments or otherwise.
• p. 2 says "according to the ordering defined by comp" which is both incomplete (because this excludes the first variant with <) and redundant (because the following subordinate clause mentions comp again)

[ Post Summit Alisdair adds: ]

Suggest:

(where last is equal to next(result, distance(first1, last1) + distance(first2, last2)), such that resulting range will be sorted in non-decreasing order; that is, for every iterator i in [result,last) other than result, the condition *i < *prev(i) or, respectively, comp(*i, *prev(i)) will be false.

Note that this might still not be technically accurate in the case of InputIterators, depending on other resolutions working their way through the system (1011).

[ Post Summit Daniel adds: ]

If we want to use prev and next here (Note: merge is sufficiently satisfied with InputIterator) we should instead add more to 26 [algorithms] p. 6, but I can currently not propose any good wording for this.

[ Batavia (2009-05): ]

Pete points out the existing wording in [algorithms] p. 4 that permits the use of + in algorithm specifications.

Alisdair points out that that wording may not apply to input iterators.

Move to Review.

[ 2009-07 Frankfurt: ]

Move to Ready.

[ 2009-08-23 Daniel reopens: ]

The proposed wording must be rephrased, because the part

for every iterator i in [result,last) other than result, the condition *i < *(i - 1) or, respectively, comp(*i, *(i - 1)) will be false"

isn't meaningful, because the range [result,last) is that of a pure OutputIterator, which is not readable in general.

[Howard: Proposed wording updated by Daniel, status moved from Ready to Review.]

[ 2009-10 Santa Cruz: ]

Matt has some different words to propose. Those words have been moved into the proposed wording section, and the original proposed wording now appears here:

In 26.8.6 [alg.merge] replace p.1+ 2:

Effects: MergesCopies all the elements of the two sorted ranges [first1,last1) and [first2,last2) into the range [result,result + (last1 - first1) + (last2 - first2)) , such that resulting range will be sorted in non-decreasing order; that is for every pair of iterators i and j of either input ranges, where *i was copied to the output range before *j was copied to the output range, the condition *j < *i or, respectively, comp(*j, *i) will be false.

Requires:The resulting range shall not overlap with either of the original ranges. The list will be sorted in non-decreasing order according to the ordering defined by comp; that is, for every iterator i in [first,last) other than first, the condition *i < *(i - 1) or comp(*i, *(i - 1)) will be false.

[ 2010-02-10 Moved to Tentatively Ready after 5 positive votes on c++std-lib. ]

Proposed resolution:

Change 26.8.6 [alg.merge] 1 and 2:

1 Effects: Merges two sorted ranges [first1,last1) and [first2,last2) into the range [result, result + (last1 - first1) + (last2 - first2)).

Effects: Copies all the elements of the two ranges [first1,last1) and [first2,last2) into the range [result, result_last), where result_last is result + (last1 - first1) + (last2 - first2), such that the resulting range satisfies is_sorted(result, result_last) or is_sorted(result, result_last, comp), respectively.

2 Requires: The ranges [first1,last1) and [first2,last2) shall be sorted with respect to operator< or comp. The resulting range shall not overlap with either of the original ranges. The list will be sorted in non-decreasing order according to the ordering defined by comp; that is, for every iterator i in [first,last) other than first, the condition *i < *(i - 1) or comp(*i, *(i - 1)) will be false.

Change 26.8.6 [alg.merge] p. 6+7 as indicated [This ensures harmonization between inplace_merge and merge]

6 Effects: Merges two sorted consecutive ranges [first,middle) and [middle,last), putting the result of the merge into the range [first,last). The resulting range will be in non-decreasing order; that is, for every iterator i in [first,last) other than first, the condition *i < *(i - 1) or, respectively, comp(*i, *(i - 1)) will be false.

7 Requires: The ranges [first,middle) and [middle,last) shall be sorted with respect to operator< or comp. The type of *first shall satisfy the Swappable requirements (37), the MoveConstructible requirements (Table 33), and the the MoveAssignable requirements (Table 35).