Почему компилятор ругается на использование шаблона (template)?

@Surges · Регистрация: 04.06.2013

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

C++

#include "stdafx.h"
#include <iostream>
#include <iomanip>
#include <chrono>
#include <ctime>
#include <thread>
#include <conio.h>
using namespace std;
template <typename T1, typename T2>                // шаблон(ы)
void quicksort(T2 a, T1 first, T1 last)
{
    int l = first; int r = last;
    int pivot = a[(l + r) / 2];
    while (l <= r)
    {
        while (a[l] < pivot)
            l++;
        while (a[r] > pivot)
            r--;
        if (l <= r) {
            swap(a[l], a[r]);
            l++;
            r--;
        }
    }
    if (first < r)
        quicksort(a, first, r);
    if (l < last)
        quicksort(a, l, last);
}
int main()
{
    const unsigned long size = 40000000;
    int n[size];
    for (int i = 0; i != size; i++)
    {
        n[i] = rand();
    }
    quicksort(n, 0, size - 1);                   // Красным подчеркивается здесь
    system("pause");
    return 0;
}

Если самому задать типы переменных, то программа идет как по маслу.
В чем моя ошибка?
Жду ответа с нетерпением.

@Serg_o_Grey · 10.04.2016, 15:31

чтобы массив добавить используйте T2 *a

@Surges · 10.04.2016, 15:42 **[ТС]**

Ser o Grey,
Ничего не изменилось

@Serg_o_Grey · 10.04.2016, 16:00

Surges, а у вас сейчас точно на template ругается?

Добавлено через 5 минут
а у вам не здесь случаем проблема
int n[size];

Добавлено через 7 минут
вы замечаете что в функции используете переменные не того типа?

@Surges · 10.04.2016, 16:02 **[ТС]**

Serg o Grey,
выводимый текст ошибок:

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

error C2672: 'quicksort': no matching overloaded function found
error C2782: 'void quicksort(T2 *,T1,T1)': template parameter 'T1' is ambiguous
error C2784: 'void quicksort(T2 *,T1,T1)': could not deduce template argument for 'T1' from 'unsigned long'

Из текста сообщений следует, что шаблон T1 не может догадаться, какой будет тип. Но разве это не очевидно, что должно быть "int" ?

@Serg_o_Grey · 10.04.2016, 16:07

const unsigned long nul = 0;
quicksort(n, nul, size - 1);

Добавлено через 1 минуту
правда у вас в программе есть еще ряд проблем, связанных с невозможностью функции распознать массив

@Surges · 10.04.2016, 16:13 **[ТС]**

Serg o Grey,
Большое спасибо, я понял, в чем было дело.

@hoggy · 10.04.2016, 16:14

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

В чем моя ошибка?

1.
массивы по значению не передаются.

2.

C++

1 2	const unsigned long size = 40000000; int n[size];

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

лекарство:
http://rextester.com/ZIVJH23566

C++

#include <iostream>
#include <climits>
#include <cassert>
#include <random>
#include <chrono>
 
 
 
//-------------------------------------------------------------------------        
//-------------------------------------------------------------------------        
//-------------------------------------------------------------------------        
int randomize(const int a = 0, const int b = INT_MAX)
{
    static std::default_random_engine gen(
        static_cast<unsigned>(
            std::chrono::system_clock::now().time_since_epoch().count()
        )
    );
    std::uniform_int_distribution<int> distribution(a, b);
    return distribution(gen);
}
//-------------------------------------------------------------------------        
//-------------------------------------------------------------------------        
//-------------------------------------------------------------------------        
    
template<class T> using baseArray 
    = typename std::remove_reference< 
        typename std::remove_const< 
            decltype(   std::declval<T>()[0]  ) 
        >::type 
    >::type;
 
//-------------------------------------------------------------------------        
//-------------------------------------------------------------------------        
//-------------------------------------------------------------------------        
 
 
template <typename T>   
void quicksort(T& a, const baseArray<T>& first, const baseArray<T>& last)
{
    const size_t size = sizeof(a)/sizeof(a[0]);
    assert(first<size && last < size);
    
    using type = baseArray<T>;
    
    type l = first; 
    type r = last;
    type pivot = a[(l + r) / 2];
    
    using std::swap;
    
    while (l <= r)
    {
        while (a[l] < pivot)
            l++;
        while (a[r] > pivot)
            r--;
        if (l <= r) {
            swap(a[l], a[r]);
            l++;
            r--;
        }
    }
    if (first < r)
        quicksort(a, first, r);
    if (l < last)
        quicksort(a, l, last);
}
    
    
int main()
{
    //const unsigned long size = 40000000;
    
    const unsigned long size = 40;
    int n[size];
    for (int i = 0; i != size; i++)
        n[i] = randomize();
    
    std::cout << "before:\n{";
    for(const auto& i: n)
        std::cout << i <<", ";
    std::cout << "};\n";
 
    quicksort(n, 0, size - 1); 
    
    std::cout << "\nafter:\n{";
    for(const auto& i: n)
        std::cout << i <<", ";
    std::cout << "};\n";
    
}

@Serg_o_Grey · 10.04.2016, 16:14

C++

// определяем внутри функции размер массива
 
#include <iostream>
 
using namespace std;
 
template <int N>
int getSizeArr(int (&a)[N])
{
    return sizeof(a);
}
 
int main() 
{ 
    int arr[10];
    for (int i = 0; i < 10; i++) arr[i] = 2;
    cout << sizeof(arr) <<endl;
    cout << getSizeArr(arr) << endl;
    cin.get();
    return 0;
}
 
 
 
////////////////////////////////////////////////////

Передача массива произвольного размера в функцию

Это можно сделать несколькими способами:

1. Использовать шаблоны. В таком случае заголовок функции будет выглядеть как

C++

1	template <int N> void trans (int (&matrix)[N][N]) // передача матрицы по ссылке

Использование:

C++

1 2	int m[5][5]; trans(m);

2. Использовать массив указателей на массивы:

C++

1	void trans (int **matrix, int n)

Использование:
1) Вариант 1 (статическое распределение памяти):

C++

1
2
3

int m1[5][5];
int* m[] = {m1[0], m1[1], m1[2], m1[3], m1[4]};
trans(m, 5);

2) Вариант 2 (динамическое распределение памяти):

C++

int** m = new int*[5];
for (int i=0; i<5; i++)
   m[i] = new int[5];
trans(m, 5);

3. Использовать STL:

C++

#include <vector>
typedef std::vector<int> row;
typedef std::vector<row> matrix;
void trans(matrix& mat);

Использование:

C++

1 2	matrix m(5, row(5)); trans(m);

------------------------------------------------

Достоинством первого метода является то, что компилятор сам определяет размеры массива (снижается число потенциальных ошибок).
Принципиальное достоинство второго метода - возможность работы с матрицами неуказанного при компиляции размера.
Третий метод обладает обоими достоинствами (безопасность и динамические размеры), но требует знания STL.

PS Первый и второй методы можно объединить:

C++

void trans (int **matrix, int n)
 
template <int N> inline void trans (int (&matrix)[N][N])
{
   int *m[N];
   for (int i=0; i<N; i++)
   m[i] = matrix[i];
   trans(m, N);
}

Здесь основная логика реализуется в функции, написанной по первому методу, но имеется также удобная шаблонная функция-обертка для статических матриц.

@DemolitionMan · 10.04.2016, 16:18

Какая у Вас версия того в чем Вы пишете? И вообще в чем Вы пишете?
Предполагаю, что нельзя писать две переменные типа в угловых скобках в шаблоне:

C++

1	template <typename T1, typename T2>

@Serg_o_Grey · 10.04.2016, 16:20

DemolitionMan, можно

@DemolitionMan · 10.04.2016, 16:23

Скажите, пожалуйста, Surges, в чем было дело?

@hoggy · 10.04.2016, 16:26

Surges,

так же, сам по себе алгоритм сортировки у вас работает не верно.
иногда случается вылет за пределы диапазона массива:

http://rextester.com/TXHF8438

C++

#include <iostream>
#include <climits>
#include <cassert>
#include <random>
#include <chrono>
 
//-------------------------------------------------------------------------        
//-------------------------------------------------------------------------        
int randomize(const int a = 0, const int b = INT_MAX)
{
    static std::default_random_engine gen(
        static_cast<unsigned>(
            std::chrono::system_clock::now().time_since_epoch().count()
        )
    );
    std::uniform_int_distribution<int> distribution(a, b);
    return distribution(gen);
}
//-------------------------------------------------------------------------        
//-------------------------------------------------------------------------        
 
template <typename T>   
void quicksort(T& a, const size_t first, const size_t& last)
{
    const auto size = sizeof(a)/sizeof(a[0]);
    assert(first<size && last < size);
    
    auto l = first; 
    auto r = last;
 
    const auto i = l + r /2;
    
    if(i>=size)
        std::cout <<"error: index of pivot out of range"<<std::endl;
    
    assert( i<size );
    auto pivot = a[(l + r) / 2];
    
    using std::swap;
    
    while (l <= r)
    {
        while (a[l] < pivot)
            l++;
        while (a[r] > pivot)
            r--;
        
        if(l>=size)
            std::cout <<"error: l out of range"<<std::endl;
        if(r>=size)
            std::cout <<"error: r out of range"<<std::endl;
        
        if (l <= r) {
            swap(a[l], a[r]);
            l++;
            r--;
        }
    }
    if (first < r)
        quicksort(a, first, r);
    if (l < last)
        quicksort(a, l, last);
}
    
    
int main()
{
    //const unsigned long size = 40000000;
    
    const unsigned long size = 40;
    int n[size];
    for (int i = 0; i != size; i++)
        n[i] = randomize();
    
    std::cout << "before:\n{";
    for(const auto& i: n)
        std::cout << i <<", ";
    std::cout << "};\n";
 
    quicksort(n, 0, size - 1); 
    
    std::cout << "\nafter:\n{";
    for(const auto& i: n)
        std::cout << i <<", ";
    std::cout << "};\n";
    
}

@Serg_o_Grey 116 / 106 / 51 Регистрация: 29.03.2016 Сообщений: 480
	10.04.2016, 16:20	11
	DemolitionMan, можно 0

@DemolitionMan 132 / 158 / 87 Регистрация: 06.04.2016 Сообщений: 992
	10.04.2016, 16:23	12
	Скажите, пожалуйста, Surges, в чем было дело? 0

Почему компилятор ругается на использование шаблона (template)?

Решение

Решение

@Serg_o_Grey 116 / 106 / 51 Регистрация: 29.03.2016 Сообщений: 480
	10.04.2016, 15:31	2
	чтобы массив добавить используйте T2 *a 0

@Surges 2 / 2 / 0 Регистрация: 04.06.2013 Сообщений: 44
	10.04.2016, 15:42 [ТС]	3
	Ser o Grey, Ничего не изменилось 0

@Serg_o_Grey 116 / 106 / 51 Регистрация: 29.03.2016 Сообщений: 480
	10.04.2016, 16:00	4
	Surges, а у вас сейчас точно на template ругается? Добавлено через 5 минут а у вам не здесь случаем проблема int n[size]; Добавлено через 7 минут вы замечаете что в функции используете переменные не того типа? 0

@Surges 2 / 2 / 0 Регистрация: 04.06.2013 Сообщений: 44
	10.04.2016, 16:02 [ТС]	5
	Serg o Grey, выводимый текст ошибок: Кликните здесь для просмотра всего текста error C2672: 'quicksort': no matching overloaded function found error C2782: 'void quicksort(T2 ,T1,T1)': template parameter 'T1' is ambiguous error C2784: 'void quicksort(T2 ,T1,T1)': could not deduce template argument for 'T1' from 'unsigned long' Из текста сообщений следует, что шаблон T1 не может догадаться, какой будет тип. Но разве это не очевидно, что должно быть "int" ? 0

@Serg_o_Grey 116 / 106 / 51 Регистрация: 29.03.2016 Сообщений: 480
	10.04.2016, 16:07	6
	Сообщение было отмечено Surges как решение Решение const unsigned long nul = 0; quicksort(n, nul, size - 1); Добавлено через 1 минуту правда у вас в программе есть еще ряд проблем, связанных с невозможностью функции распознать массив 1

@Surges 2 / 2 / 0 Регистрация: 04.06.2013 Сообщений: 44
	10.04.2016, 16:13 [ТС]	7
	Serg o Grey, Большое спасибо, я понял, в чем было дело. 0