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.

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

Section: 25.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 25.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 25 [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 25.8.6 [alg.merge] replace p.1+ 2:

> > > Effects: Merges Copies 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 25.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 25.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).