std::inplace_merge

Определено в заголовочном файле `<algorithm>`
template< class BidirIt > void inplace_merge( BidirIt first, BidirIt middle, BidirIt last );	(1)	(constexpr с C++26)
template< class ExecutionPolicy, class BidirIt > void inplace_merge( ExecutionPolicy&& policy, BidirIt first, BidirIt middle, BidirIt last );	(2)	(с C++17)
template< class BidirIt, class Compare > void inplace_merge( BidirIt first, BidirIt middle, BidirIt last, Compare comp );	(3)	(constexpr с C++26)
template< class ExecutionPolicy, class BidirIt, class Compare > void inplace_merge( ExecutionPolicy&& policy, BidirIt first, BidirIt middle, BidirIt last, Compare comp );	(4)	(с C++17)

Сливает два последовательных отсортированных диапазона [first, middle) и [middle, last) в один отсортированный диапазон [first, last).

1) Если [first, middle) или [middle, last) не отсортирован относительно operator<(до C++20)std::less{}(с C++20), поведение не определено.

3) Если [first, middle) или [middle, last) не отсортирован относительно comp, поведение не определено.

2,4) То же, что и (1,3), но выполняется согласно policy.

Эти перегрузки участвуют в разрешении перегрузки только в том случае, если значение следующего выражения равно true:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(с C++20)

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

Если выполняется любое из следующих условий, поведение не определено:

[first, middle) или [middle, last) не является допустимым диапазоном.

Тип `*first` не является Swappable.	(до C++11)
`BiditIt` не является ValueSwappable. Тип `first` не является MoveConstructible. Тип `first` не является MoveAssignable.	(с C++11)

Параметры

first	-	начало первого отсортированного диапазона
middle	-	конец первого отсортированного диапазона и начало второго
last	-	конец второго отсортированного диапазона
policy	-	политика выполнения, которая будет использоваться
comp	-	объект функции сравнения (то есть объект, удовлетворяющий требованиям Compare), который возвращает `true`, если первый аргумент меньше второго (то есть упорядочен перед ним). Сигнатура функции сравнения должна быть эквивалентна следующей: boolcmp(constType1&a,constType2&b); Хотя сигнатура не обязана содержать const&, функция не должна изменять переданные ей объекты и должна принимать любые значения типов (возможно, const) `Type1` и `Type2` независимо от категории значения (поэтому `Type1&` не допускается, как и `Type1`, за исключением случая, когда для `Type1` перемещение эквивалентно копированию(с C++11)). Типы Type1 и Type2 должны быть такими, чтобы объект типа BidirIt можно было разыменовать и затем неявно преобразовать в каждый из этих типов.
Требования к типам
-`BidirIt` должен удовлетворять требованиям LegacyBidirectionalIterator.
-`Compare` должен удовлетворять требованиям Compare.

Сложность

Пусть \(\scriptsize N\)N — это std::distance(first, last):

1) Ровно \(\scriptsize N-1\)N-1 сравнений с использованием operator<(до C++20)std::less{}(с C++20), если доступно достаточно дополнительной памяти; в противном случае — \(\scriptsize O(N \cdot \log(N))\)O(N⋅log(N)) сравнений.

2) \(\scriptsize O(N \cdot \log(N))\)O(N⋅log(N)) сравнений с использованием operator<(до C++20)std::less{}(с C++20).

3) Ровно \(\scriptsize N-1\)N-1 вызовов функции сравнения comp, если доступно достаточно дополнительной памяти; в противном случае — \(\scriptsize O(N \cdot \log(N))\)O(N⋅log(N)) вызовов.

4) \(\scriptsize O(N \cdot \log(N))\)O(N⋅log(N)) вызовов функции сравнения comp.

Исключения

Перегрузки с параметром шаблона с именем ExecutionPolicy сообщают об ошибках следующим образом:

Если выполнение функции, вызванной в рамках алгоритма, приводит к выбросу исключения и ExecutionPolicy является одной из стандартных политик, вызывается std::terminate. Для любого другого ExecutionPolicy поведение определяется реализацией.
Если алгоритму не удаётся выделить память, выбрасывается std::bad_alloc.

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

См. реализации в libstdc++ и libc++.

Примечания

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

Макрос проверки поддержки возможностей	Значение	Стандарт	Возможность
`__cpp_lib_constexpr_algorithms`	`202306L`	(C++26)	слияние inplace с constexpr (1), (3)

Пример

Следующий код представляет собой реализацию сортировки слиянием.

#include <algorithm>
#include <iostream>
#include <vector>

template<class Iter>
void merge_sort(Iter first, Iter last)
{
    if (last - first > 1)
    {
        Iter middle = first + (last - first) / 2;
        merge_sort(first, middle);
        merge_sort(middle, last);
        std::inplace_merge(first, middle, last);
    }
}

int main()
{
    std::vector<int> v{8, 2, -2, 0, 11, 11, 1, 7, 3};
    merge_sort(v.begin(), v.end());
    for (const auto& n : v)
        std::cout << n << ' ';
    std::cout << '\n';
}

Вывод:

-2 0 1 2 3 7 8 11 11

См. также

merge	сливает два отсортированных диапазона (шаблон функции и объект-функция алгоритма)
ranges::merge (C++20)
sort	сортирует диапазон элементов (шаблон функции и объект-функция алгоритма)
ranges::sort (C++20)
stable_sort	сортирует диапазон элементов, сохраняя относительный порядок эквивалентных элементов (шаблон функции и объект-функция алгоритма)
ranges::stable_sort (C++20)
ranges::inplace_merge (C++20)	сливает на месте два упорядоченных диапазона (объект-функция алгоритма)

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