stl inplace_merge

[sVasilich]

Добрый день всем.

Читаю описание функции inplace_merge:
http://www.cplusplus.com/reference/a...inplace_merge/

И не могу понять её смысла. Можете объяснить на пальцах что и для чего она делает? А лучше пример использования привести, так как тот что на сайте меня только сбивает с толку - для чего так делать?

[Пепел Феникса]

там же написан пример...

[sVasilich]

Ну и что происходит в том примере? Сортируем 2 массива, копируем их в один вектор и применяем к этому вектору inplace_merge(). На выходе получается один отсортированный массив... Не понимаю для чего это делалось. Ведь тоже самое получили бы, если бы к полученному вектору sort() применили...

[Пепел Феникса]

эта сортировка для сортированных массивов после обьединения как я понимаю.
поидее быстрее чем сортировка с нуля.

[sVasilich]

Спасибо, похоже что так и есть.

Чтобы уже до конца разобраться, ещё вопрос.

Из описания функции

Complexity
Linear in comparisons (N-1) if an internal buffer was used, NlogN otherwise (where N is the number elements in the range [first,last)).

Не понимаю что значит "если был использован внутренний буфер" (internal buffer was used)". В других случаях, так понимаю, сложность сравнима с sort(): N*logN.

[pproger]

2sVasilich
inplace_merge производит слияние 2-х отсортированных последовательностей. разница между merge и inplace_merge в том, что merge помещает результат слияния в новый контейнер, который не перекрывается с исходными.
inplace_merge же выполняет слияние 2-х диапазонов (которые лежат в одном контейнере), заменяя их отсортированной последовательностью.
Пример.
у тебя есть контейнер с содержимым
5 6 7 1 3 6 8 9
ты хочешь получить сортированный контейнер. т.к ты знаешь, что в этом контейнере у тебя содержатся 2 отсортированные последовательности
5 6 7
и
1 3 6 8 9
то вместо sort можешь использовать inplace_merge.
почему не использовать всегда sort? потому что временная сложность у inplace_merge - линейная. логарифмичной она становится тогда, когда нет доступной памяти, и как я понимаю, тут и вызывается тот же sort, либо его обобщенный аналог.

вывод? если нужно получить отсортированный контейнер из сортированных последовательностей, лучше вызывать inplace_merge. в лучшем случае это будет произведено за линейное время.


ПС. посмотрел реализацию inplace_merge в VC++, действительно выделяется буфер, равный длине максимальной последовательности.

Не понимаю что значит "если был использован внутренний буфер"

читай, как "если удалось выделить память, если отработал оператор new".

а насчет sort-а ошибся, в случае нехватки буфера там вызываются upper и lower_bound, которые и дают логарифмическую сложность