Section: 28.7.5 [alg.merge] Status: C++11 Submitter: Daniel Krügler Opened: 2008-01-25 Last modified: 2016-02-10
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 28.7.5 [alg.merge] in N2461 have no Requires element and the Effects element contains some requirements, which is probably editorial. Worse is that:
[ 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 28 [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 28.7.5 [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 28.7.5 [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 28.7.5 [alg.merge] p. 6+7 as indicated [This ensures harmonization between inplace_merge and merge]
6 Effects: Merges two
sortedconsecutive 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).