Movatterモバイル変換

This page is a snapshot from the LWG issues list, see theLibrary Active Issues List for more information and the meaning ofC++11 status.

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

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

Priority:Not Prioritized

View all otherissues in [alg.merge].

View all issues withC++11 status.

Discussion:

Though issue283⁽ⁱ⁾ 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 N2461have 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 wordednear to a circular definition.
• p. 2 mentions a range[first, last), which is not defined by thefunction arguments or otherwise.
• p. 2 says "according to the ordering defined by comp" which is bothincomplete (becausethis excludes the first variant with <) and redundant (because thefollowing subordinateclause mentions comp again)

[Post Summit Alisdair adds:]

Suggest:

(wherelast is equal tonext(result, distance(first1, last1) +distance(first2, last2)), such that resulting range will be sorted innon-decreasing order; that is, for every iteratori in[result,last) otherthanresult, the condition*i < *prev(i) or, respectively,comp(*i,*prev(i)) will befalse.

Note that this might still not be technically accurate in the case ofInputIterators, depending on other resolutions working their way through thesystem (1011⁽ⁱ⁾).

[Post Summit Daniel adds:]

If we want to useprev andnext here (Note:mergeis sufficiently satisfied withInputIterator) we should insteadadd more to26[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. 4that 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 iteratori in[result,last) other thanresult, the condition*i < *(i - 1) or, respectively,comp(*i, *(i - 1)) will befalse"

isn't meaningful, because the range[result,last) is that of a pureOutputIterator, which is notreadable 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 intothe proposed wording section, and the original proposed wording now appearshere:

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

Effects:MergesCopies all the elements of thetwo 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-decreasingorder; that is for everypair of iteratorsi andj of either input ranges, where*i was copiedto the output rangebefore*j was copied to the output range, the condition*j < *i or,respectively,comp(*j, *i)will befalse.

Requires:The resulting range shall not overlap with eitherof the original ranges.The list will be sorted in non-decreasing order according to theordering defined bycomp; that is, for every iteratori in[first,last) other thanfirst,the condition*i < *(i - 1) orcomp(*i, *(i - 1)) will befalse.

[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:

1Effects: 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), whereresult_last isresult+ (last1 - first1) + (last2 - first2), such that the resultingrange satisfiesis_sorted(result, result_last) oris_sorted(result, result_last, comp), respectively.

2Requires:The ranges[first1,last1) and[first2,last2) shall be sorted with respect tooperator< orcomp. The resulting range shall not overlap with either of theoriginal ranges.The list will be sorted in non-decreasing order accordingto the ordering defined bycomp; that is, for every iteratoriin[first,last) other thanfirst, the condition*i <*(i - 1) orcomp(*i, *(i - 1)) will befalse.

Change 26.8.6[alg.merge] p. 6+7 as indicated[This ensures harmonizationbetweeninplace_merge andmerge]

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

7Requires:The ranges[first,middle) and[middle,last) shall be sorted with respect tooperator< orcomp. The type of*first shall satisfy theSwappable requirements (37), theMoveConstructiblerequirements (Table 33), and the theMoveAssignable requirements (Table35).