Форум программистов, компьютерный форум CyberForum.ru

inplace_merge - C++

Восстановить пароль Регистрация
 
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
21.07.2013, 09:03     inplace_merge #1
Не понятно что эта функция делает, написано что слияет две отсортированные последовательности, но как она слияет? Она ж вроде одну последовательность как бы сортирует?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// inplace_merge example
#include <iostream>     // std::cout
#include <algorithm>    // std::inplace_merge, std::sort, std::copy
#include <vector>       // std::vector
 
int main () {
  int first[] = {5,10,15,20,25};
  int second[] = {50,40,30,20,10};
  std::vector<int> v(10);
  std::vector<int>::iterator it;
 
  std::sort (first,first+5);
  std::sort (second,second+5);
 
  it=std::copy (first, first+5, v.begin());
     std::copy (second,second+5,it);
 
  //std::inplace_merge (v.begin(),v.begin()+5,v.end());
  std::sort(v.begin(),v.end());
  std::cout << "The resulting vector contains:";
  for (it=v.begin(); it!=v.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';
 
  return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
21.07.2013, 09:22     inplace_merge #2
А достаточно просто почитать доки:
Merges two consecutive sorted ranges: [first,middle) and [middle,last), putting the result into the combined sorted range [first,last).
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
21.07.2013, 09:28  [ТС]     inplace_merge #3
0x10, а какая разница? Они ж уже скопированы в последовательность, можно просто sort применить и все?
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
21.07.2013, 09:31     inplace_merge #4
ninja2, sort в худшем случае отработает за квадрат, inplace_merge - за N*log(N). Плюс, inplace_merge гарантирует, что не будут меняться местами одинаковые элементы, sort такой гарантии не дает, только stable_sort.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
21.07.2013, 09:34  [ТС]     inplace_merge #5
Отут от не понятно зачем
C++
1
std::inplace_merge (v.begin(),v.begin()+5,v.end());
copy вроде все и так скопировало?
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
21.07.2013, 09:35     inplace_merge #6
Не понял вопроса. Что именно "зачем"?
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
21.07.2013, 09:39  [ТС]     inplace_merge #7
Цитата Сообщение от 0x10 Посмотреть сообщение
Не понял вопроса. Что именно "зачем"?
Ну там параметры одного и того же вектора передаются, от вторым параметром v.begin()+5, можно ж и v.begin()+2 передать разницы то нету?
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
21.07.2013, 09:46     inplace_merge #8
Цитата Сообщение от ninja2 Посмотреть сообщение
можно ж и передать разницы то нету?
Пробовали? Последовательности должны быть упорядочены по возрастанию. Есили передать v.begin()+2, то это условие будет нарушено.
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
21.07.2013, 09:46     inplace_merge #9
Последовательность состоит из двух отсортированных частей. В случае примера в первом посте это
5, 10, 15, 20, 25 | 10, 20, 30, 40, 50

Границы этих частей и передаются.
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
21.07.2013, 09:49     inplace_merge #10
Удалил.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
21.07.2013, 09:50  [ТС]     inplace_merge #11
А толку от этой функции? Только что быстрее сортирует и все?
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
21.07.2013, 09:51     inplace_merge #12
Цитата Сообщение от ninja2 Посмотреть сообщение
А толку от этой функции? Только что быстрее сортирует и все?
В названии функции inplace_merge от слова "sort" одна буква r.
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
21.07.2013, 09:53     inplace_merge #13
Цитата Сообщение от alsav22 Посмотреть сообщение
Есили передать v.begin()+2
В этом случае, вторая последовательность: 15 20 25 10 20 30 40 50. Неупорядочена.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
21.07.2013, 09:54  [ТС]     inplace_merge #14
Цитата Сообщение от 0x10 Посмотреть сообщение
В названии функции inplace_merge от слова "sort" одна буква r.
Ну так она что просто слияет две отсортированные подпоследовательности одной какой нить общей последовательности в отсортированую последовательность и все. Практической пользы от нее мало, можно просто sort применить к вектору и все, чем заморачиваться?
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
21.07.2013, 09:59     inplace_merge #15
Ну ок, тут уже я загонять начинаю.
В случае, если у тебя в некоторой части программы заведомо есть две отсортированные последовательности, то объединить их лучше будет с использованием именно inplace_merge, потому что гарантировано будет не хуже sort.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
21.07.2013, 10:14  [ТС]     inplace_merge #16
0x10, Да похоже она редко когда используется, да и конец для двоих последовательностей нужно знать, да видно что редкая функция. Практической пользы от нее мало.

Добавлено через 12 минут
0x10, Все таки она сортировать должна, в книге токо глянул там написано, что если экземпляры рыб одного вида отсортированы по весу, то вы можете отсортировать весь вектор по весу применив implace_merge()
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
21.07.2013, 19:08     inplace_merge #17
ninja2, inplace_merge может O(n), sort - всегда O(N log(N))

Добавлено через 17 минут
+ в inplace_merge - двунаправленные итераторы, sort - только с произвольным доступом
Yandex
Объявления
21.07.2013, 19:08     inplace_merge
Ответ Создать тему
Опции темы

Текущее время: 05:22. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru