std::ranges::inplace_merge

Определено в заголовке <algorithm>

Вызов сигнатуры

Определено в заголовке `<algorithm>`
Вызов сигнатуры
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)	(с C++20) (constexpr с 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)	(с C++20) (constexpr с C++26)

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)

(с C++20)
(constexpr с 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)

(с C++20)
(constexpr с C++26)

Объединяет две последовательные отсортированные диапазоны [first, middle) и [middle, last) в один отсортированный диапазон [first, last).

Последовательность считается отсортированной относительно компаратора comp и проекции proj, если для любого итератора it, указывающего на последовательность, и любого неотрицательного целого числа n, такого, что it + n является допустимым итератором, указывающим на элемент последовательности, std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it))) вычисляется как false.

Эта функция объединения стабильна, что означает, что для эквивалентных элементов в исходных двух диапазонах элементы из первого диапазона (сохраняя их исходный порядок) предшествуют элементам из второго диапазона (сохраняя их исходный порядок).

1) Элементы сравниваются с помощью заданной бинарной функции сравнения comp и объекта проекции proj, и диапазоны должны быть отсортированы относительно этого.

2) То же, что (1), но использует r в качестве диапазона, как если бы использовалось ranges::begin(r) как first, и ranges::end(r) как last.

Функциональные сущности, описанные на этой странице, являются неблокирующими, то есть:

Явные списки аргументов шаблона не могут быть указаны при вызове любого из них.
Ни один из них не виден для поиска аргументов по зависимости от аргументов.
Когда любой из них находится с помощью обычного поиска без указания имени как имя слева от оператора вызова функции, поиск аргументов по зависимости от аргументов ингибируется.

На практике они могут быть реализованы как объекты функций или с помощью специальных расширений компилятора.

Параметры

first	-	начало первого отсортированного диапазона
middle	-	конец первого диапазона и начало второго диапазона
last	-	конец второго отсортированного диапазона
r	-	диапазон элементов для объединения в месте
comp	-	сравнение для применения к спроецированным элементам
proj	-	проекция для применения к элементам в диапазоне

Возвращаемое значение

Итератор, равный last.

Сложность

Точно N − 1 сравнений, если доступен дополнительный буфер памяти, где N = ranges::distance(first, last). В противном случае, \(\scriptsize \mathcal{O}(N\cdot\log{(N)})\)𝓞(N•log(N)) сравнений. Кроме того, в обоих случаях вдвое больше проекций, чем сравнений.

Примечания

Эта функция пытается выделить временной буфер. Если выделение не удается, выбирается менее эффективный алгоритм.

Макрос проверки возможностей	Значение	Std	Возможность
`__cpp_lib_constexpr_algorithms`	202306L		`constexpr` стабильная сортировка

Возможная реализация

Эта реализация показывает только более медленный алгоритм, используемый, когда дополнительной памяти нет. Также см. реализацию в MSVC STL и 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 {};

Пример

#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");
}

Вывод:

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

См. также

ranges::merge (C++20)	объединяет два отсортированных диапазона (неблокирующий)
ranges::set_union (C++20)	вычисляет объединение двух множеств (неблокирующий)
ranges::is_sorted (C++20)	проверяет, отсортирован ли диапазон в порядке возрастания (неблокирующий)
ranges::sort (C++20)	сортирует диапазон в порядке возрастания (неблокирующий)
inplace_merge	объединяет два упорядоченных диапазона на месте (шаблон функции)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/algorithm/ranges/inplace_merge