This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of Immediate status.

4464. §[alg.merge] Wording tweaks

Section: 26.8.6 [alg.merge] Status: Immediate Submitter: Ruslan Arutyunyan Opened: 2025-11-07 Last modified: 2025-11-08

Priority: Not Prioritized

View other active issues in [alg.merge].

View all other issues in [alg.merge].

View all issues with Immediate status.

Discussion:

The original text of the “US 163-262” issue says: “Bullets 1.3 and 1.4 and paragraph 3 should say E(e1, e2) instead of E(e1, e1)” in [alg.merge]. The problem, though, was introduced when merging P3179R9 “Parallel Range Algorithms” proposal. The original wording of P3179 does not have parentheses after E. Those extra parameters in E do not bring clarity to merge algorithm. The proposed resolution is to strike them through.

[Kona 2025-11-07; approved by LWG. Status changed: New → Immediate.]

Proposed resolution:

This wording is relative to N5014.

1. Modify 26.8.6 [alg.merge], as indicated:

   template<class InputIterator1, class InputIterator2,
            class OutputIterator>
     constexpr OutputIterator
       merge(InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2, InputIterator2 last2,
             OutputIterator result);
   […]
   template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
            sized-random-access-range OutR, class Comp = ranges::less,
            class Proj1 = identity, class Proj2 = identity>
     requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
     ranges::merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, borrowed_iterator_t<OutR>>
       ranges::merge(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r,
                     Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
   

   -1- Let:

   • (1.1) — N be: […]
   • (1.2) — comp be less{}, proj1 be identity{}, and proj2 be identity{}, for the overloads with no parameters by those names;
   • (1.3) — E(e1, e1) be bool(invoke(comp, invoke(proj2, e2), invoke(proj1, e1)));
   • (1.4) — K be the smallest integer in [0, last1 - first1) such that for the element e1 in the position first1 + K there are at least N − K elements e2 in [first2, last2) for which E(e1, e1) holds, and be equal to last1 - first1 if no such integer exists.

   -2- Preconditions: The ranges [first1, last1) and [first2, last2) are sorted with respect to comp and proj1 or proj2, respectively. The resulting range does not overlap with either of the original ranges.

   -3- Effects: Copies the first K elements of the range [first1, last1) and the first N − K elements of the range [first2, last2) into the range [result, result + N). If an element a precedes b in an input range, a is copied into the output range before b. If e1 is an element of [first1, last1) and e2 of [first2, last2), e2 is copied into the output range before e1 if and only if E(e1, e1) is true.