979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
||||||
1 | ||||||
inplace_merge21.07.2013, 09:03. Показов 2348. Ответов 16
Метки нет (Все метки)
Не понятно что эта функция делает, написано что слияет две отсортированные последовательности, но как она слияет? Она ж вроде одну последовательность как бы сортирует?
0
|
21.07.2013, 09:03 | |
Ответы с готовыми решениями:
16
inplace_merge Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
|
|
21.07.2013, 09:22 | 2 |
А достаточно просто почитать доки:
0
|
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
|
21.07.2013, 09:28 [ТС] | 3 |
0x10, а какая разница? Они ж уже скопированы в последовательность, можно просто sort применить и все?
0
|
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
|
|
21.07.2013, 09:31 | 4 |
ninja2, sort в худшем случае отработает за квадрат, inplace_merge - за N*log(N). Плюс, inplace_merge гарантирует, что не будут меняться местами одинаковые элементы, sort такой гарантии не дает, только stable_sort.
1
|
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
||||||
21.07.2013, 09:34 [ТС] | 5 | |||||
Отут от не понятно зачем
0
|
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
|
|
21.07.2013, 09:35 | 6 |
Не понял вопроса. Что именно "зачем"?
0
|
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
|
21.07.2013, 09:39 [ТС] | 7 |
Ну там параметры одного и того же вектора передаются, от вторым параметром v.begin()+5, можно ж и v.begin()+2 передать разницы то нету?
0
|
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
|
|
21.07.2013, 09:46 | 9 |
Последовательность состоит из двух отсортированных частей. В случае примера в первом посте это
5, 10, 15, 20, 25 | 10, 20, 30, 40, 50 Границы этих частей и передаются.
1
|
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
|
21.07.2013, 09:50 [ТС] | 11 |
А толку от этой функции? Только что быстрее сортирует и все?
0
|
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
|
|
21.07.2013, 09:51 | 12 |
2
|
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
|
21.07.2013, 09:54 [ТС] | 14 |
Ну так она что просто слияет две отсортированные подпоследовательности одной какой нить общей последовательности в отсортированую последовательность и все. Практической пользы от нее мало, можно просто sort применить к вектору и все, чем заморачиваться?
0
|
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
|
|
21.07.2013, 09:59 | 15 |
Ну ок, тут уже я загонять начинаю.
В случае, если у тебя в некоторой части программы заведомо есть две отсортированные последовательности, то объединить их лучше будет с использованием именно inplace_merge, потому что гарантировано будет не хуже sort.
1
|
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
|
21.07.2013, 10:14 [ТС] | 16 |
0x10, Да похоже она редко когда используется, да и конец для двоих последовательностей нужно знать, да видно что редкая функция. Практической пользы от нее мало.
Добавлено через 12 минут 0x10, Все таки она сортировать должна, в книге токо глянул там написано, что если экземпляры рыб одного вида отсортированы по весу, то вы можете отсортировать весь вектор по весу применив implace_merge()
0
|
What a waste!
1608 / 1300 / 180
Регистрация: 21.04.2012
Сообщений: 2,729
|
|
21.07.2013, 19:08 | 17 |
ninja2, inplace_merge может O(n), sort - всегда O(N log(N))
Добавлено через 17 минут + в inplace_merge - двунаправленные итераторы, sort - только с произвольным доступом
0
|
21.07.2013, 19:08 | |