文件名称:
03.1编程范式之泛型编程.md
所在目录:
杂记 / 读书笔记 / 左耳听风
文件大小:
9.40 KB
下载地址:
文本预览:
# 编程范式之泛型编程
### C 语言的泛型
### 一个泛型的示例 - swap 函数
好了，我们再看下，C 语言是如何泛型的。C 语言的类型泛型基本上来说就是使用`void *`关键字或是使用宏定义。
下面是一个使用了`void*`泛型版本的 swap 函数。
```C
void swap(void* x, void* y, size_t size)
{
char tmp[size];
memcpy(tmp, y, size);
memcpy(y, x, size);
memcpy(x, tmp, size);
}
```
上面这个函数几乎完全改变了 int 版的函数的实现方式，这个实现方式有三个重点：
- **函数接口中增加了一个`size`参数**。为什么要这么干呢？因为，用了 `void*` 后，类型被“抽象”掉了，编译器不能通过类型得到类型的尺寸了，所以，需要我们手动地加上一个类型长度的标识。
- **函数的实现中使用了`memcpy()`函数**。为什么要这样干呢？还是因为类型被“抽象”掉了，所以不能用赋值表达式了，很有可能传进来的参数类型还是一个结构体，因此，为了要交换这些复杂类型的值，我们只能使用内存复制的方法了。
- **函数的实现中使用了一个`temp[size]`数组**。这就是交换数据时需要用的 buffer，用 buffer 来做临时的空间存储。
于是，新增的`size`参数，使用的`memcpy`内存拷贝以及一个 buffer，这增加了编程的复杂度。这就是 C 语言的类型抽象所带来的复杂度的提升。
在提升复杂度的同时，我们发现还有问题，比如，我们想交换两个字符串数组，类型是：`char*`，那么，我的`swap()`函数的`x`和`y`参数是不是要用`void**`了？这样一来，接口就没法定义了。
除了使用 `void*` 来做泛型，在 C 语言中，还可以用宏定义来做泛型，如下所示：
```c
#define swap(x, y, size) {\
char temp[size]; \
memcpy(temp, &y, size); \
memcpy(&y, &x, size); \
memcpy(&x, temp, size); \
}
```
但用宏带来的问题就是编译器做字符串替换，因为宏是做字符串替换，所以会导致代码膨胀，导致编译出的执行文件比较大。不过对于 swap 这个简单的函数来说，用`void*`和宏替换来说都可以达到泛型。
但是，如果我们不是 swap，而是 min() 或 max() 函数，那么宏替换的问题就会暴露得更多一些。比如，对于下面的这个宏：
```c
#define min(x, y) （(x)>(y) ? (y) : (x)）
```
其中一个最大的问题，就是有可能会有**重复执行**的问题。
### C++ 泛型编程
C++ 泛型版的代码：
```c++
template
Iter search(Iter pStart, Iter pEnd, T target)
{
for(Iter p = pStart; p != pEnd; p++) {
if ( *p == target )
return p;
}
return NULL;
}
```
在 C++ 的泛型版本中，我们可以看到：
- 使用`typename T`抽象了数据结构中存储数据的类型。
- 使用`typename Iter`，这是不同的数据结构需要自己实现的“迭代器”，这样也就抽象掉了不同类型的数据结构。
- 然后，我们对数据容器的遍历使用了`Iter`中的`++`方法，这是数据容器需要重载的操作符，这样通过操作符重载也就泛型掉了遍历。
- 在函数的入参上使用了`pStart`和`pEnd`来表示遍历的起止。
- 使用`*Iter`来取得这个“指针”的内容。这也是通过重载 `*` 取值操作符来达到的泛型。
### Go 泛型编程
go1.18开始可以支持泛型
```go
package main
import "fmt"
func find[T comparable] (arr []T, elem T) int {
for i, v := range arr {
if v == elem {
return i
}
}
return -1
}
```
Go语言的泛型已基本可用了，只不过，还有三个问题：
- 一个是 `fmt.Printf()`中的泛型类型是 `%v` 还不够好，不能像c++ `iostream`重载 `>>` 来获得程序自定义的输出。
- 另外一个是，go不支持操作符重载，所以，你也很难在泛型算法中使用“泛型操作符”如：`==` 等
- 最后一个是，上面的 `find()` 算法依赖于“数组”，对于hash-table、tree、graph、link等数据结构还要重写。也就是说，没有一个像C++ STL那样的一个泛型迭代器（这其中的一部分工作当然也需要通过重载操作符（如：`++` 来实现）
### Java泛型编程
```java
//此处T可以随便写为任意标识，常见的如T、E、K、V等形式的参数常用于表示泛型
//在实例化泛型类时，必须指定T的具体类型
public class Generic{
//key这个成员变量的类型为T,T的类型由外部指定
private T key;
public Generic(T key) { //泛型构造方法形参key的类型也为T，T的类型由外部指定
this.key = key;
}
public T getKey(){ //泛型方法getKey的返回值类型为T，T的类型由外部指定
return key;
}
}
```
### 类型系统
在计算机科学中，类型系统用于定义如何将编程语言中的数值和表达式归类为许多不同的类型，以及如何操作这些类型，还有这些类型如何互相作用。类型可以确认一个值或者一组值具有特定的意义和目的。
一般来说，编程语言会有两种类型，一种是内建类型，如 int、float 和 char 等，一种是抽象类型，如 struct、class 和 function 等。抽象类型在程序运行中，可能不表示为值。类型系统在各种语言之间有非常大的不同，也许，最主要的差异存在于编译时期的语法，以及运行时期的操作实现方式。
编译器可能使用值的静态类型以最优化所需的存储区，并选取对数值运算时的最佳算法。例如，在许多 C 编译器中，“浮点数”数据类型是以 32 比特表示、与 IEEE 754 规格一致的单精度浮点数。因此，在数值运算上，C 应用了浮点数规范（浮点数加法、乘法等）。
类型的约束程度以及评估方法，影响了语言的类型。更进一步，编程语言可能就类型多态性部分，对每一个类型都对应了一个针对于这个类型的算法运算。类型理论研究类型系统，尽管实际的编程语言类型系统，起源于计算机架构的实际问题、编译器实现，以及语言设计。
程序语言的类型系统主要提供如下的功能。
- **程序语言的安全性**。使用类型可以让编译器侦测一些代码的错误。例如：可以识别出一个错误无效的表达式。如：`“Hello, World” + 3`这样的不同数据类型间操作的问题。强类型语言提供更多的安全性，但是并不能保证绝对的安全。
- **利于编译器的优化**。 静态类型语言的类型声明，可以让编译器明确地知道程序员的意图。因此，编译器就可以利用这一信息做很多代码优化工作。例如：如果我们指定一个类型是 `int` ，那么编译就知道，这个类型会以 4 个字节的倍数进行对齐，编译器就可以非常有效地利用更有效率的机器指令。
- **代码的可读性**。有类型的编程语言，可以让代码更易读和更易维护。代码的语义也更清楚，代码模块的接口（如函数）也更丰富和清楚。
- **抽象化**。类型允许程序设计者对程序以较高层次的方式思考，而不是烦人的低层次实现。例如，我们使用整型或是浮点型来取代底层的字节实现，我们可以将字符串设计成一个值，而不是底层字节的数组。从高层上来说，类型可以用来定义不同模块间的交互协议，比如函数的入参类型和返回类型，从而可以让接口更有语义，而且不同的模块数据交换更为直观和易懂。
但是，正如前面说的，**类型带来的问题就是我们作用于不同类型的代码，虽然长得非常相似，但是由于类型的问题需要根据不同版本写出不同的算法，如果要做到泛型，就需要涉及比较底层的玩法**。
### 泛型的本质
要了解泛型的本质，就需要了解类型的本质。
- 类型是对内存的一种抽象。不同的类型，会有不同的内存布局和内存分配的策略。
- 不同的类型，有不同的操作。所以，对于特定的类型，也有特定的一组操作。
所以，要做到泛型，我们需要做下面的事情。
- 标准化掉类型的内存分配、释放和访问。
- 标准化掉类型的操作。比如：比较操作，I/O 操作，复制操作……
- 标准化掉数据容器的操作。比如：查找算法、过滤算法、聚合算法……
- 标准化掉类型上特有的操作。需要有标准化的接口来回调不同类型的具体操作……
所以，C++ 动用了非常繁多和复杂的技术来达到泛型编程的目标。
- 通过类中的构造、析构、拷贝构造，重载赋值操作符，标准化（隐藏）了类型的内存分配、释放和复制的操作。
- 通过重载操作符，可以标准化类型的比较等操作。
- 通过 iostream，标准化了类型的输入输出控制。
- 通过模板技术（包括模板的特化），来为不同的类型生成类型专属的代码。
- 通过迭代器来标准化数据容器的遍历操作。
- 通过面向对象的接口依赖（虚函数技术），来标准化了特定类型在特定算法上的操作。
- 通过函数式（函数对象），来标准化对于不同类型的特定操作。
我理解其本质就是 —— **屏蔽掉数据和操作数据的细节，让算法更为通用，让编程者更多地关注算法的结构，而不是在算法中处理不同的数据类型。**
### C 语言的泛型
### 一个泛型的示例 - swap 函数
好了，我们再看下，C 语言是如何泛型的。C 语言的类型泛型基本上来说就是使用`void *`关键字或是使用宏定义。
下面是一个使用了`void*`泛型版本的 swap 函数。
```C
void swap(void* x, void* y, size_t size)
{
char tmp[size];
memcpy(tmp, y, size);
memcpy(y, x, size);
memcpy(x, tmp, size);
}
```
上面这个函数几乎完全改变了 int 版的函数的实现方式，这个实现方式有三个重点：
- **函数接口中增加了一个`size`参数**。为什么要这么干呢？因为，用了 `void*` 后，类型被“抽象”掉了，编译器不能通过类型得到类型的尺寸了，所以，需要我们手动地加上一个类型长度的标识。
- **函数的实现中使用了`memcpy()`函数**。为什么要这样干呢？还是因为类型被“抽象”掉了，所以不能用赋值表达式了，很有可能传进来的参数类型还是一个结构体，因此，为了要交换这些复杂类型的值，我们只能使用内存复制的方法了。
- **函数的实现中使用了一个`temp[size]`数组**。这就是交换数据时需要用的 buffer，用 buffer 来做临时的空间存储。
于是，新增的`size`参数，使用的`memcpy`内存拷贝以及一个 buffer，这增加了编程的复杂度。这就是 C 语言的类型抽象所带来的复杂度的提升。
在提升复杂度的同时，我们发现还有问题，比如，我们想交换两个字符串数组，类型是：`char*`，那么，我的`swap()`函数的`x`和`y`参数是不是要用`void**`了？这样一来，接口就没法定义了。
除了使用 `void*` 来做泛型，在 C 语言中，还可以用宏定义来做泛型，如下所示：
```c
#define swap(x, y, size) {\
char temp[size]; \
memcpy(temp, &y, size); \
memcpy(&y, &x, size); \
memcpy(&x, temp, size); \
}
```
但用宏带来的问题就是编译器做字符串替换，因为宏是做字符串替换，所以会导致代码膨胀，导致编译出的执行文件比较大。不过对于 swap 这个简单的函数来说，用`void*`和宏替换来说都可以达到泛型。
但是，如果我们不是 swap，而是 min() 或 max() 函数，那么宏替换的问题就会暴露得更多一些。比如，对于下面的这个宏：
```c
#define min(x, y) （(x)>(y) ? (y) : (x)）
```
其中一个最大的问题，就是有可能会有**重复执行**的问题。
### C++ 泛型编程
C++ 泛型版的代码：
```c++
template
Iter search(Iter pStart, Iter pEnd, T target)
{
for(Iter p = pStart; p != pEnd; p++) {
if ( *p == target )
return p;
}
return NULL;
}
```
在 C++ 的泛型版本中，我们可以看到：
- 使用`typename T`抽象了数据结构中存储数据的类型。
- 使用`typename Iter`，这是不同的数据结构需要自己实现的“迭代器”，这样也就抽象掉了不同类型的数据结构。
- 然后，我们对数据容器的遍历使用了`Iter`中的`++`方法，这是数据容器需要重载的操作符，这样通过操作符重载也就泛型掉了遍历。
- 在函数的入参上使用了`pStart`和`pEnd`来表示遍历的起止。
- 使用`*Iter`来取得这个“指针”的内容。这也是通过重载 `*` 取值操作符来达到的泛型。
### Go 泛型编程
go1.18开始可以支持泛型
```go
package main
import "fmt"
func find[T comparable] (arr []T, elem T) int {
for i, v := range arr {
if v == elem {
return i
}
}
return -1
}
```
Go语言的泛型已基本可用了，只不过，还有三个问题：
- 一个是 `fmt.Printf()`中的泛型类型是 `%v` 还不够好，不能像c++ `iostream`重载 `>>` 来获得程序自定义的输出。
- 另外一个是，go不支持操作符重载，所以，你也很难在泛型算法中使用“泛型操作符”如：`==` 等
- 最后一个是，上面的 `find()` 算法依赖于“数组”，对于hash-table、tree、graph、link等数据结构还要重写。也就是说，没有一个像C++ STL那样的一个泛型迭代器（这其中的一部分工作当然也需要通过重载操作符（如：`++` 来实现）
### Java泛型编程
```java
//此处T可以随便写为任意标识，常见的如T、E、K、V等形式的参数常用于表示泛型
//在实例化泛型类时，必须指定T的具体类型
public class Generic
//key这个成员变量的类型为T,T的类型由外部指定
private T key;
public Generic(T key) { //泛型构造方法形参key的类型也为T，T的类型由外部指定
this.key = key;
}
public T getKey(){ //泛型方法getKey的返回值类型为T，T的类型由外部指定
return key;
}
}
```
### 类型系统
在计算机科学中，类型系统用于定义如何将编程语言中的数值和表达式归类为许多不同的类型，以及如何操作这些类型，还有这些类型如何互相作用。类型可以确认一个值或者一组值具有特定的意义和目的。
一般来说，编程语言会有两种类型，一种是内建类型，如 int、float 和 char 等，一种是抽象类型，如 struct、class 和 function 等。抽象类型在程序运行中，可能不表示为值。类型系统在各种语言之间有非常大的不同，也许，最主要的差异存在于编译时期的语法，以及运行时期的操作实现方式。
编译器可能使用值的静态类型以最优化所需的存储区，并选取对数值运算时的最佳算法。例如，在许多 C 编译器中，“浮点数”数据类型是以 32 比特表示、与 IEEE 754 规格一致的单精度浮点数。因此，在数值运算上，C 应用了浮点数规范（浮点数加法、乘法等）。
类型的约束程度以及评估方法，影响了语言的类型。更进一步，编程语言可能就类型多态性部分，对每一个类型都对应了一个针对于这个类型的算法运算。类型理论研究类型系统，尽管实际的编程语言类型系统，起源于计算机架构的实际问题、编译器实现，以及语言设计。
程序语言的类型系统主要提供如下的功能。
- **程序语言的安全性**。使用类型可以让编译器侦测一些代码的错误。例如：可以识别出一个错误无效的表达式。如：`“Hello, World” + 3`这样的不同数据类型间操作的问题。强类型语言提供更多的安全性，但是并不能保证绝对的安全。
- **利于编译器的优化**。 静态类型语言的类型声明，可以让编译器明确地知道程序员的意图。因此，编译器就可以利用这一信息做很多代码优化工作。例如：如果我们指定一个类型是 `int` ，那么编译就知道，这个类型会以 4 个字节的倍数进行对齐，编译器就可以非常有效地利用更有效率的机器指令。
- **代码的可读性**。有类型的编程语言，可以让代码更易读和更易维护。代码的语义也更清楚，代码模块的接口（如函数）也更丰富和清楚。
- **抽象化**。类型允许程序设计者对程序以较高层次的方式思考，而不是烦人的低层次实现。例如，我们使用整型或是浮点型来取代底层的字节实现，我们可以将字符串设计成一个值，而不是底层字节的数组。从高层上来说，类型可以用来定义不同模块间的交互协议，比如函数的入参类型和返回类型，从而可以让接口更有语义，而且不同的模块数据交换更为直观和易懂。
但是，正如前面说的，**类型带来的问题就是我们作用于不同类型的代码，虽然长得非常相似，但是由于类型的问题需要根据不同版本写出不同的算法，如果要做到泛型，就需要涉及比较底层的玩法**。
### 泛型的本质
要了解泛型的本质，就需要了解类型的本质。
- 类型是对内存的一种抽象。不同的类型，会有不同的内存布局和内存分配的策略。
- 不同的类型，有不同的操作。所以，对于特定的类型，也有特定的一组操作。
所以，要做到泛型，我们需要做下面的事情。
- 标准化掉类型的内存分配、释放和访问。
- 标准化掉类型的操作。比如：比较操作，I/O 操作，复制操作……
- 标准化掉数据容器的操作。比如：查找算法、过滤算法、聚合算法……
- 标准化掉类型上特有的操作。需要有标准化的接口来回调不同类型的具体操作……
所以，C++ 动用了非常繁多和复杂的技术来达到泛型编程的目标。
- 通过类中的构造、析构、拷贝构造，重载赋值操作符，标准化（隐藏）了类型的内存分配、释放和复制的操作。
- 通过重载操作符，可以标准化类型的比较等操作。
- 通过 iostream，标准化了类型的输入输出控制。
- 通过模板技术（包括模板的特化），来为不同的类型生成类型专属的代码。
- 通过迭代器来标准化数据容器的遍历操作。
- 通过面向对象的接口依赖（虚函数技术），来标准化了特定类型在特定算法上的操作。
- 通过函数式（函数对象），来标准化对于不同类型的特定操作。
我理解其本质就是 —— **屏蔽掉数据和操作数据的细节，让算法更为通用，让编程者更多地关注算法的结构，而不是在算法中处理不同的数据类型。**
点赞
回复
X