Пространства имён
Варианты
Действия

std::inplace_merge

Материал из cppreference.com
 
 
Алгоритмы
Функции
Немодифицирующие линейные операции
Модифицирующие линейные операции
Разделение
Сортировка (на отсортированных промежутках)
Бинарный поиск (на отсортированных промежутках)
Множества (на отсортированных промежутках)
merge
inplace_merge
includes
Куча
Минимум/максимум
Числовые операции
Библиотека C
 
Заголовочный файл <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.
Original:
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.
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

Содержание

[править] Параметры

first -
В начале первого отсортированный диапазон
Original:
the beginning of the first sorted range
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
middle -
К концу первого отсортированы диапазоне и в начале второго
Original:
the end of the first sorted range and the beginning of the second
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
last -
К концу второго отсортированы диапазоне
Original:
the end of the second sorted range
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
comp - comparison function which returns ​true if the first argument is less than the second.

The signature of the comparison function should be equivalent to the following:

bool cmp(const Type1 &a, const Type2 &b);

The signature does not need to have const &, but the function must not modify the objects passed to it.
The types  Type1 and  Type2 must be such that an object of type BidirIt can be dereferenced and then implicitly converted to both of them. ​

Type requirements
-
BidirIt must meet the requirements of ValueSwappable and BidirectionalIterator.
-
The type of dereferenced BidirIt must meet the requirements of MoveAssignable and MoveConstructible.

[править] Возвращаемое значение

(Нет)
Original:
(none)
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

[править] Сложность

Именно N-1 сравнения, если достаточно дополнительной памяти доступно, в противном случае N·log(N) где N = std::distance(first, last).
Original:
Exactly N-1 comparisons if enough additional memory is available, otherwise N·log(N) where N = std::distance(first, last).
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

[править] Notes

Эта функция пытается выделить временный буфер, как правило, по телефону std::get_temporary_buffer. Если распределение не удается, менее эффективный алгоритм выбрал.
Original:
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 text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

[править] Пример

Следующий код является осуществление сортировки слиянием .
Original:
The following code is an implementation of merge sort.
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

#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';
}

Вывод:

-2 0 1 2 3 7 8 11 11

[править] См. также

слияние двух отсортированных диапазонах
Original:
merges two sorted ranges
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

(шаблон функции) [edit]
виды диапазон в порядке возрастания
Original:
sorts a range into ascending order
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

(шаблон функции) [edit]
виды диапазон элементов при сохранении порядка между равными элементами
Original:
sorts a range of elements while preserving order between equal elements
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

(шаблон функции) [edit]