算法库里的heap算法，仿函数和模版进阶（续）
文章目录
- 算法库里面的heap
- 仿函数
- 模版
- 非类型模版参数
- array
- 特化
- 函数模版的特化
- 类模版的特化
- 分离编译
算法库里面的heap
- sort_heap是算法库里的函数，前提要求是堆才能排序
- is_heap判断是否是堆
- make_heap建堆算法
int main()
{
int a[5] = { 10,19,27,39,19 };
std::vector<int> v(a, a + 5);
sort(a, a + 5);
// 虽然is_heap要求参数是迭代器，
// 但是可以是数组因为数组空间是连续的，原生指针也可以是天然的迭代器
cout << is_heap(v.begin(), v.end()) << endl;
cout << is_heap(a, a + 5) << endl;
make_heap(v.begin(), v.end());
// 默认建大堆
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
cout << is_heap(v.begin(), v.end()) << endl;
// 排的是升序
sort_heap(v.begin(), v.end());
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
return 0;
}
仿函数
greater< int >和less< int >是不需要我们自己写的，functional 这个头文件中包含有
有些场景需要我们自己写仿函数
- 类类型不支持比较大小
- 类类型支持比较大小，但比较的逻辑不是你想要的
底层是按指针比的，先new和后new的是随机的，它的逻辑比较大小不是你想要的，所以要自己写一个仿函数比较大小
// 正确写法
class DateLess
{
public:
bool operator()(Date* p1, Date* p2)
{
return *p1 < *p2;
}
};
wbc::priority_queue<Date*,vector<Date*>,DateLess> q2;
q2.push(new Date(2018, 1, 2));
q2.push(new Date(2018, 1, 3));
q2.push(new Date(2018, 1, 6));
cout << *q2.top() << endl;
q2.pop();
cout << *q2.top() << endl;
q2.pop();
cout << *q2.top() << endl;
q2.pop();
// 错误写法
wbc::priority_queue<Date*> q2;
q2.push(new Date(2018, 1, 2));
q2.push(new Date(2018, 1, 3));
q2.push(new Date(2018, 1, 6));
cout << *q2.top() << endl;
q2.pop();
cout << *q2.top() << endl;
q2.pop();
cout << *q2.top() << endl;
q2.pop();
模版
非类型模版参数
模版参数分为类型参数和非类型参数
非类型模版参数,只要给了非类类型就可以
非类型模版参数可以控制大小,但是它只能用于整形（int,usigned int,short,char,long,bool），其他类型都不可以
// #define N 5
// 对比#define就是可以令每个Stack的N大小不同
// 可以给缺省值
template<size_t N = 10>
class Stack
{
private:
int _a[N];
int _top;
};
//template<double P>
//class Stack
//{
//
//};
int main()
{
// 不给值这样写
Stack<> s0;
Stack<5> s1;
Stack<10> s2;
return 0;
}
C++20才支持double作为非类型的模版参数
array
array需要包array这个头文件
std::array是库里面的一个固定的数组
array在栈上开空间可以一次开出空间，开空间的效率比vector效率高
#include<array>
int main()
{
// std::array是库里面的一个固定的数组
// array的数据在栈上
array<int, 10> a1;
array<int, 20> a2;
// array 和我们写的数组有什么不同呢?
// 越界的检查机制不同
// a是静态数组，对越界的后两个标记位进行检查，对读不检查，对写会抽查
// 读
int a[10];
cout << a[10] << endl;
// 写,可以检查出来
// a[10] = 10;
// a[11] = 11;
// 检查不出来了
// a[12] = 20;
// a[20] = 30;
// array对读和写都检查
// array调用的是operator[],里面的assert强制检查了
// 而上面的a是指针解引用
// cout << a1[11] << endl;
// a1[20] = 10;
// 数据在堆上
vector<int> v(100, 1);
// sizeof算的是栈上的空间大小
// vector在栈上给了一个buff数组
cout << sizeof(v) << endl;
cout << sizeof(a1) << endl;
return 0;
}
特化
函数模版的特化
在原模版的基础上才有特化
函数模板的特化步骤：
- 必须要先有一个基础的函数模板
- 关键字template后面接一对空的尖括号<>
- 函数名后跟一对尖括号，尖括号中指定需要特化的类型
- 函数形参表: 必须要和模板函数的基础参数类型完全相同，如果不同编译器可能会报一些奇
怪的错误。
// 函数模版
template<class T>
bool lessfunc(const T& left,const T& right)
{
return left < right;
}
// 函数模版的特化
// Date*
template<>
bool lessfunc<Date*>(Date* const & left, Date* const & right)
{
return *left < *right;
}
// 函数模版的特化
// const Date*
template<>
bool lessfunc<const Date*>(const Date* const& left,const Date* const& right)
{
return *left < *right;
}
// 函数模版的特化
//template<>
//bool lessfunc<Date*>(Date* left, Date* right)
//{
// return *left < *right;
//}
// 建议直接写成函数的形式
//bool lessfunc(Date* left, Date* right)
//{
// return *left < *right;
//}
//bool lessfunc(const Date* left,const Date* right)
//{
// return *left < *right;
//}
int main()
{
Date d1(2018, 1, 3);
Date d2(2018, 1, 3);
cout << lessfunc(1, 2) << endl;
cout << lessfunc(d1, d2) << endl;
Date* p1 = &d1;
Date* p2 = &d2;
cout << lessfunc(p1, p2) << endl;
const Date* p3 = &d1;
const Date* p4 = &d2;
cout << lessfunc(p3, p4) << endl;
// 这两种const没有区别,都是修饰本身
int const i = 0;
const int j = 0;
// 这两种const没有区别,都是修饰本身
const int& k = i;
int const& p = j;
return 0;
}
类模版的特化
全特化指的是模版参数全都给了
偏特化/半特化是指模版参数给了部分
走的优先级：全特化 > 偏特化 > 模版
// 类模版
template<class T1, class T2>
class Data
{
public:
Data() { cout << "Data<T1, T2>" << endl; }
private:
T1 _d1;
T2 _d2;
};
// 半特化/偏特化
template<class T1>
class Data<T1, double>
{
public:
Data()
{
cout << "Data<T1,double>" << endl;
}
};
// 全特化
template<>
class Data<int, char>
{
public:
Data()
{
cout << "Data<int,char>" << endl;
}
};
template<class T1>
class Data<T1, char>
{
public:
Data() { cout << "Data<T1, char>" << endl; }
};
int main()
{
Data<int, int> d1;
// 有半特化在和全特化在走全特化
Data<int, char> d2;
Data<int, double> d3;
Data<int, double> d4;
return 0;
}
更进一步的参数限制
限制都是指针的参数
限制都是引用的参数
限制一个是指针一个是引用
// 偏特化
template<typename T1,typename T2>
class Data<T1*, T2*>
{
public:
Data() { cout << "Data<T1*, T2*>" << endl; }
};
template<typename T1, typename T2>
class Data<T1&, T2&>
{
public:
Data() { cout << "Data<T1&, T2&>" << endl; }
};
template<typename T1, typename T2>
class Data<T1*, T2&>
{
public:
Data() { cout << "Data<T1*, T2&>" << endl; }
};
Data<int*, char*> d5;
Data<int&, double&> d6;
Data<int*, double&> d7;
- 可以用偏特化解决Date*,比较的是指针的问题，转为比较指向的内容
// 偏特化
template<class T>
class Less<T*>
{
public:
bool operator()(T* const& x, T* const& y)
{
return *x < *y;
}
};
wbc::priority_queue<Date*,vector<Date*>,Less<Date*>> q2;
// wbc::priority_queue<Date*> q2;
q2.push(new Date(2018, 1, 2));
q2.push(new Date(2018, 1, 3));
q2.push(new Date(2018, 1, 6));
cout << *q2.top() << endl;
q2.pop();
cout << *q2.top() << endl;
q2.pop();
cout << *q2.top() << endl;
q2.pop();
wbc::priority_queue<int*> q3;
q3.push(new int(2));
q3.push(new int(1));
q3.push(new int(3));
cout << *q3.top() << endl;
q3.pop();
cout << *q3.top() << endl;
q3.pop();
cout << *q3.top() << endl;
q3.pop();
- 可以自己控制T1是引用还是指针，不用固定的传入
template<typename T1, typename T2>
class Data<T1*, T2&>
{
public:
Data()
{
cout << "Data<T1*, T2&>" << endl;
int a = 0;
T1* x = &a;
T2& y = a;
T1 c = a;
cout << typeid(x).name() << endl;
cout << typeid(y).name() << endl;
}
// void push(const T1& x);
};
Data<int*, int&> d7;
// T1->int
// T2->int
分离编译
模版不支持声明和定义分离，会导致链接错误
分离（.h和.cpp）
链接的时候通过符号表中的地址找到对应的函数
解决方法：
- 在.cpp文件中进行显示实例化
// 显示实例化
template
int Add(const int& left, const int& right);
template
double Add(const double& left, const double& right);
- 直接在.h中定义模版，用的地方直接有定义，直接实例化，都不需要链接(推荐实现这种)
// 直接在.h中定义
template<class T>
T Add(const T& left, const T& right)
{
cout << "Add(const T& left, const T& right)" << endl;
return left + right;
}