std::inplace_merge
Материал из cppreference.com
 |
Эта страница была переведена автоматически с английской версии вики используя Переводчик Google. Перевод может содержать ошибки и странные формулировки. Наведите курсор на текст, чтобы увидеть оригинал. Щёлкните здесь, чтобы увидеть английскую версию этой страницы. (Вы можете помочь в исправлении ошибок и улучшении перевода. Для инструкций перейдите по ссылке.) |
| Определено в заголовочном файле <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) |
| Требования к типам | ||
-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
[править] См. также
| объединяет два отсортированных диапазона (шаблон функции) | |
| сортирует диапазон в порядке возрастания (шаблон функции) | |
| сортирует диапазон элементов, сохраняя порядок между равными элементами (шаблон функции) |
