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

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

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

1) Элементы сравниваются с помощью operator<, и диапазоны должны быть отсортированы относительно этого же компаратора.

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

2,4) Аналогично (1,3), но выполняется в соответствии с policy. Эти перегрузки не участвуют в решении перегрузки, если

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>` является `true`.	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>` является `true`.	(начиная с C++20)

Параметры

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

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

(нет)

Сложность

Учитывая N = std::distance(first, last),

1,3) Точно N - 1 сравнений, если доступно достаточно дополнительной памяти. Если память недостаточна, \(\scriptsize O(N log(N))\)O(N log(N)) сравнений.

2,4) \(\scriptsize O(N log(N))\)O(N log(N)) сравнений.

Исключения

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

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

Примечания

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

Макрос проверки наличия функции	Значение	Std	Функция
`__cpp_lib_constexpr_algorithms`	202306L		`constexpr` стабильное упорядочение

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

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

Пример

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

#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	объединяет два отсортированных диапазона (шаблон функции)
sort	сортирует диапазон в порядке возрастания (шаблон функции)
stable_sort	сортирует диапазон элементов, сохраняя порядок между равными элементами (шаблон функции)
ranges::inplace_merge (C++20)	объединяет два упорядоченных диапазона на месте (niebloid)

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