Difference between revisions of "cpp/algorithm/ranges/inplace merge"

Latest revision as of 04:31, 10 July 2024

Defined in header `<algorithm>`
Call signature
template< std::bidirectional_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity > requires std::sortable<I, Comp, Proj> I inplace_merge( I first, I middle, S last, Comp comp = {}, Proj proj = {} );	(1)	(since C++20) (constexpr since C++26)
template< ranges::bidirectional_range R, class Comp = ranges::less, class Proj = std::identity > requires std::sortable<ranges::iterator_t<R>, Comp, Proj> ranges::borrowed_iterator_t<R> inplace_merge( R&& r, ranges::iterator_t<R> middle, Comp comp = {}, Proj proj = {} );	(2)	(since C++20) (constexpr since C++26)

Merges two consecutive sorted ranges [first, middle) and [middle, last) into one sorted range [first, last).

A sequence is said to be sorted with respect to the comparator comp and projection proj if for any iterator it pointing to the sequence and any non-negative integer n such that it + n is a valid iterator pointing to an element of the sequence, std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it))) evaluates to false.

This merge function is stable, which means that for equivalent elements in the original two ranges, the elements from the first range (preserving their original order) precede the elements from the second range (preserving their original order).

1) Elements are compared using the given binary comparison function comp and projection object proj, and the ranges must be sorted with respect to the same.

2) Same as (1), but uses r as the range, as if using ranges::begin(r) as first, and ranges::end(r) as last.

The function-like entities described on this page are 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.

In practice, they may be implemented as function objects, or with special compiler extensions.

struct inplace_merge_fn
{
    template<std::bidirectional_iterator I, std::sentinel_for<I> S,
             class Comp = ranges::less, class Proj = std::identity>
    requires std::sortable<I, Comp, Proj>
    constexpr I operator()(I first, I middle, S last, Comp comp = {}, Proj proj = {}) const
    {
        I last_it = ranges::next(middle, last);
        inplace_merge_slow(first, middle, last_it,
                           ranges::distance(first, middle),
                           ranges::distance(middle, last_it),
                           std::ref(comp), std::ref(proj));
        return last_it;
    }
 
    template<ranges::bidirectional_range R, class Comp = ranges::less,
             class Proj = std::identity>
    requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
    constexpr ranges::borrowed_iterator_t<R>
        operator()(R&& r, ranges::iterator_t<R> middle,
                   Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), std::move(middle), ranges::end(r),
                       std::move(comp), std::move(proj));
    }
 
private:
    template<class I, class Comp, class Proj>
    static constexpr void inplace_merge_slow(I first, I middle, I last,
                                             std::iter_difference_t<I> n1,
                                             std::iter_difference_t<I> n2,
                                             Comp comp, Proj proj)
    {
        if (n1 == 0 || n2 == 0)
            return;
        if (n1 + n2 == 2 && comp(proj(*middle), proj(*first)))
        {
            ranges::iter_swap(first, middle);
            return;
        }
 
        I cut1 = first, cut2 = middle;
        std::iter_difference_t<I> d1{}, d2{};
 
        if (n1 > n2)
        {
            d1 = n1 / 2;
            ranges::advance(cut1, d1);
            cut2 = ranges::lower_bound(middle, last, *cut1,
                                       std::ref(comp), std::ref(proj));
            d2 = ranges::distance(middle, cut2);
        }
        else
        {
            d2 = n2 / 2;
            ranges::advance(cut2, d2);
            cut1 = ranges::upper_bound(first, middle, *cut2,
                                       std::ref(comp), std::ref(proj));
            d1 = ranges::distance(first, cut1);
        }
 
        I new_middle = ranges::rotate(cut1, middle, cut2);
        inplace_merge_slow(first, cut1, new_middle, d1, d2,
                           std::ref(comp), std::ref(proj));
        inplace_merge_slow(new_middle, cut2, last, n1 - d1, n2 - d2,
                           std::ref(comp), std::ref(proj));
    }
};
 
inline constexpr inplace_merge_fn inplace_merge {};

[edit] Example

Run this code

#include <algorithm>
#include <complex>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>
 
void print(auto const& v, auto const& rem, int middle = -1)
{
    for (int i{}; auto n : v)
        std::cout << (i++ == middle ? "│ " : "") << n << ' ';
    std::cout << rem << '\n';
}
 
template<std::random_access_iterator I, std::sentinel_for<I> S>
requires std::sortable<I>
void merge_sort(I first, S last)
{
    if (last - first > 1)
    {
        I middle{first + (last - first) / 2};
        merge_sort(first, middle);
        merge_sort(middle, last);
        std::ranges::inplace_merge(first, middle, last);
    }
}
 
int main()
{
    // custom merge-sort demo
    std::vector v{8, 2, 0, 4, 9, 8, 1, 7, 3};
    print(v, ": before sort");
    merge_sort(v.begin(), v.end());
    print(v, ": after sort\n");
 
    // merging with comparison function object and projection
    using CI = std::complex<int>;
    std::vector<CI> r{{0,1}, {0,2}, {0,3}, {1,1}, {1,2}};
    const auto middle{std::ranges::next(r.begin(), 3)};
    auto comp{std::ranges::less{}};
    auto proj{[](CI z) { return z.imag(); }};
 
    print(r, ": before merge", middle - r.begin());
    std::ranges::inplace_merge(r, middle, comp, proj);
    print(r, ": after merge");
}

Output:

8 2 0 4 9 8 1 7 3 : before sort
0 1 2 3 4 7 8 8 9 : after sort
 
(0,1) (0,2) (0,3) │ (1,1) (1,2) : before merge
(0,1) (1,1) (0,2) (1,2) (0,3) : after merge

[edit] See also

ranges::merge (C++20)	merges two sorted ranges (niebloid)[edit]
ranges::set_union (C++20)	computes the union of two sets (niebloid)[edit]
ranges::is_sorted (C++20)	checks whether a range is sorted into ascending order (niebloid)[edit]
ranges::sort (C++20)	sorts a range into ascending order (niebloid)[edit]
inplace_merge	merges two ordered ranges in-place (function template) [edit]

@@ Line 2: / Line 2: @@
 {{cpp/algorithm/ranges/navbar}}
 {{dcl begin}}
-{{dcl header | algorithm}}
+{{dcl header|algorithm}}
-{{dcl h | Call signature}}
+{{dcl h|Call signature}}
-{{dcl | num=1 | since=c++20 |1=
+{{dcla|anchor=no|num=1|since=c++20|constexpr=c++26|1=
 template< std::bidirectional_iterator I, std::sentinel_for<I> S,
            class Comp = ranges::less, class Proj = std::identity >
 requires std::sortable<I, Comp, Proj>
-I ranges::inplace_merge( I first, I middle, S last, Comp comp = {}, Proj proj = {} );
+    I inplace_merge( I first, I middle, S last,
+                     Comp comp = {}, Proj proj = {} );
 }}
-{{dcl | num=2 | since=c++20 |1=
+{{dcla|anchor=no|num=2|since=c++20|constexpr=c++26|1=
 template< ranges::bidirectional_range R, class Comp = ranges::less,
            class Proj = std::identity >
 requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
 ranges::borrowed_iterator_t<R>
-ranges::inplace_merge( R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {} );
+    inplace_merge( R&& r, ranges::iterator_t<R> middle,
+                   Comp comp = {}, Proj proj = {} );
 }}
 {{dcl end}}
-Merges two consecutive ''sorted'' ranges {{tt|[first, middle)}} and {{tt|[middle, last)}} into one ''sorted'' range {{tt|[first, last)}}.
+Merges two consecutive ''sorted'' ranges {{range|first|middle}} and {{range|middle|last}} into one ''sorted'' range {{range|first|last}}.
-A sequence is said to be ''sorted'' with respect to the comparator {{tt|comp}} and projection {{tt|proj}} if for any iterator {{tt|it}} pointing to the sequence and any non-negative integer {{tt|n}} such that {{tt|it + n}} is a valid iterator pointing to an element of the sequence, {{c|std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it)))}} evaluates to {{tt|false}}.
+A sequence is said to be ''sorted'' with respect to the comparator {{c|comp}} and projection {{c|proj}} if for any iterator {{tt|it}} pointing to the sequence and any non-negative integer {{tt|n}} such that {{tt|it + n}} is a valid iterator pointing to an element of the sequence, {{c|std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it)))}} evaluates to {{c|false}}.
 This merge function is ''stable'', which means that for equivalent elements in the original two ranges, the elements from the first range (preserving their original order) precede the elements from the second range (preserving their original order).
-@1@ Elements are compared using the given binary comparison function {{tt|comp}} and projection object {{tt|proj}}, and the ranges must be sorted with respect to the same.
+@1@ Elements are compared using the given binary comparison function {{c|comp}} and projection object {{c|proj}}, and the ranges must be sorted with respect to the same.
-@2@ Same as {{v|1}}, but uses {{tt|r}} as the range, as if using {{c|ranges::begin(r)}} as {{tt|first}}, and {{c|ranges::end(r)}} as {{tt|last}}.
+@2@ Same as {{v|1}}, but uses {{c|r}} as the range, as if using {{c|ranges::begin(r)}} as {{c|first}}, and {{c|ranges::end(r)}} as {{c|last}}.
 {{cpp/ranges/niebloid}}
@@ Line 33: / Line 35: @@
 ===Parameters===
 {{par begin}}
-{{par | first | the beginning of the first sorted range}}
+{{par|first|the beginning of the first sorted range}}
-{{par | middle | the end of the first range and the beginning of the second range}}
+{{par|middle|the end of the first range and the beginning of the second range}}
-{{par | last | the end of the second sorted range}}
+{{par|last|the end of the second sorted range}}
-{{par | r | the range of elements to merge inplace}}
+{{par|r|the range of elements to merge inplace}}
-{{par | comp | comparison to apply to the projected elements}}
+{{par|comp|comparison to apply to the projected elements}}
-{{par | proj | projection to apply to the elements in the range.}}
+{{par|proj|projection to apply to the elements in the range}}
 {{par end}}
 ===Return value===
-An iterator equal to {{tt|last}}.
+An iterator equal to {{c|last}}.
 ===Complexity===
-Exactly {{c|N−1}} comparisons, if additional memory buffer is available, where {{c|1= N = ranges::distance(first, last)}}. Otherwise, {{tt|𝓞(N•log(N))}} comparisons. Additionally, twice as many projections as comparisons in both cases.
+Exactly {{c|N − 1}} comparisons, if additional memory buffer is available, where {{c|1=N = ranges::distance(first, last)}}. Otherwise, {{mathjax-or|\(\scriptsize \mathcal{O}(N\cdot\log{(N)})\)|𝓞(N•log(N))}} comparisons. Additionally, twice as many projections as comparisons in both cases.
 ===Notes===
 This function attempts to allocate a temporary buffer. If the allocation fails, the less efficient algorithm is chosen.
-<!-- ===Possible implementation===
-Too bulky to be placed here. Later on add links to the flagships implementations.
+{{feature test macro|__cpp_lib_constexpr_algorithms|{{c/core|constexpr}} stable sorting|value=202306L|std=C++26}}
--->
+===Possible implementation===
+This implementation only shows the slower algorithm used when no additional memory is available. See also the implementation in [https://github.com/microsoft/STL/blob/e745bad3b1d05b5b19ec652d68abb37865ffa454/stl/inc/algorithm#L7131-L7235 MSVC STL] and [https://github.com/gcc-mirror/gcc/blob/54258e22b0846aaa6bd3265f592feb161eecda75/libstdc%2B%2B-v3/include/bits/ranges_algo.h#L2573-L2602 libstdc++].
+{{eq fun|1=<!--copied from libstdc++-->
+struct inplace_merge_fn
+{
+    template<std::bidirectional_iterator I, std::sentinel_for<I> S,
+             class Comp = ranges::less, class Proj = std::identity>
+    requires std::sortable<I, Comp, Proj>
+    constexpr I operator()(I first, I middle, S last, Comp comp = {}, Proj proj = {}) const
+    {
+        I last_it = ranges::next(middle, last);
+        inplace_merge_slow(first, middle, last_it,
+                           ranges::distance(first, middle),
+                           ranges::distance(middle, last_it),
+                           std::ref(comp), std::ref(proj));
+        return last_it;
+    }
+    template<ranges::bidirectional_range R, class Comp = ranges::less,
+             class Proj = std::identity>
+    requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
+    constexpr ranges::borrowed_iterator_t<R>
+        operator()(R&& r, ranges::iterator_t<R> middle,
+                   Comp comp = {}, Proj proj = {}) const
+    {
+        return (*this)(ranges::begin(r), std::move(middle), ranges::end(r),
+                       std::move(comp), std::move(proj));
+    }
+private:
+    template<class I, class Comp, class Proj>
+    static constexpr void inplace_merge_slow(I first, I middle, I last,
+                                             std::iter_difference_t<I> n1,
+                                             std::iter_difference_t<I> n2,
+                                             Comp comp, Proj proj)
+    {
+        if (n1 == 0 {{!!}} n2 == 0)
+            return;
+        if (n1 + n2 == 2 && comp(proj(*middle), proj(*first)))
+        {
+            ranges::iter_swap(first, middle);
+            return;
+        }
+        I cut1 = first, cut2 = middle;
+        std::iter_difference_t<I> d1{}, d2{};
+        if (n1 > n2)
+        {
+            d1 = n1 / 2;
+            ranges::advance(cut1, d1);
+            cut2 = ranges::lower_bound(middle, last, *cut1,
+                                       std::ref(comp), std::ref(proj));
+            d2 = ranges::distance(middle, cut2);
+        }
+        else
+        {
+            d2 = n2 / 2;
+            ranges::advance(cut2, d2);
+            cut1 = ranges::upper_bound(first, middle, *cut2,
+                                       std::ref(comp), std::ref(proj));
+            d1 = ranges::distance(first, cut1);
+        }
+        I new_middle = ranges::rotate(cut1, middle, cut2);
+        inplace_merge_slow(first, cut1, new_middle, d1, d2,
+                           std::ref(comp), std::ref(proj));
+        inplace_merge_slow(new_middle, cut2, last, n1 - d1, n2 - d2,
+                           std::ref(comp), std::ref(proj));
+    }
+};
+inline constexpr inplace_merge_fn inplace_merge {};
+}}
 ===Example===
 {{example
- | code=
+|code=
 #include <algorithm>
 #include <complex>
@@ Line 70: / Line 146: @@
 }
-template <std::random_access_iterator I, std::sentinel_for<I> S>
+template<std::random_access_iterator I, std::sentinel_for<I> S>
 requires std::sortable<I>
 void merge_sort(I first, S last)
 {
-     if (last - first > 1) {
+     if (last - first > 1)
-         I middle {first + (last - first) / 2};
+    {
+         I middle{first + (last - first) / 2};
          merge_sort(first, middle);
          merge_sort(middle, last);
@@ Line 85: / Line 162: @@
 {
      // custom merge-sort demo
-     std::vector v {8, 2, 0, 4, 9, 8, 1, 7, 3};
+     std::vector v{8, 2, 0, 4, 9, 8, 1, 7, 3};
      print(v, ": before sort");
      merge_sort(v.begin(), v.end());
@@ Line 92: / Line 169: @@
      // merging with comparison function object and projection
      using CI = std::complex<int>;
-     std::vector<CI> r { {0,1}, {0,2}, {0,3}, {1,1}, {1,2} };
+     std::vector<CI> r{{0,1}, {0,2}, {0,3}, {1,1}, {1,2}};
-     const auto middle { std::ranges::next(r.begin(), 3) };
+     const auto middle{std::ranges::next(r.begin(), 3)};
-     auto comp { std::ranges::less{} };
+     auto comp{std::ranges::less{}<!---->};
-     auto proj { [](CI z) { return z.imag(); } };
+     auto proj{[](CI z) { return z.imag(); }<!---->};
      print(r, ": before merge", middle - r.begin());
@@ Line 101: / Line 178: @@
      print(r, ": after merge");
 }
- | output=
+|output=
 2 0 4 9 8 1 7 3 : before sort
 1 2 3 4 7 8 8 9 : after sort
@@ Line 111: / Line 188: @@
 ===See also===
 {{dsc begin}}
-{{dsc inc | cpp/algorithm/ranges/dsc merge}}
+{{dsc inc|cpp/algorithm/ranges/dsc merge}}
-{{dsc inc | cpp/algorithm/ranges/dsc set_union}}
+{{dsc inc|cpp/algorithm/ranges/dsc set_union}}
-{{dsc inc | cpp/algorithm/ranges/dsc is_sorted}}
+{{dsc inc|cpp/algorithm/ranges/dsc is_sorted}}
-{{dsc inc | cpp/algorithm/ranges/dsc sort}}
+{{dsc inc|cpp/algorithm/ranges/dsc sort}}
-{{dsc inc | cpp/algorithm/dsc inplace_merge}}
+{{dsc inc|cpp/algorithm/dsc inplace_merge}}
 {{dsc end}}
 {{langlinks|de|es|fr|it|ja|pt|ru|zh}}

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)
Metaprogramming library (C++11)
Diagnostics library
General utilities library
Strings library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Numerics library
Localizations library
Input/output library
Filesystem library (C++17)
Regular expressions library (C++11)
Concurrency support library (C++11)
Execution support library (C++26)
Technical specifications
Symbols index
External libraries

first	-	the beginning of the first sorted range
middle	-	the end of the first range and the beginning of the second range
last	-	the end of the second sorted range
r	-	the range of elements to merge inplace
comp	-	comparison to apply to the projected elements
proj	-	projection to apply to the elements in the range

cppreference.com

Namespaces

Variants

Views

Actions

Difference between revisions of "cpp/algorithm/ranges/inplace merge"

Latest revision as of 04:31, 10 July 2024

Contents

[edit] Parameters

[edit] Return value

[edit] Complexity

[edit] Notes

[edit] Possible implementation

[edit] Example

[edit] See also

Navigation

Toolbox