std::ranges::inplace_merge - cppreference.com (original) (raw)

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 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.

Contents

• 1 Parameters
• 2 Return value
• 3 Complexity
• 4 Notes
• 5 Possible implementation
• 6 Example
• 7 See also

[edit] Parameters

[edit] Return value

An iterator equal to last.

[edit] Complexity

Exactly N − 1 comparisons, if additional memory buffer is available, where N = ranges::distance(first, last). Otherwise, \(\scriptsize \mathcal{O}(N\cdot\log{(N)})\)𝓞(N•log(N)) comparisons. Additionally, twice as many projections as comparisons in both cases.

[edit] Notes

This function attempts to allocate a temporary buffer. If the allocation fails, the less efficient algorithm is chosen.

[edit] Possible implementation

This implementation only shows the slower algorithm used when no additional memory is available. See also the implementation in MSVC STL and libstdc++.

struct inplace_merge_fn { template<std::bidirectional_iterator I, std::sentinel_for 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, Comp, Proj> constexpr ranges::borrowed_iterator_t operator()(R&& r, ranges::iterator_t 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 n1, std::iter_difference_t 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 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

#include #include #include #include #include #include   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 S> requires std::sortable 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; std::vector 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