最近看了一些关于编程范式的文章,简要做一些小结和记录 什么是编程范式 在现实生活中,为了适配各种规格的螺帽,我们需要许多种类的螺丝刀。 在编程世界中,静态语言有许多种类的数据类型。 不过,我们可以发现,无论是传统世界,还是编程世界,我们都在干一件事情,就是通过使用一种更为通用的方式,抽象和隔离,让复杂的“世界”变得简单一些。 C语言的范式例子1:swap函数 原版,swap交换变量(只能交换int型) void swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } 改进版,使用void * 抽象化数据类型,范式编程: void swap(void* x, void* y, size_t size) { char tmp[size]; memcpy(tmp, y, size); memcpy(y, x, size); memcpy(x, tmp, size); } 函数接口中增加了一个size参数。一旦用了 void* 后,类型就会被“抽象”掉,编译器不能通过类型得到类型的尺寸了,所以需要我们手动加上一个类型长度的标识。 函数的实现中使用了memcpy()函数。因为类型被“抽象”掉了,所以不能用赋值表达式了,很有可能传进来的参数类型还是一个结构体,不过,为了要交换这些复杂类型的值,我们只能使用内存复制的方法了。 函数的实现中使用了一个temp[size]数组。这就是交换数据时需要用的 buffer,会用 buffer 来做临时的空间存储。 C语言的范式例子2:search函数 原版C语言函数,搜索target在整型数组中的位置: int search(int* a, size_t size, int target) { for(int i=0; i<size; i++) { if (a[i] == target) { return i; } } return -1; } 把search函数变为泛型,使之不仅能查找整型数组,也能查找适配其他传入的各种类型参数。 参数a,可以遍历的数组、结构体数组等 target,void *,不定类型的数据(以适配范式) cmpFn,函数,用户程序员自定义的各种数据的比较函数 int search(void* a, size_t size, void* target, size_t elem_size, int(*cmpFn)(void*, void*) ) { for(int i=0; i<size; i++) { // 这里不用memcmp比较,是因为 针对传入的数据类型是结构体类型时,memcmp会比较内存地址。 //使用 unsigned char * 计算地址 if ( cmpFn ((unsigned char *)a + elem_size * i, target) == 0 ) { return i; } } return -1; } //整数比较函数 int int_cmp(int* x, int* y) { return *x - *y; } //字符串比较函数 int string_cmp(char* x, char* y){ return strcmp(x, y); } //结构体比较函数 typedef struct _account { char name[10]; char id[20]; } Account; int account_cmp(Account* x, Account* y) { int n = strcmp(x->name, y->name); if (n != 0) return n; return strcmp(x->id, y->id); } 上面的泛型search函数缺陷:只支持顺序类型的数据结构,遇到复杂的图、树等无法抽象化非顺序型的数据容器 另外C语言还可以使用宏定义来泛型化。 泛型编程 一个良好的泛型编程需要解决如下几个泛型编程的问题: 1.算法的泛型; 2.类型的泛型; 3.数据结构(数据容器)的泛型。 就像前面的search()函数,里面的 for(int i=0; i<len; i++) 这样的遍历方式,只能适用于顺序型的数据结构的方式迭代,如:array、set、queue、list 和 link 等。并不适用于非顺序型的数据结构。 如哈希表 hash table,二叉树 binary tree、图 graph 等这样数据不是按顺序存放的数据结构(数据容器)。所以,如果找不到一种泛型的数据结构的操作方式(如遍历、查找、增加、删除、修改……),那么,任何的算法或是程序都不可能做到真正意义上的泛型。 比如,如果我要在一个 hash table 中查找一个 key,返回什么呢?一定不是返回“索引下标”,因为在 hash table 这样的数据结构中,数据的存放位置不是顺序的,而且还会因为容量不够的问题被重新 hash 后改变,所以返回数组下标是没有意义的。 对此,我们要把这个事做得泛型和通用一些。如果找到,返回找到的这个元素的一个指针(地址)会更靠谱一些。 所以,为了解决泛型的问题,我们需要动用以下几个 C++ 的技术。 1.使用“模板”来抽象类型,这样可以写出类型无关的数据结构(数据容器)。 2.使用一个“迭代器”来遍历或是操作数据结构内的元素。 C++的范式例子1:search函数 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中的++方法,这是数据容器需要重载的操作符,这样通过操作符重载也就泛型掉了遍历, 为了兼容原有 C 语言的编程习惯我们不用标准接口Iter.Next(),不用Iter.GetValue()来取代*。 在函数的入参上使用了pStart和pEnd来表示遍历的起止。 使用Iter来取得这个“指针”的内容。这也是通过重载 取值操作符来达到的泛型。 说明:所谓的Iter,在实际代码中,就是像vector::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++的范式例子2: 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;也就是T假设了 Iter 中出来的类型是T。0假设了类型是int;如果类型不一样,就会导致转型的问题 改进版,需要迭代器 Iter在实际调用者那会是一个具体的像vector::iterator的东西 在这个声明中,int已经被传入Iter中了;所以定义result的T应该可以从Iter中来。这样就可以保证类型是一样的,而且不会有被转型的问题。 C++ 泛型编程:迭代器 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(); ... ... }; 1.首先,一个迭代器需要和一个"数据容器"(类)在一起,因为里面是对这个容器的具体的代码实现,对这个容器的迭代。 2.它需要重载一些操作符,比如:取值操作*、成员操作->、比较操作==和!=,还有遍历操作++,等等。 3.然后,还要typedef一些类型,比如value_type,告诉我们容器内的数据的实际类型是什么样子。 4.还有一些,如begin()和end()的基本操作。 5.我们还可以看到其中有一个pointer _ptr的内部指针来指向当前的数据(注意,pointer就是 T*)。 有了迭代器,我们让用户自型传入模板T的类型,解决T result = 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; } int main(){ container<int> c; container<int>::iterator it = c.begin(); sum(c.begin(), c.end(), 0); return 0; } 这就是整个 STL 的泛型方法,其中包括: 1.泛型的数据容器; 2.泛型数据容器的迭代器; 3.泛型的算法; reduce函数式编程 如果我们有一个 员工结构体,再想用sum函数来求和怎么办? struct Employee { string name; string id; int vacation; double salary; }; 结构体数组增加了很多数据类型,以前sum函数就不知道怎么办了吧, vector<Employee> staff; //total salary or total vacation days? sum(staff.begin(), staff.end(), 0); 这个例子而言,我想计算员工薪水里面最高的,和休假最少的,或者我想计算全部员工的总共休假多少天。那么面对这么多的需求,我们是否可以泛型一些呢?怎样解决这些问题呢? 引入更抽象化的函数编程——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; } reduce函数 需要增加一个参数 op,这个参数可以是一个函数,来完成我们想要的业务操作。 比如下面的业务操作函数:我们来求员工的工资和、最大工资 double sum_salaries = reduce( staff.begin(), staff.end(), 0.0, {return s + e.salary;} ); double max_salary = reduce( staff.begin(), staff.end(), 0.0, {return s > e.salary? s: e.salary; } ); C++STL中的count_if(): 下面这个示例中,先定义了一个函数对象counter(struct里定义函数)。这个函数对象需要一个Cond的函数对象,它是个条件判断函数,如果满足条件,则加 1,否则加 0。 然后,用上面的counter函数对象和reduce函数共同来打造一个counter_if算法 当条件满足的时候我就记个数,也就是统计满足某个条件的个数。 //对象counter,满足Cond函数的条件,就将参数c 加 1。 template<class T, class Cond> struct counter { size_t operator()(size_t c, T t) const { return c + (Cond(t) ? 1 : 0); } }; //count_if函数,返回上面文章中编写使用的reduce函数 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 万元的员工的数量时,参数3为Cond条件函数,{ return e.salary > 10000; }一行代码就完成了 size_t cnt = count_if(staff.begin(), staff.end(), { return e.salary > 10000; }); 函数式编程 修饰器模式 面向对象编程 原型编程范式 逻辑编程范式 前两小段,是编程范式的简单介绍,C语言到C++的演化, 未完待续。。。。。
转载自://www.cnblogs.com/fisherss/p/11503712.html