1.模板观念与函数模板
课程主要内容
- C++模板简介
- 泛型编程
- 容器
- 进阶
C++模板简介
generic types:泛型。type翻译为型别。型别更加的具体。
简单的例子：
int Max(int a, int b){
return (a > b) ? a : b;
}
long Max(long a, long b){
return (a > b) ? a : b;
}
...
===>
template<typename T>
T Max(T a, T b){
return (a > b) ? a : b;
}
在这个函数中，T是一个abstract type，generic type，不是一个具体的类型。
两种类模板
- 类模板(Class template)
- 函数模板(Function template)
模板声明的时候，并未给出函数或类的完整定义。只是提供了一个语法框架。
模板的实例化是从模板构建出一个真正的函数或类的过程，指定T真正型别的时候。
实例化（instantiation）
- 显式实例化，在代码中明确指定
- 隐式实例化，由编译器推导
C++函数模板
是指参数化的一族函数（不止一个）。
class 和 typename，在用作定义型别参数时，在语法上没有区别，但是在语义上有区别，建议使用typename。但是不能使用struct。
在使用Max模板函数时，不能使用不同型别的参数来调用。
用具体型别代替模板参数T的过程就叫做实例化，从而产生了一个模板实例。
模板被编译了两次
- 没有实例化之前，编译器会检查语法是否有错误。
- 实例化期间，编译器会检查调用是否合法。
参数推导
- 模板参数是由传递给模板函数的实参决定的。
- 不允许自动型别转换，每个T必须严格匹配。
Max(1, 2.0);
===>
Max(static_cast<double>(1), 2.0);//将1转换为double
Max<double>(1, 2.0);//编译器认为1为double
函数模板重载
函数模板也可以像普通函数一样被重载。普通函数可以和模板函数同同时存在（名称一样），当调用即符合普通函数的调用，又符合模板函数时，优先调用普通函数。
所有的重载版本的声明必须位于他们被调用位置之前。
2.类模板与操作符重载
类模板
类通过参数泛化，从而构建出一族不同型别的类实例。
类模板实参可以是某一型别或常量（仅限int或enum），而且可以带默认值。
一个例子
const std::size_t DefaultStackSize = 1024;
template<typename T, std::size_t n = DefaultStackSize>
class Stack{
public:
void Push(const T cosnt& element)；
int Pop(T& element);
int Top(T& element) cosnt;
private:
std::vector<T> m_Members;
std::size_t m_nMaxSize = n; //n是编译时的常量，n可以有默认值
};
类模板的声明
在类模板内部，T可以像其他型别一样，定义变量和成员函数。
除了Copy constructor之外，如果在类模板中需要使用到类本身，如operator=，应该使用完整的定义（Stack<T, n>）,而不能省略型别T。
Stack<T>& operator= (Stack<T, n> const &)
类模板的实现
template<typename T, std::size_t nMaxSize>
void Stack<T, nMaxSize>::Push(const T cosnt& element){ ... }
类模板的特化
允许对一个类模板的某些模板参数型别做特化。
特化的作用或好处
- 对于某种特殊的型别，可以做一些特别的优化或提供不同的处理方式。
- 避免在实例化类模板时引起一些可能产生的诡异行为。
特化一个类需要特化其所有参数化的成员函数。
template<>
class Stack<std::wstring>{ ... };
特化后可以添加新的成员函数，也可以改为使用list来存储Stack的内部实现。
偏特化
类模板被定义为：
template <typename T1, typename T2>
class MyClass{ ... };
- 偏特化为同样类型：
template <typename T> class MyClass<T, T> { ... };
- 偏特化部分模板参数为指定型别：
template <typename T> class MyClass<T, int> { ... };
- 偏特化为指针：
template <typename T1, typename T2>
class MyClass<T1*, T2*>{ ... };
| 使用 | 原型 |
|---|---|
| MyClass<int, float> obj; | MyClass<T1, T2> |
| MyClass<float, float> obj; | MyClass<T, T> |
| MyClass<float, int> obj; | MyClass<T, int> |
| MyClass<int, float> obj; | MyClass<T1, T2> |
如果不止一个偏特化同等程度地能够匹配某个调用，那么该调用具有二义性，编译会报错。
| 使用 | 原型 |
|---|---|
| MyClass<int, int> obj; | Error matches MyClass<T, T> and MyClass<T, int> |
| MyClass<int, int> obj; | Error matches MyClass<T, T> and MyClass<T1, T2> |
默认模板实参
类似于函数的默认参数，对于类模板而言也可以定义其模板参数的默认值，这些值就叫做默认模板参数。
C++操作符重载
- 不可以用operator定义一种新的操作符
- 对于内置型别，不能再用operator重载
- 可重载为非静态成员函数或静态全局函数，如果该全局函数需要访问类的private和protected成员，则需要声明为friend。
- 除了operator=，所有其他操作符重载均可以被子类继承。
3.泛型编程(Generic Programming)
概观
泛型编程是一种思想，是一种编程方法。在不同的语言表现方式不一样，在C++中使用模板的方式表现出来。
关联特性 Traits
什么是traits，以及为什么使用traits？
template<typename T>
T Sigma(const T* begin, const T* end){
T total = T();
while(end != begin){
total += *begin++;
}
return total;
}
char str[] = "abc";
int length = strlen(str);
char* p = str;
char* e = str + length;
printf("Sigma(str) = %d\n", Sigma(p, q)); //得到的结果溢出。
运行结果（溢出）：
Sigma(str) = 38
为每个Sigma函数的参数型别创建一种关联（association），关联的型别就是用来存储Sigma结果的型别。
这种关联可以看做是型别T的一种特性（characteristic of the type T），此种型别可以称作T的trait。
Trais可以实现为模板类，association则是针对每个具体型别T的特化。
template<typename T> class SigmaTraits{};
template<> class SigmaTraits<char>{
public: typedef int ReturnType;
};
template<> class SigmaTraits<short>{
public: typedef int ReturnType;
};
...
修改后的Sigma函数：
template<typename T>
typename SigmaTraits<T>::ReturnType Sigma(const T* begin, const T* end){
typedef SigmaTraits<T>::ReturnType ReturnType;
ReturnType total = ReturnType();
while(end != begin){
total += *begin++;
}
return total;
}
修改后的执行结果：
Sigma(str) = 294
虽然此时传入参数T的型别是char，但是返回类型是int。原因就是使用了Traits。
迭代器
迭代器是指泛化的指针，迭代器本身是一个对象，指向另外一个（可以被迭代的）对象。
在STL中迭代器是容器和算法之间的接口。
基本思想
- 分离算法和容器，不需要相互依赖。
- 粘合算法和容器，使得一种算法的实现可以运用到多种不同的容器上。
- 每种容器都有其对应的迭代器。
4.容器（上）
Vector
Vector是一种可以存放任意型别的动态数组，连续的内存空间。
#include<vector>//使用的时候，不要加.h
访问vector的元素：
- vector::at() //有数组越界检查，效率低。
- vector::operator[] //不检查，效率高。
删除vector的元素：
- clear：清除整个vector
- pop_back：弹出vector尾部元素
- erase：删除vector某一位置元素
v.erase(
std::remove_if(
v.begin(),
v.end(),
ContainsString(L"C++")
),
v.end());
std::remove_if函数返回了一个迭代器，需要删除的元素的位置，remove_if函数需要一个条件函数，条件函数是一个派生自std::unary_function的一个仿函数，返回true或false来决定该元素是否是否会被删除。
Deque
Deque是一种可以存放任意型别的双向队列。
Deque提供的函数与vector类似，新增了两个函数：
- push_front：在头部插入一个元素
- pop_front：在头部弹出一个元素
List
List是一种可以存放任意型别的双向链表（doubly linked list）。内存中地址不连续。
List的优势：
- List的优势在于其弹性，可以随意插入和删除元素，仅仅改变节点前项和后项的链接。
- 对于插入、删除和替换等，效率极高。
- 通常只改变链接，没有元素复制。
List的劣势：
- 只能以连续的方式存取List中的元素。
- 对于查找、随机存取等元素定位，效率低。
splice
list::splice实现list拼接的功能。将源list的内容部分或全部元素删除，拼插入到目的list。
函数有以下三种声明：
void splice ( iterator position, list<T,Allocator>& x );
void splice ( iterator position, list<T,Allocator>& x, iterator i );
void splice ( iterator position, list<T,Allocator>& x, iterator first, iterator last );
函数说明：在list间移动元素：
- 将x的元素移动到目的list的指定位置，高效的将他们插入到目的list并从x中删除。
- 目的list的大小会增加，增加的大小为插入元素的大小。x的大小相应的会减少同样的大小。
- 前两个函数不会涉及到元素的创建或销毁。第三个函数会.
- 指向被删除元素的迭代器会失效。
参数：
- position：目的list的位置，用来标明 插入位置。
- x ：源list。
- first,last：x里需要被移动的元素的迭代器。区间为[first, last)，包含first指向的元素，不包含last指向的元素。
