• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

《Essential C++》读书笔记 之 泛型编程风格

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

2014-07-07

3.1 指针的算术运算(The Arithmetic of Pointer)

  新需求1

  新需求2

  新需求3

3.2 了解 Iterators(泛性指针)

3.3 所有容器的共通操作

3.6 如何设计一个泛性算法

  Function Objects

  Function Object Adapters

 

 

Standard Template Library(STL)主要由两种组件构成:

  • 一是容器(container),包括vector,list,set,map等类;
  • 另一种是用以操作这些容器类的所谓泛型算法(generic algorithm),包括find(),sort(),replace(),merge()等等。

容器概述

vector和list这两个容器是所谓的序列式容器(sequential container)。序列式容器会依次维护第一个元素、第二个元素......直到最后一个元素。我们在序列式容器上主要进行所谓的迭代(iterate)操作。

map和set这两种容器属于关联式容器(associative container)。关联式容器可以让我们快速寻找容器中的元素。

所谓map乃是一对对的key/value组合。key用于搜索,value要存储或取出数据。

所谓set,其中仅含有key。我们对它进行查询操作,为的是要判断某值是否存在其中。例如:我们想要建立一组索引表,用来记录新闻、故事中出现的字,我们希望一些中性字眼,如the,an,but排除掉。我们可以把这些中性字放在exclude_word的一个set中,每次放入某个字到索引表之前,查询一下exclude_word。若有,忽略;反之,加入。

泛型算法概述

所谓泛型算法,提供了许多可施行于容器及数组型别上的操作行为。这些算法之所以称为泛型(generic),因为它们和它们所要操作的元素型别无关。

泛型算法是通过function template技术,达成“与操作对象之型别相互独立”的目的。

3.1 指针的算术运算(The Arithmetic of Pointer)


 返回

假设我们需要一个函数find()要完成以下任务。给定一个存储整数的vector,以及一个整数值。如果此值存在于vector内,返回一个指针指向该值;反之,返回0。

1 int *find(const vector<int>&vec, int value)
2 {
3     for(int ix=0;ix<vec.size();++ix)
4         if(vec[ix]==value)
5             retrun &vec[ix];
6     return 0;
7 }
View Code

 

新需求1:要求这个函数不仅可以处理整数,也可以处理任何型别。其实,这个任务其实要求我们将泛型算法find()以fuction template的形式呈现:

1 template <typename elemType>
2 elemType *find(const vector<elemType>&vec, const elemType &value)
3 {
4     for(int ix=0;ix<vec.size();++ix)
5         if(vec[ix]==value)
6             retrun &vec[ix];
7     return 0;
8 }
View Code

 

新需求2:要求这个函数可以处理vector和array内任意型别的元素。

这个任务难度较大,我们将它分割一下:

(1)将array的元素传入find(),而不指明该array;

(2)将将vector的元素传入find(),而不指明该vector。理想情况下,这两个问题的解法会包含我们最初问题的共同解法。

我们先看任务(1):首先要了解array是如何传入函数的,看如下代码:

int min(int *arrary){};

当数组被传递给函数,或者由函数返回时,仅有第一个元素的地址会被传递。

由于函数find()需要知道何时停止对array的读取。

解法之一是:增加一个参数,用来表示array的容量,声明如下:

template <typename elemType>
elemType *find(const elemType *arr, int size, const elemType &value);

 解法之二是:传入另一个地址,指示array读取操作的终点。我们将此值成为“哨兵”。

template <typename elemType>
elemType *find(const elemType *arr, const elemType *sentinel, const elemType &value);

解法二最让人感兴趣的地方是:array从参数表中彻底消失了---这形同解决了小问题(1)

解法一实现:

 1 template <typename elemType>
 2 elemType *find(const elemType *arr, int size, const elemType &value)
 3 {
 4     if(!array||size<1)
 5         return 0;
 6     for(int ix=0;ix<size;++ix)
 7         if(arr[ix]==value)
 8             retrun &arr[ix];
 9     return 0;
10 }
View Code

上述代码中,虽然array是以第一个元素的指针传入find()中,但我们可以看到,仍然可以通过subscript(下标)运算符存取array的每个元素,就如同此arr是个对象(而非指针形式)一般。why?

因为事实上所谓的下标操作就是将array的起始值加上索引值,产生出某个元素的地址,然后该地址在被提领以返回元素值。例如:

    arr[2];

会返回array的第三个元素。

   *(arr+2)

也返回第三个元素的值。 这里的2,在指针运算中,要把“指针所指之型别”的容量大小考虑进去。若arr第一个元素为1000,那么arr+2的地址为1000+2*4。

解法二实现

 1 template <typename elemType>
 2 elemType *find(const elemType *first, const elemType *last, const elemType &value)
 3 {
 4     if(!first||!last)
 5         return 0;
 6     for(;first!=last;++first)
 7         if(*first==value)
 8             retrun first;
 9     return 0;
10 }
View Code

调用解法二函数find()

    string sa[4]={"when","where","who","what"};
    string *ps=find(sa,sa+3,sa[3]);

再看任务(2):这个任务是说,无论vector元素类型为何,都能一一存取vector内的每个元素。因为vector和array相同,都是一一块连续内存存储所有元素,所以它们的处理方式相同。但是,切记:vector可以为空。

如果定义一个空的vector,执行是就会抛错,见如下代码:

    vector<string> vec;
    find(&vec[0],&vec[vec.size()-1],search_value);

我们可以封装一下“取用第一个元素的地址”,“取用最后一个元素的地址”

 1 template <typename elemType>
 2 inline elemType * begin(const vector<elemType> &vec)
 3 {
 4     return vec.empty()?0:&vec[0];
 5 }
 6 template <typename elemType>
 7 inline elemType * end(const vector<elemType> &vec)
 8 {
 9     return vec.empty()?0:&vec[vec.size()-1];
10 }
11 
12 find(begin(vec),end(vec),search_value);
View Code

 

新需求3:令它也支持list类。

这又是一个难题。list也是一个容器。不同的是,list元素以一组指针相互链接(linked):向前(forward)指针用来寻址下一个(next)元素,回向(backward)指针用来寻址上一个(preceding)元素。

因此,指针的算术运算并不适用于list,因为指针的算术运算必须首先假设所有元素都存储在连续的空间里,然后才能根据当前指针,加上元素大小之后,指向下一个元素。

首先浮起的念头是,多写一份find()函数,使其有能力处理list对象。我们的理由是:array、vector、list的指针行为大相径庭,以至于无法以一个通用的语法来取得其下一个元素。

这样的说法错综复杂。对的部分是,他们的地层指针运行方式,就标准语法而言的确大不相同。错的部分是,我们不需要提供另一个find()函数来支持list。事实上,除了参数表之外,find()的实现内容一点也不需要改变。

解决这个问题的方法是,在底层指针的行为处理上提供一层抽象化机制,取代原来的“指针直接操作的“方式 。

3.2 了解Iterators(泛型指针)


 返回

那么,如何对底层指针的操作实现抽象化呢?

  • 第一:需要一组对象,提供有如内建运算符(++, *, ==, !=)一般运算符,并允许我们只为这些运算符提供一份代码实现。我们可以利用c++的类机制来完成。
  • 第二:要设计一组iterator classes,让我们得以使用“和指针相同的语法”进行程序的撰写。

实现上述问题后,我们就可以得到方法find()代码: 

 1 template <typename IteratorType, typename elemType> 
 2 IteratorType find(IteratorType first, IteratorType last, const elemType &value)
 3 {
 4     if(!first||!last)
 5         return 0;
 6     for(;first!=last;++first)
 7         if(*first==value)
 8             retrun first;
 9     return 0;
10 }
View Code

这样,array、vector和list就都能调用它了:

 1     const int asize=8;
 2     int ia[asize]={1,1,2,3,5,8,13,21};
 3     vector<int> ivec(ia,ia+asize);
 4     list<int> ilist(ia,ia+asize);
 5 
 6     int *pia=find(ia,ia+asize,1024);
 7 
 8     vector<int>::iterator it;
 9     it=find(ivec.begin(),ivec.end(),1024);
10 
11     list<int>::iterator iter;
12     iter=find(ilist.begin(),ilist.end(),1024);
View Code

3.3 所有容器的共通操作


 返回

以下为容器类(以及string类)的共同操作:

  • equality(==)和inequality(!=)运算符,返回true或false。
  • assignment(=)运算符,将某个容器复制给另一个容器。
  • empty()会在容器无任何元素是返回true,否则返回false。
  • szie()传用容器内当前含有的元素数目。
  • clear()删除所有元素。

每个容器还提供如下函数:

  • begin()返回一个iterator,指向容器第一个元素。
  • end()返回一个iterator,指向容器的最后一个元素的下一个位置。
  • insert()将一个或某个范围内的元素安插到容器内
  • erase()将容器内的单一元素或某个范围内的元素删除。 

3.6 如何设计一个泛性算法


 返回

现有个函数,用户给一个整数vector,我们必须返回一个新的vector,其中内含原vector之中小于10的所有数值。它的代码如下:

1 vector<int> less_than(const vector<int> &vec,int less_tan_val)
2 {
3     vector<int> nvec;
4     for(int ix=0;ix<vec.size();++ix)
5         if(vec[ix]<less_tan_val)
6             nvec.push_back(vec[ix]);
7     return nvec;
8 }
View Code

 

新需求:这个函数允许用户指定不同的比较操作,如大于、小于等等。如何can能将“比较操作”参数化呢?

解法:以函数调用取代less-than运算符,加入第三个参数pred,用它来指定一个函数指针,下面是这个函数声明:

vector<int> filter(const vector<int> &vec,int filter_value, bool (*pred)(int,int));

这个指针可以指向不同的比较函数:

bool less_than(int v1,int v2){return v1<v2 ? true : false;)
bool greater_than(int v1,int v2){return v1>v2?true:false;)

函数filter第一个版本的定义:

1 vector<int> filter_ver1(const vector<int> &vec, int filter_value, bool (*pred)(int,int))
2 {
3     vector<int> nvec;
4     for(int ix=0;ix<vec.size();++ix)
5         //调用pred所指函数比较vec[ix]和filter_value
6         if(pred(vec[ix],filter_value))
7             nvec.push_back(vec[ix]);
8     return nvec;
9 }
View Code

调用filter_ver1:

1     vector<int> big_vec;
2     int value;
3     //...填充big_vec和value
4     vector<int> lt_10=filter_ver1(big_vec,value,less_than);
View Code

Function Objects


 返回 

所谓function object,是某种class的实体对象,这类classes对function call运算符进行了重载操作,如此一来,可是function object被当成一般函数来使用。

function object实现出我们原本可能以独立函数加以定义的事物。但又何必如此呢?主要是为了效率。我们可以令call 运算符成为inline,因而消除“通过函数指针来调用函数”时需付出的额外代价。

标准程序库事先定义了一组function objects,分为算术运算(arithmetic)、关系(relational)、逻辑运算(logical)三大类。以下列表中的type会被替换为内建型别或class 型别:

算术运算:plus<type>,minus<type>,...

关系:less<type>,greater<type>,...

逻辑运算:分别对应与&&,||,!运算符:logical_and<type>,logical_or<type>,logical_not<type>

看如何使用function object:

1 //欲使用事先定义的function objects,首先得含入相关头文件
2 #include <functional>
3 
4     //sort()会使用底部元素型别所供应的greater_than运算符,将匀速递减排序
5     sort(vec.begin(),vec.end(),greater<int>);
View Code

其中的: greate<int>{}会产生一个匿名的class template object,传给sort()。

Function Object Adapters


 返回

fuction object less<type>期望外界传入两个值,如果第一个值小于第二个值就返回true。但在本例中,每个元素都必须和用户指定的数值进行比较。理想情况下,我们需要做的就是将less<type>转化为一个一元运算符。这可以通过“将其第二个参数绑定(bind)至用户指定的数值”而达成。这么一来,less<type>便会将每个元素拿出来一一与用户指定的数值比较。

标准程序库提供的adapter(配接器)便应此而生。

见使用了bind2nd adapter的函数filter_ver2: 

 1 vector<int> filter_ver2(const vector<int> &vec, int filter_value, less<int> &lt)
 2 {
 3     vector<int> nvec;
 4     vector<int>::const_iterator iter=vec.begin();
 5 
 6     //bind2nd(lt,val)会把val绑定于less<int>的第二个参数上,这样,less<int>会将每个iter和val比较。    
 7     while((iter=find_if(iter,vec.end(),bind2nd(lt,val))))!=vec.end())
 8     {
 9             nvec.push_back(vec[ix]);
10             iter++;
11     }
12     return nvec;
13 }
View Code

接下来如何消除filter()与vector元素型别的相互馆来,以及filter()与vector容器类型的相依关联,意识filter更加泛型化呢?

为了消除它和容器类型间的相依性,我们传入一对iterator[first,last],并将在参数表中增加另一个iterator,用以指定从何处开始复制元素。见如下代码:

 1 template <typename InputIterator,typename OutputIterator, typename ElemType, typename Com>
 2 OutputIterator filter_ver1(InputIterator first, InputIterator last, OutputIterator at, const ElemType &val, Com pred)
 3 {
 4     while((first=find_if(first,last,bind2nd(pred,val))))!=last)
 5     {
 6             cout<<"found value: "<<*first;
 7             *at++=*first++;
 8     }
 9     return at;
10 }
View Code

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C# 同步转异步 AutoResetEvent发布时间:2022-07-13
下一篇:
【转】符合w3c标准的最新flash(swf)网页插入代码发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap