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

std::inplace_merge

Материал из cppreference.com
< cpp‎ | algorithm

 
 
Алгоритмы
Функции
Немодифицирующие линейные операции
Модифицирующие линейные операции
Разделение
Сортировка (на отсортированных промежутках)
Бинарный поиск (на отсортированных промежутках)
Множества (на отсортированных промежутках)
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.
Оригинал:
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 Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.

Содержание

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

first -
В начале первого отсортированный диапазон
Оригинал:
the beginning of the first sorted range
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.
middle -
К концу первого отсортированы диапазоне и в начале второго
Оригинал:
the end of the first sorted range and the beginning of the second
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.
last -
К концу второго отсортированы диапазоне
Оригинал:
the end of the second sorted range
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.
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.
Типы Type1 и Type2 должны быть таковы, что объект типа BidirIt может быть разыменован и затем неявно преобразован в оба из них. ​

Требования к типам
-
BidirIt должен соответствовать требованиям ValueSwappable and 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).
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.

[править] Заметки

Эта функция пытается выделить временный буфер, как правило, по телефону 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.
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.

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

Следующий код является осуществление сортировки слиянием .
Оригинал:
The following code is an implementation of merge sort.
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.

#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

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

слияние двух отсортированных диапазонах
Оригинал:
merges two sorted ranges
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.

(шаблон функции) [edit]
виды диапазон в порядке возрастания
Оригинал:
sorts a range into ascending order
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.

(шаблон функции) [edit]
виды диапазон элементов при сохранении порядка между равными элементами
Оригинал:
sorts a range of elements while preserving order between equal elements
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.

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