Слияние массивов в упорядоченный массив

@Fortra · Регистрация: 14.12.2014

Студворк — интернет-сервис помощи студентам

выполнить слияние упорядоченного по возрастанию А(m) и неупорядоченного(n) массивов(n<<m) в упорядоченный по не убыванию массив С.

@hoggy · 16.12.2014, 02:49

http://rextester.com/SZKW83882

C++

#include <set>
#include <iostream>
 
 
template<size_t N, size_t M>
int (&merge(  const int (&a)[N], const int (&b)[M] )   )[N+M]
{
    ::std::multiset<int> s(a, a+N);
    s.insert(b, b+M);
    
    static int c[N+M];
    
    size_t n=0;
    for(const auto& e: s)
        c[n] = e,
        ++n;
   
    return c;
}
    
 
template<size_t N> 
::std::ostream& operator<< (::std::ostream& ss, const int (&ar)[N] )
{
    for(const auto& e: ar)
        ss<< e <<", ";
    return ss;
}
    
int main()
{
    std::cout << "Hello, world!\n";
    
    const int a[]= {1,2,3,4,5};
    const int b[]= {5,2,7,9};
    
    ::std::cout<< "array a: { "<< a <<"};\n";
    ::std::cout<< "array b: { "<< b <<"};\n";
    
    const auto& r = merge(a,b);
    
    ::std::cout<< "result : { "<< r <<"};\n";
}

@Fortra · 16.12.2014, 13:58 **[ТС]**

выполнить слияние упорядоченного по возрастанию А(m) и неупорядоченного(n) массивов(n<<m) в упорядоченный по не убыванию массив С.(НЕ ипользовать функции).

MrGluck · 16.12.2014, 14:28

Сообщение от Fortra

НЕ ипользовать функции

А main можно?

Добавлено через 1 минуту
Опишите пожалуйста, как вы предполагаете слияние неотсортированной последовательности с сортированной так, чтобы получилась опять же сортированная?

@Fortra · 16.12.2014, 14:29 **[ТС]**

да можна)

@~~tyreu~~ · 16.12.2014, 15:16

а что за template?

MrGluck · 16.12.2014, 15:42

Сообщение от tyreu

а что за template?

Ключевое слово. Здесь используется для того, чтобы можно было передавать массив в функцию, не указывая размер.

@~~tyreu~~ · 16.12.2014, 15:44

Интересно, спасибо

@Fortra · 16.12.2014, 23:19 **[ТС]**

а как понять
for(const auto& e: ar)
ss<< e <<", ";

@hoggy · 17.12.2014, 20:46

Сообщение от Fortra

НЕ ипользовать функции).

http://rextester.com/WOL1751

Кликните здесь для просмотра всего текста

C++

#include <set>
#include <iostream>
 
int main()
{
    ::std::cout << "Hello, world!\n";
    
    const int a[]= {1,2,3,4,5};
    ::std::cout<< "array a: { ";
    for(const auto& e: a)
        ::std::cout<< e <<", ";
    ::std::cout << "};\n";
    
 
    const int b[]= {5,2,7,9};    
    ::std::cout<< "array b: { ";
    for(const auto& e: b)
        ::std::cout<< e <<", ";
    ::std::cout << "};\n";
 
    enum { A = sizeof(a)/sizeof(a[0]) };
    enum { B = sizeof(b)/sizeof(b[0]) };
    enum { C = A + B };
    int c[C];
    
    
    ::std::multiset<int> s(a, a+A);
    s.insert(b, b+B);
    
    size_t n=0;
    for(const auto& e: s)
        c[n] = e,
        ++n;
    
    
    ::std::cout<< "result : { ";
    for(const auto& e: c)
        ::std::cout<< e <<", ";
    ::std::cout << "};\n";
    
}

Добавлено через 2 минуты

Сообщение от Fortra

а как понять
for(const auto& e: ar)
ss<< e <<", ";

Цикл по всей коллекции (в данном случае по всему массиву)

Здесь ar - массив, по которому нужно пробежаться
e - элемент массива, который вытаскивается из массива на каждом шаге цикла

а это инструкция, которую нужно выполнить над каждым элементом e

C++

1	ss<< e <<", ";

MrGluck · 18.12.2014, 19:18

Есть for цикл по коллекции, но почему-то по прежнему идёт вычисление количества элементов через деление размеров. Есть же std::begin + std::end. На статических массивах работает замечательно.

C++

1	std::multiset<int> s(std::begin(a), std::end(a));

@hoggy · 18.12.2014, 20:23

Сообщение от MrGluck

Есть же std::begin + std::end. На статических массивах работает замечательно.

Это - не принципиально.

Принципиально получить массив-результат-слияния.

C++

1 2	enum { C = A + B }; int c[C];

Что бы определить его размер, необходимо определить размеры исходных массивов.

MrGluck · 18.12.2014, 20:40

Сообщение от hoggy

Что бы определить его размер, необходимо определить размеры исходных массивов.

Или же использовать

C++

s.size()

(хоть это и бессмысленно)

@hoggy · 18.12.2014, 21:51

Сообщение от MrGluck

Или же использовать

на с++ размер массива должен быть известен времени компиляции.

MrGluck · 18.12.2014, 22:47

Сообщение от hoggy

на с++ размер массива должен быть известен времени компиляции.

Да что вы говорите

C++

1	int *c = new int[s.size()];

@hoggy · 18.12.2014, 23:26

Сообщение от MrGluck

Да что вы говорите
int *c = new int[s.size()];

Здесь нет массива.

MrGluck · 19.12.2014, 10:48

Сообщение от hoggy

Здесь нет массива.

Динамические массивы

В стандарте например это массивами называют.

5.3.4 New
8. <...> If the allocated type is an array type, the allocation
function’s name is operator new[] and the deallocation function’s name is operator delete[]. <...>

Ilot · 19.12.2014, 11:04

MrGluck, эм... а почему нет?:

C++

int a[M]; //<-sort
int b[N]; //<-unsort
int c[M + N];//<-out
std::sort(b, b + N);
std::merge(a, a + M, b, b + N, c) ;

MrGluck · 19.12.2014, 11:09

Сообщение от Ilot

MrGluck, эм... а почему нет?:

Не по теме:

Я хотел понять по какому алгоритму он предполагал сии действия, выразился некорректно (двусмысленно)

@hoggy · 19.12.2014, 12:58

Сообщение от MrGluck

В стандарте например это массивами называют.

выделение памяти под массив. Самого массива при этом нет. Есть операция выделения и указатель.

Добавлено через 3 минуты

Сообщение от Ilot

эм... а почему нет?:
int a[M]; //<-sort
int b[N]; //<-unsort
int c[M + N];//<-out
std::sort(b, b + N);
std::merge(a, a + M, b, b + N, c)

Потому что нужно сначала сделать слияние, и только потом сортировать.

@Fortra 0 / 0 / 0 Регистрация: 14.12.2014 Сообщений: 10
		1
	Слияние массивов в упорядоченный массив 16.12.2014, 01:40. Показов 2108. Ответов 31 Метки нет (Все метки) выполнить слияние упорядоченного по возрастанию А(m) и неупорядоченного(n) массивов(n<<m) в упорядоченный по не убыванию массив С. 0

@Fortra 0 / 0 / 0 Регистрация: 14.12.2014 Сообщений: 10
	16.12.2014, 13:58 [ТС]	3
	выполнить слияние упорядоченного по возрастанию А(m) и неупорядоченного(n) массивов(n<<m) в упорядоченный по не убыванию массив С.(НЕ ипользовать функции). 0

MrGluck Форумчанин 8215 / 5045 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	16.12.2014, 14:28	4
	Сообщение от Fortra НЕ ипользовать функции А main можно? Добавлено через 1 минуту Опишите пожалуйста, как вы предполагаете слияние неотсортированной последовательности с сортированной так, чтобы получилась опять же сортированная? 0

@Fortra 0 / 0 / 0 Регистрация: 14.12.2014 Сообщений: 10
	16.12.2014, 14:29 [ТС]	5
	да можна) 0

@~~tyreu~~ Заблокирован
	16.12.2014, 15:16	6
	а что за template? 0

MrGluck Форумчанин 8215 / 5045 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	16.12.2014, 15:42	7
	Сообщение от tyreu а что за template? Ключевое слово. Здесь используется для того, чтобы можно было передавать массив в функцию, не указывая размер. 0

@~~tyreu~~ Заблокирован
	16.12.2014, 15:44	8
	Интересно, спасибо 0

@Fortra 0 / 0 / 0 Регистрация: 14.12.2014 Сообщений: 10
	16.12.2014, 23:19 [ТС]	9
	а как понять for(const auto& e: ar) ss<< e <<", "; 0

@hoggy 8737 / 4315 / 960 Регистрация: 15.11.2014 Сообщений: 9,760
	18.12.2014, 21:51	14
	Сообщение от MrGluck Или же использовать на с++ размер массива должен быть известен времени компиляции. 0

@hoggy 8737 / 4315 / 960 Регистрация: 15.11.2014 Сообщений: 9,760
	18.12.2014, 23:26	16
	Сообщение от MrGluck Да что вы говорите int *c = new int[s.size()]; Здесь нет массива. 0

MrGluck Форумчанин 8215 / 5045 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	19.12.2014, 10:48	17
	Сообщение от hoggy Здесь нет массива. Динамические массивы В стандарте например это массивами называют. 5.3.4 New 8. <...> If the allocated type is an array type, the allocation function’s name is operator new[] and the deallocation function’s name is operator delete[]. <...> 0

MrGluck Форумчанин 8215 / 5045 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	19.12.2014, 11:09	19
	Сообщение от Ilot MrGluck, эм... а почему нет?: Не по теме: Я хотел понять по какому алгоритму он предполагал сии действия, выразился некорректно (двусмысленно) 0

@hoggy 8737 / 4315 / 960 Регистрация: 15.11.2014 Сообщений: 9,760
	19.12.2014, 12:58	20
	Сообщение от MrGluck В стандарте например это массивами называют. выделение памяти под массив. Самого массива при этом нет. Есть операция выделения и указатель. Добавлено через 3 минуты Сообщение от Ilot эм... а почему нет?: int a[M]; //<-sort int b[N]; //<-unsort int c[M + N];//<-out std::sort(b, b + N); std::merge(a, a + M, b, b + N, c) Потому что нужно сначала сделать слияние, и только потом сортировать. 0