std::ranges::merge, std::ranges::merge_result

Defined in header `<algorithm>`
Call signature
template< std::input_iterator I1, std::sentinel_for<I1> S1, std::input_iterator I2, std::sentinel_for<I2> S2, std::weakly_incrementable O, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2> constexpr ranges::merge_result<I1, I2, O> merge( I1 first1, S1 last1, I2 first2, S2 last2, O d_first, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(1)	(since C++20)
template< ranges::input_range R1, ranges::input_range R2, std::weakly_incrementable O, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>, O, Comp, Proj1, Proj2> constexpr ranges::merge_result<ranges::borrowed_iterator_t<R1>, ranges::borrowed_iterator_t<R2>, O> merge( R1&& r1, R2&& r2, O d_first, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(2)	(since C++20)
template< /execution-policy/ Ep, std::random_access_iterator I1, std::sized_sentinel_for<I1> S1, std::random_access_iterator I2, std::sized_sentinel_for<I2> S2, std::random_access_iterator O, std::sized_sentinel_for<O> OutS, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2> ranges::merge_result<I1, I2, O> merge( Ep&& policy, I1 first1, S1 last1, I2 first2, S2 last2, O d_first, OutS d_last, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(3)	(since C++26)
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 = std::identity, class Proj2 = std::identity > requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>, ranges::iterator_t<OutR>, Comp, Proj1, Proj2> ranges::merge_result<ranges::borrowed_iterator_t<R1>, ranges::borrowed_iterator_t<R2>, ranges::borrowed_iterator_t<OutR>> merge( Ep&& policy, R1&& r1, R2&& r2, OutR&& d_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(4)	(since C++26)
Helper types
template< class I1, class I2, class O > using merge_result = ranges::in_in_out_result<I1, I2, O>;	(5)	(since C++20)

For the definition of /*execution-policy*/, see this page; for the definition of /*sized-random-access-range*/, see this page.

Constructs a hypothetical sorted sequence containing all elements from two sorted source ranges. Copies elements of the sequence to the destination range.

1,2) All elements of the sequence will be copied to the destination range beginning at d_first.

For each group of equivalent elements in the sequence, any pair of elements from the group has the following order:

If the two elements are from the same source range, the order between them in the sequence follows the original order between them in the source range.
Otherwise, the element from the first source range is always placed before the element from the second source range.

1) The two source ranges are [first1, last1) and [first2, last2).

2) The two source ranges are r1 and r2.

3,4) Same as (1,2), but executed according to policy, and the destination range is [d_first, d_last) or d_r. If the destination range is exhausted, the remaining elements in the two source ranges will not be copied.

If any of the following conditions is satisfied, the behavior is undefined:

The first source range is not sorted with respect to the comparator comp and projection proj1.
The second source range is not sorted with respect to the comparator comp and projection proj2.
The destination range overlaps with any of the two source ranges.

The function-like entities described on this page are algorithm function objects (informally known as niebloids), that is:

Explicit template argument lists cannot be specified when calling any of them.
None of them are visible to argument-dependent lookup.
When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.

Parameters

first1, last1	-	the iterator-sentinel pair defining the first source range
r1	-	the first source range
first2, last2	-	the iterator-sentinel pair defining the second source range
r2	-	the second source range
d_first	-	the beginning of the destination range
d_last	-	the sentinel of the destination range
d_r	-	the destination range
comp	-	the comparator to be applied to the (projected) elements
proj1	-	the projection to be applied to the elements in the first source range
proj2	-	the projection to be applied to the elements in the second source range
policy	-	the execution policy to use

Return value

A ranges::merge_result object where:

The data member in1 holds an iterator to the first remaining element in the first source range, or the past-the-end iterator of the first source range if all elements of that range are copied.
The data member in2 holds an iterator to the first remaining element in the second source range, or the past-the-end iterator of the second source range if all elements of that range are copied.
The data member out holds the past-the-end iterator of the destination range.

Complexity

Given

$\scriptsize N_1$ $N 1$ as ranges::distance(first1, last1) or ranges::distance(r1),
$\scriptsize N_2$ $N 2$ as ranges::distance(first2, last2) or ranges::distance(r2),
$\scriptsize N_3$ $N 3$ as ranges::distance(d_first, d_last) or ranges::distance(d_r):

1,2) At most

N 1 +N 2 -1

applications of comp, proj1 and proj2.

3,4)

𝓞(min(N 1 +N 2,N 3))

applications of comp, proj1 and proj2.

Notes

This algorithm performs a similar task as ranges::set_union does. Both consume two sorted source ranges and produce a sorted output with elements from both inputs. The difference between these two algorithms is with handling values from both source ranges which compare equivalent (see notes on LessThanComparable).

If any equivalent values appeared n1 times in the first range and n2 times in the second, ranges::merge would output all n1 + n2 occurrences whereas ranges::set_union would output std::max(n1, n2) ones only. So ranges::merge outputs exactly ranges::distance(r1) + ranges::distance(r2) values and ranges::set_union may produce fewer.

Possible implementation

struct merge_fn
{
    template<std::input_iterator I1, std::sentinel_for<I1> S1,
             std::input_iterator I2, std::sentinel_for<I2> S2,
             std::weakly_incrementable O, class Comp = ranges::less,
             class Proj1 = std::identity, class Proj2 = std::identity>
        requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2>
    constexpr ranges::merge_result<I1, I2, O>
        operator()(I1 first1, S1 last1, I2 first2, S2 last2, O d_first,
                   Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        for (; !(first1 == last1 or first2 == last2); ++result)
        {
            if (std::invoke(comp, std::invoke(proj2, *first2),
                            std::invoke(proj1, *first1)))
                *d_first = *first2, ++first2;
            else
                *d_first = *first1, ++first1;
        }
        auto ret1{ranges::copy(std::move(first1), std::move(last1), std::move(result))};
        auto ret2{ranges::copy(std::move(first2), std::move(last2), std::move(ret1.out))};
        return {std::move(ret1.in), std::move(ret2.in), std::move(ret2.out)};
    }
    
    template<ranges::input_range R>
    constexpr get_end(R&& r)
    {
        return ranges::end(r);
    }
    
    template<ranges::forward_range R>
    constexpr get_end(R&& r)
    {
        return ranges::next(ranges::begin(r), ranges::end(r));
    }
    
    template<ranges::input_range R1, ranges::input_range R2,
             std::weakly_incrementable O, class Comp = ranges::less,
             class Proj1 = std::identity, class Proj2 = std::identity>
        requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>,
                                O, Comp, Proj1, Proj2>
    constexpr ranges::merge_result<ranges::borrowed_iterator_t<R1>,
                                   ranges::borrowed_iterator_t<R2>, O>
        operator()(R1&& r1, R2&& r2, O result,
                   Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (*this)(ranges::begin(r1), get_end(r1),
                       ranges::begin(r2), get_end(r2),
                       std::move(result), std::move(comp),
                       std::move(proj1), std::move(proj2));
    }
};

inline constexpr merge_fn merge{};

Example

Run this code

#include <algorithm>
#include <print>
#include <span>
#include <vector>

int main()
{
    std::vector<int> in1, in2, out;
    
    in1 = {1, 2, 3, 4, 5};
    in2 = {3, 4, 5, 6, 7};
    out.resize(in1.size() + in2.size());
    const auto ret = std::ranges::merge(in1, in2, out.begin());
    std::print("{} + {} =\n{}\n\n", in1, in2, std::span(out.begin(), ret.out));
    
    in1 = {1, 2, 3, 4, 5, 5, 5};
    in2 = {3, 4, 5, 6, 7};
    out.clear();
    out.reserve(in1.size() + in2.size());
    std::ranges::merge(in1, in2, std::back_inserter(out));
    std::print("{} + {} =\n{}\n", in1, in2, std::span(out.cbegin(), out.cend()));
}

Output:

[1, 2, 3, 4, 5] + [3, 4, 5, 6, 7] =
[1, 2, 3, 3, 4, 4, 5, 5, 6, 7]

[1, 2, 3, 4, 5, 5, 5] + [3, 4, 5, 6, 7] =
[1, 2, 3, 3, 4, 4, 5, 5, 5, 5, 6, 7]

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

merge	merges two sorted ranges (function template) [edit]
ranges::inplace_merge (C++20)	merges two ordered ranges in-place (algorithm function object)[edit]
ranges::is_sorted (C++20)	checks whether a range is sorted (algorithm function object)[edit]
ranges::set_union (C++20)	computes the union of two sets (algorithm function object)[edit]
ranges::sort (C++20)	sorts a range of elements (algorithm function object)[edit]
ranges::stable_sort (C++20)	sorts a range of elements while preserving relative order between equivalent elements (algorithm function object)[edit]

cppreference.com

Search

Namespaces

Variants

Views

Actions

std::ranges::merge, std::ranges::merge_result

Contents

Parameters

Return value

Complexity

Notes

Possible implementation

Example

See also

Navigation

Tools