std::inplace_merge — cppreference.com

Материал из cppreference.com

Определено в заголовочном файле `<algorithm>`
`template< class BidirIt > void inplace_merge( BidirIt first, BidirIt middle, BidirIt last );`	(1)
`template< class BidirIt, class Compare> void inplace_merge( BidirIt first, BidirIt middle, BidirIt last, Compare comp );`	(2)

Объединяет два последовательных отсортированы диапазонах [first, middle) и [middle, last) в один отсортированный диапазон [first, last). Порядок равных элементов гарантированно будет сохранена. Первый вариант используется operator< для сравнения элементов, вторая версия использует данную функцию сравнения comp.

Оригинал:

Merges two consecutive sorted ranges [first, middle) and [middle, last) into one sorted range [first, last). The order of equal elements is guaranteed to be preserved. The first version uses operator< to compare the elements, the second version uses the given comparison function comp.

Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

Параметры

first	—	В начале первого отсортированный диапазон Оригинал: the beginning of the first sorted range Текст был переведён автоматически используя Переводчик Google. Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
middle	—	К концу первого отсортированы диапазоне и в начале второго Оригинал: the end of the first sorted range and the beginning of the second Текст был переведён автоматически используя Переводчик Google. Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
last	—	К концу второго отсортированы диапазоне Оригинал: the end of the second sorted range Текст был переведён автоматически используя Переводчик Google. Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
comp	—	объект функции сравнения (т.е. объект, удовлетворяющий требованиям Compare), который возвращает `true`, если первый аргумент "меньше", чем второй. Определение сравнения должно быть эквивалентно: `bool cmp(const Type1 &a, const Type2 &b);` Использование `noexcept` (начиная с C++11) желательно но не обязательно. Параметры не обязаны передаваться по `const&`, но не должны модифицироваться. Они должны быть способны принимать все значения типа (даже `const`) `Type1` и `Type2` независимо от категории значений (таким образом, `Type1&` не допускается, равно как и `Type1`, если только для `Type1` перемещение не эквивалентно копированию (начиная с C++11)). Типы `Type1` и `Type2` должны быть таковы, что объект типа `BidirIt` может быть разыменован и затем неявно преобразован в оба из них.
Требования к типам
-`BidirIt` должен соответствовать требованиям `ValueSwappable` и `BidirectionalIterator`.
-The type of dereferenced `BidirIt` must meet the requirements of `MoveAssignable` and `MoveConstructible`.

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

(Нет)

Сложность

Именно N-1 сравнения, если достаточно дополнительной памяти доступно, в противном случае N·log(N) где N = std::distance(first, last).

Оригинал:

Exactly N-1 comparisons if enough additional memory is available, otherwise N·log(N) where N = std::distance(first, last).

Заметки

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

Оригинал:

This function attempts to allocate a temporary buffer, typically by calling std::get_temporary_buffer. If the allocation fails, the less efficient algorithm is chosen.

Пример

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

Оригинал:

The following code is an implementation of merge sort.

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

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(auto n : v) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
}

Вывод:

См. также

	объединяет два отсортированных диапазона (шаблон функции) [править]
	сортирует диапазон в порядке возрастания (шаблон функции) [править]
	сортирует диапазон элементов, сохраняя порядок между равными элементами (шаблон функции) [править]

Категории: