This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++11 status.
std::merge()
specification incorrect/insufficientSection: 27.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^{(i)} has fixed many open issues, it seems that some are still open:
Both 25.3.4 [lib.alg.merge] in 14882:2003 and 27.8.6 [alg.merge] in N2461 have no Requires element and the Effects element contains some requirements, which is probably editorial. Worse is that:
[first, last)
, which is not defined by the
function arguments or otherwise.
[ Post Summit Alisdair adds: ]
Suggest:
(where
last
is equal tonext(result, distance(first1, last1) + distance(first2, last2))
, such that resulting range will be sorted in non-decreasing order; that is, for every iteratori
in[result,last)
other thanresult
, 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 of
InputIterators
, depending on other resolutions working their way through the system (1011^{(i)}).
[ Post Summit Daniel adds: ]
If we want to use
prev
andnext
here (Note:merge
is sufficiently satisfied withInputIterator
) we should instead add more to 27 [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 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 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 27.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 iteratorsi
andj
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 befalse
.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 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 27.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)
, whereresult_last
isresult + (last1 - first1) + (last2 - first2)
, such that the resulting range satisfiesis_sorted(result, result_last)
oris_sorted(result, result_last, comp)
, respectively.2 Requires: The ranges
[first1,last1)
and[first2,last2)
shall be sorted with respect tooperator<
orcomp
. 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 bycomp
; that is, for every iteratori
in[first,last)
other thanfirst
, the condition*i < *(i - 1)
orcomp(*i, *(i - 1))
will befalse
.
Change 27.8.6 [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 iteratori
in[first,last)
other thanfirst
, 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 tooperator<
orcomp
. The type of*first
shall satisfy theSwappable
requirements (37), theMoveConstructible
requirements (Table 33), and the theMoveAssignable
requirements (Table 35).