std::inplace_merge

template< class BidirIt >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last );

template< class ExecutionPolicy, class BidirIt >
void inplace_merge( ExecutionPolicy&& policy,
                    BidirIt first, BidirIt middle, BidirIt last );

template< class BidirIt, class Compare >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last,
                    Compare comp );

template< class ExecutionPolicy, class BidirIt, class Compare >
void inplace_merge( ExecutionPolicy&& policy,
                    BidirIt first, BidirIt middle, BidirIt last,
                    Compare comp );

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

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

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

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

Параметры

Сложность

Пусть \(\scriptsize N\)N равно std::distance(first, last):

Исключения

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

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

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

Смотрите реализации в 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

Смотрите также