std::inplace_merge
Материал из cppreference.com
 |
Эта страница была переведена автоматически с английской версии вики используя Переводчик Google. Перевод может содержать ошибки и странные формулировки. Наведите курсор на текст, чтобы увидеть оригинал. Щёлкните здесь, чтобы увидеть английскую версию этой страницы. (Вы можете помочь в исправлении ошибок и улучшении перевода. Для инструкций перейдите по ссылке.) |
<metanoindex/>
<tbody> </tbody>| Определено в заголовочном файле <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, если первый аргумент "меньше", чем второй.Определение сравнения должно быть эквивалентно:
Использование |
| Требования к типам | ||
-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).Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
Заметки
Эта функция пытается выделить временный буфер, как правило, по телефону 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.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
Пример
Следующий код является осуществление сортировки слиянием .
Оригинал:
The following code is an implementation of merge sort.
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
Запустить этот код
#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
См. также
| объединяет два отсортированных диапазона (шаблон функции) | |
| сортирует диапазон в порядке возрастания (шаблон функции) | |
| сортирует диапазон элементов, сохраняя порядок между равными элементами (шаблон функции) |
