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技术，达成“与操作对象之型别相互独立”的目的。

返回

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

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

fuction template的形式呈现：

1 template 
2 elemType *find(const vector&vec, const elemType &value)
3 {
4     for(int ix=0;ixix)
5         if(vec[ix]==value)
6             retrun &vec[ix];
7     return 0;
8 }

返回

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

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

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

 1 template  
 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 }

这样，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);

返回

以下为容器类（以及string类）的共同操作：

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

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

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

返回

现有个函数，用户给一个整数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;ixix)
5         if(vec[ix]<less_tan_val)
6             nvec.push_back(vec[ix]);
7     return nvec;
8 }

新需求：这个函数允许用户指定不同的比较操作，如大于、小于等等。如何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 v1true : 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;ixix)
5         //调用pred所指函数比较vec[ix]和filter_value
6         if(pred(vec[ix],filter_value))
7             nvec.push_back(vec[ix]);
8     return nvec;
9 }

调用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);

返回 

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

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

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

算术运算：plus,minus,...

关系：less,greater,...

逻辑运算：分别对应与&&，||，！运算符：logical_and,logical_or,logical_not

看如何使用function object：

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

其中的： greate{}会产生一个匿名的class template object，传给sort()。

返回

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

标准程序库提供的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的第二个参数上，这样，less会将每个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 }

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

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

 1 template 
 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 }