极客时间已完结课程限时免费阅读

31 | 编程范式游记（2）- 泛型编程

31 | 编程范式游记（2）- 泛型编程-极客时间

31 | 编程范式游记（2）- 泛型编程

2018-01-16 陈皓 来自北京
《左耳听风》
课程介绍

讲述：杨超

时长17:07大小15.64M

你好，我是陈皓，网名左耳朵耗子。
在上节课，我从 C 语言开始说起，聊了聊面向过程式的编程范式，相信从代码的角度你对这类型的语言已经有了一些理解。作为一门高级语言，C 语言绝对是编程语言历史发展中的一个重要里程碑，但随着认知的升级，面向过程的 C 语言已经无法满足更高层次的编程的需要。于是，C++ 出现了。

C++ 语言

1980 年，AT&T 贝尔实验室的 Bjarne Stroustrup 创建的 C++ 语言横空出世，它既可以全面兼容 C 语言，又巧妙揉合了一些面向对象的编程理念。现在来看，不得不佩服 Stroustrup 的魄力。在这里，我也向你推荐一本书，书名是《C++ 语言的设计和演化》。
这本书系统介绍了 C++ 诞生的背景以及初衷，书的作者就是Stroustrup本人，所以你可以非常详细地从语言创建者的角度了解他的设计思路和创新之旅。当然，就是在今天，C++ 这门语言也还有很多争议，这里我不细说。如果你感兴趣的话，可以看看我几年前在酷壳上发表的文章《C++ 的坑真的多吗？》。
从语言角度来说，实际上早期 C++ 的许多工作是对 C 的强化和净化，并把完全兼容 C 作为强制性要求（这也是 C++ 复杂晦涩的原因，这点 Java 就干得比 C++ 彻底得多）。在 C89、C99 这两个 C 语言的标准中，有许多改进都是从 C++ 中引进的。
可见，C++ 对 C 语言的贡献非常之大。是的，因为 C++ 很大程度就是用来解决 C 语言中的各种问题和各种不方便的。比如：
用引用来解决指针的问题。
用 namespace 来解决名字空间冲突的问题。
通过 try-catch 来解决检查返回值编程的问题。
用 class 来解决对象的创建、复制、销毁的问题，从而可以达到在结构体嵌套时可以深度复制的内存安全问题。
通过重载操作符来达到操作上的泛型。（比如，消除《01 | 编程范式游记：起源》中提到的比较函数cmpFn，再比如用>>操作符消除printf()的数据类型不够泛型的问题。）
通过模板 template 和虚函数的多态以及运行时识别来达到更高层次的泛型和多态。
用 RAII、智能指针的方式，解决了 C 语言中因为需要释放资源而出现的那些非常 ugly 也很容易出错的代码的问题。
用 STL 解决了 C 语言中算法和数据结构的 N 多种坑。

C++ 泛型编程

C++ 是支持编程范式最多的一门语言，它虽然解决了很多 C 语言的问题，但我个人觉得它最大的意义是解决了 C 语言泛型编程的问题。因为，我们可以看到一些 C++ 的标准规格说明书里，有一半以上都在说明 STL 的标准规格应该是什么样的，这说明泛型编程是 C++ 重点中的重点。
理想情况下，算法应是和数据结构以及类型无关的，各种特殊的数据类型理应做好自己分内的工作，算法只关心一个标准的实现。而对于泛型的抽象，我们需要回答的问题是，如果我们的数据类型符合通用算法，那么对数据类型的最小需求又是什么呢？
我们来看看 C++ 是如何有效解决程序泛型问题的，我认为有三点。
第一，它通过类的方式来解决。
类里面会有构造函数、析构函数表示这个类的分配和释放。
还有它的拷贝构造函数，表示了对内存的复制。
还有重载操作符，像我们要去比较大于、等于、不等于。
这样可以让一个用户自定义的数据类型和内建的那些数据类型就很一致了。
第二，通过模板达到类型和算法的妥协。
模板有点像 DSL，模板的特化会根据使用者的类型在编译时期生成那个模板的代码。
模板可以通过一个虚拟类型来做类型绑定，这样不会导致类型转换时的问题。
模板很好地取代了 C 时代宏定义带来的问题。
第三，通过虚函数和运行时类型识别。
虚函数带来的多态在语义上可以支持“同一类”的类型泛型。
运行时类型识别技术可以做到在泛型时对具体类型的特殊处理。
这样一来，就可以写出基于抽象接口的泛型。
拥有了这些 C++ 引入的技术，我们就可以做到 C 语言很难做到的泛型编程了。
正如前面说过的，一个良好的泛型编程需要解决如下几个泛型编程的问题：
算法的泛型；
类型的泛型；
数据结构（数据容器）的泛型。

C++ 泛型编程的示例 - Search 函数

就像前面的search()函数，里面的 for(int i=0; i<len; i++) 这样的遍历方式，只能适用于顺序型的数据结构的方式迭代，如：array、set、queue、list 和 link 等。并不适用于非顺序型的数据结构。
如哈希表 hash table，二叉树 binary tree、图 graph 等这样数据不是按顺序存放的数据结构（数据容器）。所以，如果找不到一种泛型的数据结构的操作方式（如遍历、查找、增加、删除、修改……），那么，任何的算法或是程序都不可能做到真正意义上的泛型。
除了search()函数的“遍历操作”之外，还有 search 函数的返回值，是一个整型的索引下标。这个整型的下标对于“顺序型的数据结构”是没有问题的，但是对于“非顺序的数据结构”，在语义上都存在问题。
比如，如果我要在一个 hash table 中查找一个 key，返回什么呢？一定不是返回“索引下标”，因为在 hash table 这样的数据结构中，数据的存放位置不是顺序的，而且还会因为容量不够的问题被重新 hash 后改变，所以返回数组下标是没有意义的。
对此，我们要把这个事做得泛型和通用一些。如果找到，返回找到的这个元素的一个指针（地址）会更靠谱一些。
所以，为了解决泛型的问题，我们需要动用以下几个 C++ 的技术。
使用模板技术来抽象类型，这样可以写出类型无关的数据结构（数据容器）。
使用一个迭代器来遍历或是操作数据结构内的元素。
我们来看一下 C++ 版的search()函数是什么样的。
先重温一下 C 语言版的代码：
int search(void* a, size_t size, void* target,
size_t elem_size, int(*cmpFn)(void*, void*) )
{
for(int i=0; i<size; i++) {
if ( cmpFn (a + elem_size * i, target) == 0 ) {
return i;
}
}
return -1;
}
我们再来看一下 C++ 泛型版的代码：
template<typename T, typename Iter>
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来取得这个“指针”的内容。这也是通过重载 * 取值操作符来达到的泛型。
当然，你可能会问，为什么我们不用标准接口Iter.Next()取代++， 用Iter.GetValue()来取代*，而是通过重载操作符？其实这样做是为了兼容原有 C 语言的编程习惯。
说明一下，所谓的Iter，在实际代码中，就是像vector<int>::iterator或map<int, string>::iterator这样的东西。这是由相应的数据容器来实现和提供的。
注：下面是 C++ STL 中的find()函数的代码。
template<class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val)
{
while (first!=last) {
if (*first==val) return first;
++first;
}
return last;
}

C++ 泛型编程示例 - Sum 函数

也许你觉得到这一步，我们的泛型设计就完成了。其实，还远远不够。search函数只是一个开始，我们还有很多别的算法会让问题变得更为复杂。
我们再来看一个sum()函数。
先看 C 语言版：
long sum(int *a, size_t size) {
long result = 0;
for(int i=0; i<size; i++) {
result += a[i];
}
return result;
}
再看一下 C++ 泛型的版本：
template<typename T, typename Iter>
T sum(Iter pStart, Iter pEnd) {
T result = 0;
for(Iter p=pStart; p!=pEnd; p++) {
result += *p;
}
return result;
}
你看到了什么样的问题？这个代码中最大的问题就是 T result = 0; 这条语句：
那个0假设了类型是int；
那个T假设了 Iter 中出来的类型是T。
这样的假设是有问题的，如果类型不一样，就会导致转型的问题，这会带来非常 buggy 的代码。那么，我们怎么解决呢？

C++ 泛型编程的重要技术 - 迭代器

我们知道Iter在实际调用者那会是一个具体的像vector<int>::iterator这样的东西。在这个声明中，int已经被传入Iter中了。所以，定义result的T应该可以从Iter中来。这样就可以保证类型是一样的，而且不会有被转型的问题。
所以，我们需要精心地实现一个“迭代器”。下面是一个“精简版”的迭代器（我没有把 C++ STL 代码里的迭代器列出来，是因为代码太多太复杂，我这里只是为了说明问题）。
template <class T>
class container {
public:
class iterator {
public:
typedef iterator self_type;
typedef T value_type;
typedef T* pointer;
typedef T& reference;
reference operator*();
pointer operator->();
bool operator==(const self_type& rhs)；
bool operator!=(const self_type& rhs)；
self_type operator++() { self_type i = *this; ptr_++; return i; }
self_type operator++(int junk) { ptr_++; return *this; }
...
...
private:
pointer _ptr;
};
iterator begin();
iterator end();
...
...
};
上面的代码是我写的一个迭代器（这个迭代器在语义上是没有问题的），我没有把所有的代码列出来，而把它的一些基本思路列了出来。这里我说明一下几个关键点。
首先，一个迭代器需要和一个容器在一起，因为里面是对这个容器的具体的代码实现。
它需要重载一些操作符，比如：取值操作*、成员操作->、比较操作==和!=，还有遍历操作++，等等。
然后，还要typedef一些类型，比如value_type，告诉我们容器内的数据的实际类型是什么样子。
还有一些，如begin()和end()的基本操作。
我们还可以看到其中有一个pointer _ptr的内部指针来指向当前的数据（注意，pointer就是 T*）。
好了，有了这个迭代器后，我们还要解决T result = 0后面的这个0的问题。这个事，算法没有办法搞定，最好由用户传入。于是出现了下面最终泛型的sum()版函数。
template <class Iter>
typename Iter::value_type
sum(Iter start, Iter end, T init) {
typename Iter::value_type result = init;
while (start != end) {
result = result + *start;
start++;
}
return result;
}
我们可以看到typename Iter::value_type result = init这条语句是关键。我们解决了所有的问题。
我们使用如下：
container<int> c;
container<int>::iterator it = c.begin();
sum(c.begin(), c.end(), 0);
这就是整个 STL 的泛型方法，其中包括：
泛型的数据容器；
泛型数据容器的迭代器；
然后泛型的算法就很容易写了。

需要更多的抽象

更为复杂的需求

但是，还能不能做到更为泛型呢？比如：如果我们有这样的一个数据结构 Employee，里面有 vacation 就是休假多少天，以及工资。
struct Employee {
string name;
string id;
int vacation;
double salary；
};
现在我想计算员工的总薪水，或是总休假天数。
vector<Employee> staff;
//total salary or total vacation days?
sum(staff.begin(), staff.end(), 0);
我们的sum完全不知道怎么搞了，因为要累加的是Employee类中的不同字段，即便我们的 Employee 中重载了+操作，也不知道要加哪个字段。
另外，我们可能还会有：求平均值 average，求最小值 min，求最大值 max，求中位数 mean 等等。你会发现，算法写出来基本上都是一样的，只是其中的“累加”操作变成了另外一个操作。就这个例子而言，我想计算员工薪水里面最高的，和休假最少的，或者我想计算全部员工的总共休假多少天。那么面对这么多的需求，我们是否可以泛型一些呢？怎样解决这些问题呢？

更高维度的抽象

要解决这个问题，我希望我的这个算法只管遍历，具体要干什么，那是业务逻辑，由外面的调用方来定义我就好了，和我无关。这样一来，代码的重用度就更高了。
下面是一个抽象度更高的版本，这个版本再叫sum就不太合适了。这个版本应该是reduce——用于把一个数组 reduce 成一个值。
template<class Iter, class T, class Op>
T reduce (Iter start, Iter end, T init, Op op) {
T result = init;
while ( start != end ) {
result = op( result, *start );
start++;
}
return result;
}
上面的代码中，我们需要传一个函数进来。在 STL 中，它是个函数对象，我们还是这套算法，但是 result 不是像前面那样去加，是把整个迭代器值给你一个 operation，然后由它来做。我把这个方法又拿出去了，所以就会变成这个样子。
在 C++ STL 中，与我的这个 reduce 函数对应的函数名叫 accumulate()，其实际代码有两个版本。
第一个版本就是下面的版本，只不过是用for语句而不是while。
template<class InputIt, class T>
T accumulate(InputIt first, InputIt last, T init)
{
for (; first != last; ++first) {
init = init + *first;
}
return init;
}
第二个版本，更为抽象，因为需要传入一个“二元操作函数”——BinaryOperation op来做 accumulate。accumulate 的语义比 sum 更抽象了。
template<class InputIt, class T, class BinaryOperation>
T accumulate(InputIt first, InputIt last, T init,
BinaryOperation op)
{
for (; first != last; ++first) {
init = op(init, *first);
}
return init;
}
来看看我们在使用中是什么样子的：
double sum_salaries =
reduce( staff.begin(), staff.end(), 0.0,
[](double s, Employee e)
{return s + e.salary;} );
double max_salary =
reduce( staff.begin(), staff.end(), 0.0,
[](double s, Employee e)
{return s > e.salary? s: e.salary; } );
注意：我这里用了 C++ 的 lambda 表达式。
你可以很清楚地看到，reduce 这个函数就更通用了，具体要干什么样的事情呢？放在匿名函数里面，它会定义我，我只做一个 reduce。更抽象地来说，我就把一个数组，一个集合，变成一个值。怎么变成一个值呢？由这个函数来决定。

Reduce 函数

我们来看看如何使用 reduce 和其它函数完成一个更为复杂的功能。
下面这个示例中，我先定义了一个函数对象counter。这个函数对象需要一个Cond的函数对象，它是个条件判断函数，如果满足条件，则加 1，否则加 0。
template<class T, class Cond>
struct counter {
size_t operator()(size_t c, T t) const {
return c + (Cond(t) ? 1 : 0);
}
};
然后，我用上面的counter函数对象和reduce函数共同来打造一个counter_if算法（当条件满足的时候我就记个数，也就是统计满足某个条件的个数），我们可以看到，就是一行代码的事。
template<class Iter, class Cond>
size_t count_if(Iter begin, Iter end, Cond c){
return reduce(begin, end, 0,
counter<Iter::value_type, Cond>(c));
}
至于是什么样的条件，这个属于业务逻辑，不是我的流程控制，所以，这应该交给使用方。
于是，当我需要统计薪资超过 1 万元的员工的数量时，一行代码就完成了。
size_t cnt = count_if(staff.begin(), staff.end(),
[](Employee e){ return e.salary > 10000; });
Reduce 时可以只对结构体中的某些值做 Reduce，比如说只对 salary>10000 的人做，只选出这个里面的值，它用 Reduce 就可以达到这步，只要传不同的方式给它，你就可以又造出一个新的东西出来。
说着说着，就到了函数式编程。函数式编程里面，我们可以用很多的像 reduce 这样的函数来完成更多的像 STL 里面的count_if()这样有具体意义的函数。关于函数式编程，我们会在后面继续具体聊。

小结

在这篇文章中，我们聊到 C++ 语言是如何通过泛型来解决 C 语言遇到的问题，其实这里面主要就是泛型编程和函数式编程的基本方法相关的细节，虽然解决编程语言中类型带来的问题可能有多种方式，不一定就是 C++ 这种方式。
而我之所以从 C/C++ 开始，目的只是因为 C/C++ 都是比较偏底层的编程语言。从底层的原理上，我们可以更透彻地了解，从 C 到 C++ 的演进这一过程中带来的编程方式的变化。这可以让你看到，在静态类型语言方面解决泛型编程的一些技术和方法，从而感受到其中的奥妙和原理。
因为形式是多样的，但是原理是相通的，所以，这个过程会非常有助于你更深刻地了解后面会谈到的更多的编程范式。
以下是《编程范式游记》系列文章的目录，方便你了解这一系列内容的全貌。
01 | 编程范式游记：起源
02 | 编程范式游记：泛型编程
03 | 编程范式游记：类型系统和泛型的本质
04 | 编程范式游记：函数式编程
05 | 编程范式游记：修饰器模式
06 | 编程范式游记：面向对象编程
07 | 编程范式游记：基于原型的编程范式
08 | 编程范式游记：Go 语言的委托模式
09 | 编程范式游记：编程的本质
10 | 编程范式游记：逻辑编程范式
11 | 编程范式游记：程序世界里的编程范式
分享给需要的人，Ta购买本课程，你将得29元
生成海报并分享

赞 38

提建议

© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
上一篇
30 | 编程范式游记（1）- 起源
下一篇
32 | 编程范式游记（3） - 类型系统和泛型的本质
unpreview
 写留言

精选留言(47)

  • okokabcd
    2018-02-14
    版本一： 电影(男主，女主) { 男主杀死了女主 } 版本二： 电影(男主，女主，情节(A,B){A爱上了B}){ 情节(男主，女主) }
    展开
    共 1 条评论
    71
  • 昵称
    2018-04-12
    《STL源码解析》，《inside c++model》，记得当时啃这两本时经常要感叹怎么设计的这么精妙，了解内部实现方式后，在使用的时候也更加心里有底
    18
  • 闫飞
    2018-01-10
    泛型技术是静态系统所独有的特性，本质上我觉得还是为了兼顾执行效率和编程灵活性，实现零成本抽象这一刀尖上跳舞的巨大挑战。 较新的语言标准还提炼了很多基础设施，比如大量使用SFINAE并泛化之,提供enable if, constexpr if, 乃至自动类型推断和concept check，和Java那边的套路是完全不一样的。 可以说不深入理解泛型技术基本，就不能很好理解现代的C++了。
    展开
    16
  • Geek_e5dad7
    2019-10-22
    看到大家都说看的很享受，但是我真的看不懂😭
    共 1 条评论
    13
  • edisonhuang
    2019-06-18
    C++通过范型消除了C语言中很多易出bug的代码，实现代码重用。其中关键在于：算法的泛型；类型的泛型；数据结构（数据容器）的泛型。 C++通过类，在构造和析构函数中做资源的申请释放，通过引用解决了用指针来取值的问题。通过操作符的重载让算法代码忽略具体类型，可以有统一的表达。通过类似迭代器的范型容器来统一不同数据结构的统一算法表达。 通过抽象算法中函数的操作，用函数式编程的方式，实现算法的泛型。 总之，通过不同粒度的抽象，而让代码重用更容易，bug更少，更好维护和扩展
    展开
    10
  • 知知知了
    2018-06-02
    counter结构体有点问题，调了半天。 如果刚上大学能看到耗子书的文章就好了，看谭浩强学的c和c++真浪费生命，编程还沦为了二流，唉
    共 1 条评论
    7
  • Join
    2018-01-10
    读起来真是太享受了，感觉之前看的那些STL知识被瞬间点燃了，以前思考并未达到这样的深度，能做到将技术和业务逻辑分离开的代码真是太通用了，现在回去再读一遍STL源码解析会更有体会
    7
  • 郑杰
    2018-01-09
    可以讲讲java的类型擦除原理吗
    6
  • karas
    2019-06-07
    实在不怎么懂cpp，对标Java说一点。感觉cpp做到通用操作最重要的是操作符重载，比如上面的累加的实现主要就是靠++重载定义next（），*重载定义怎么取对象的值，+重载定义累加的逻辑。对标Java，Java没有操作符重载，他主要依赖接口去规约必要的通用操作。比如一般容器会实现iterator接口，涉及到排序则要求<T extends Comparator>类型参数。凭直觉来讲，操作符可能更加灵活一点。 另外最后介绍的函数参数，应该算是Java里的匿名类吧，当然j8也可以用lambda了，不过我倒觉得这和泛型无关吧，算是函数式的概念。
    展开
    5
  • CH_G318
    2019-01-24
    有些代码跑不通，总是报错，现在修改成下面的样子了： template<class T, class Cond> struct counter { Cond cond; // 添加一个变量 size_t operator()(size_t c, T t) { return c + (cond(t) ? 1 : 0); // 使用变量进行判断 } }; template<class Iter, class Cond> size_t count_if(Iter begin, Iter end, Cond c) { auto op = counter<typename Iter::value_type, Cond>{c}; // 初始化counter结构体 return reduce(begin, end, size_t(0), op); }
    展开
    共 1 条评论
    4
  • saiyn
    2018-05-31
    从c到c++的发展过程，让我深刻理解了迭代器是个什么鬼，感谢耗子叔
    5
  • 桃子妈妈
    2019-06-06
    大神就是把复杂的知识简单化的讲解出来，好厉害
    4
  • 夏洛克的救赎
    2018-05-20
    如何理解aop
    3
  • 云学
    2018-01-09
    恰巧不久前实现过迭代器，所以读起来非常享受
    3
  • 流云
    2020-07-14
    汇编语言算是无类型语言，C语言引入了类型系统，C++ 又扩展了泛型编程，类型往底层反映了内存布局与管理策略，往上层抽象出算法的通用性，通过类型系统把这几种语言的理解推进了一大步，感谢左耳朵。 下面为counter 新增了一个私有成员变量和一个构造函数，解决编译错误问题： template<class T, class Cond> class counter { private: Cond cond; public: counter(Cond c):cond(c) { } size_t operator()(size_t c, T t) const { return c + (cond(t) ? 1 : 0); } };
    展开
    共 1 条评论
    2
  • caohuan
    2018-11-07
    耗子哥 一步步的抽象过程，让我想到了C#和java都是面向对象语言，都有抽象的说法，比如 类为对象的抽象，接口为 类的抽象，有了抽象的思维，会让实现变得友好，逻辑也清晰，耗子哥的专栏也是这样的设计思想。
    2
  • 上上签
    2018-02-14
    认真仔细学习，才觉得真是很不错的，不白付费。
    2
  • JK.Ryan
    2018-01-11
    写的很赞👍🏾，感觉也可以顺带讲一下Go的接口，对比多语言可以更加突出“范式”：）

    作者回复: 后面会有的

    2
  • 郑杰
    2018-01-09
    c++的模板特化跟Java的类型擦除应该做的是一类事情吧？
    2
  • Marvichov
    2020-07-11
    Rust可以对generic type做Trait (类似java的interface）类型检测 (相当于把C++ concept具象化了): ``` // where clause is borrowed from swift, personally, I think it's great for readability fn some_function<T, U>(t: T, u: U) -> i32 where T: Display + Clone, U: Clone + Debug {...} ``` 总体感觉rust的interface oriented programming是C++ generic的升级，完全可以替代以继承
    展开
    1