编程范式系列-泛型编程

SystemDesign 编程范式

创建时间:2020-02-04 12:31

字数:2.8k 阅读:

评论:

1. 起源
1.1 C语言
2. 泛型编程
3. 泛型的本质
reference

1. 起源

编程范式, programming paradigm，是一类典型的编程风格。

将主流编程语言分为三部分，加上对于编程本质的理解。共四篇文章。

泛型编程
函数式编程
面向对象编程
编程本质和逻辑编程

1.1 C语言

几乎现行的所有编程语言都是从c语言拓展来的，简述c语言的特性：

静态弱类型语言，使用变量时需要声明变量类型，但类型之间有隐式转换
typedef 定义类型的别名，达到变量类型的抽象
不同变量类型可以用结构体组合在一起

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);
}

利用宏定义来做泛型

#define swap(x, y, size) {\
    char temp[size]; \
    memcpy(temp, &y, size); \
    memcpy(&y,   &x, size); \
    memcpy(&x, temp, size); \
}

比较大小的宏定义

#define min(x, y)  （(x)>(y) ? (y) : (x)）

这里如果比较min(x++, y++)的话，各自会加两次

小结
如果说程序 = 算法 + 数据， C语言会有这几个问题

一个通用的算法，需要对所处理的数据的数据类型进行适配。但在适配数据类型的过程中，C 语言只能使用 void * 或宏替换的方式。这两种方式导致了类型过于宽松，并带来很多其它问题。
适配数据类型，需要 C 语言在泛型中加入一个类型的 size，这是因为我们识别不了被泛型后的数据类型，而 C 语言没有运行时的类型识别，所以，只能将这个工作抛给调用泛型算法的程序员来做了
算法其实是在操作数据结构，而数据则是放到数据结构中的。所以，真正的泛型除了适配数据类型外，还要适配数据结构。最后这个事情导致泛型算法的复杂急剧上升。比如容器内存的分配和释放，不同的数据体可能有非常不一样的内存分配和释放模型，再比如对象之间的复制，要把它存进来我需要有一个复制，这其中又涉及到是深拷贝，还是浅拷贝。
最后，在实现泛型算法的时候，你会发现自己在纠结哪些东西应该抛给调用者处理，哪些又是可以封装起来。如何平衡和选择，并没有定论，也不好解决。

比如 C 语言就是过程式的编程语言，像C语言这样的过程式编程语言优点是底层灵活而且高效，特别适合开发运行较快且对系统资源利用率要求较高的程序，但我上面抛出的问题它在后来也没有试图去解决，因为编程范式的选择基本已经决定了它的“命运”。

2. 泛型编程

2.1 C++ 语言

C++ 很大程度上是来解决C语言中的各种问题和各种不方便。

用引用来解决指针的问题。
用 namespace 来解决名字空间冲突的问题。
通过 try-catch 来解决检查返回值编程的问题。
用 class 来解决对象的创建、复制、销毁的问题，从而可以达到在结构体嵌套时可以深度复制的内存安全问题。
通过重载操作符来达到操作上的泛型
通过模板 template 和虚函数的多态以及运行时识别来达到更高层次的泛型和多态。
用 RAII、智能指针的方式，解决了 C 语言中因为需要释放资源而出现的那些非常 ugly 也很容易出错的代码的问题。
用 STL 解决了 C 语言中算法和数据结构的 N 多种坑。

2.2 C++ 语言的泛型编程

理想情况下，算法应该与数据结构和类型无关的。各种特殊的数据结构应该能自己做好泛型处理，算法是一个标准的实现。

对于泛型的抽象，需要回答的问题是：如果我们的数据类型符合通用算法，那么对数据类型的最小需求是什么？？？

2.2.1 C++ 如何解决泛型问题的？

通过类的方式解决

类里面会有构造函数、析构函数表示这个类的分配和释放。
还有它的拷贝构造函数，表示了对内存的复制。
还有重载操作符，像我们要去比较大于、等于、不等于。

通过模板达到类型和算法的妥协

模板有点像 DSL，模板的特化会根据使用者的类型在编译时期生成那个模板的代码。
模板可以通过一个虚拟类型来做类型绑定，这样不会导致类型转换时的问题。

通过虚函数和运行时类识别

虚函数带来的多态在语义上可以让“同一类”的类型进行泛型。
运行时类型识别技术可以做到在泛型时对具体类型的特殊处理。

一个良好的泛型编程需要解决 1）算法的泛型 2）类型的泛型 3）数据结构的泛型

2.2.2 泛型编程实例

Search 函数

不是所有的数据结构都是顺序型的，不能用 for(int i = 0; i < len; i++) 来做抽象的，比如hashtable，二叉树，图就是非顺序型的。这种写法对他们来说没有意义。

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;
}

可以看到：

使用 typename T 抽象了数据结构中存储数据的类型
使用 typename Iter，让不同的数据结构实现自己的迭代器，用这种方式抽象掉了不同类型的数据结构。
然后，我们对数据容器的遍历使用了Iter中的++方法，这是数据容器需要重载的操作符，这样通过操作符重载也就泛型掉了遍历。
使用*Iter来取得指针的内容，这也是通过重载*取值操作符来达到的泛型。
tips: Iter 在实际代码中，是类似于vector<int>::iterator map<int, String>::iterator。是由相应的数据容器来实现和提供的。

迭代器

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一些类型，搞死容器内的数据的实际类型是什么样子的
begin() end()基本操作

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;
}

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;
}

2.2 动态类型语言的泛型编程

在编程世界，我们需要处理好两件事情：

编程语言中的类型问题
对真实世界中业务代码的抽象、重用和拼装

2.2.1 类型系统

在计算机科学中，类型系统用于定义如何将编程语言中的数值和表达式归类为许多不同的类型，以及如何操作这些类型，还有这些类型如何互相作用。类型可以确认一个值或者一组值具有特定的意义和目的。

类型系统在各种语言之间很不同，存在于编译时期的语法，以及运行时期的操作实现方式。

程序语言的类型系统主要提供如下功能：

程序语言的安全性

使用类型可以让编译器侦测一些代码的错误。例如：可以识别出一个错误无效的表达式。如：“Hello, World” + 3这样的不同数据类型间操作的问题。强类型语言提供更多的安全性，但是并不能保证绝对的安全。

利于编译器的优化

静态类型语言的类型声明，可以让编译器明确地知道程序员的意图。因此，编译器就可以利用这一信息做很多代码优化工作。例如：如果我们指定一个类型是int,那么编译就知道，这个类型会以4个字节的倍数进行对齐，编译器就可以非常有效地利用更有效率的机器指令。

代码的可读性

有类型的编程语言，可以让代码更易读和更易维护。代码的语义也更清楚，代码模块的接口（如函数）也更丰富和更清楚。

抽象化

类型允许程序设计者对程序以较高层次的方式思考，而不是烦人的低层次实现。例如，我们使用整型或是浮点型来取代底层的字节实现，我们可以将字符串设计成一个值，而不是底层的字节的数组。从高层上来说，类型可以用来定义不同模块间的交互协议，比如函数的入参类型和返回类型，从而可以让接口更有语义，而且不同的模块数据交换更为直观和易懂。

在动态语言中，一个变量的类型是由运行时的解释器来动态标记的，这样就可以动态地和底层的计算机指令或内存布局对应起来。

3. 泛型的本质

类型是对内存的一种抽象。不同的类型，会有不同的内存布局和内存分配的策略。
不同的类型，有不同的操作。所以，对于特定的类型，也有特定的一组操作。

Generic programming centers around the idea of abstracting from concrete, efficient algorithms to obtain generic algorithms that can be combined with different data representations to produce a wide variety of useful software.

屏蔽掉数据和操作数据的细节，让算法更为通用，让编程者更多地关注算法结构，而不是在算法中处理不同的数据类型。

要做到泛型，我们需要：