模版介绍

STL中主要由容器，迭代器，算法三个部件构成

容器用来管理对象的集合，每一种容器都有自己的优缺点，储存的方式等都有所不同，使用时需根据程序的需求考虑不同容器的效率来选择

迭代器为所有容器提供了一组公共接口，并且，每一种容器都提供自己的迭代器

STL中把数据和算法分开，赋予了STL极大的弹性

下图演示了三个部件之间的交互关系

可以看出，迭代器是容器和算法之间的接口，总体说来，STL使容器与算法分离，使其二者不需要相互依赖，而迭代器又将算法和不同的容器stick在一起，从而使需要的算法能够运用到不同的容器上（例如可以对多种容器使用find函数，中介便是迭代器）。

模版是C++的一种特性，允许函数或类通过泛型的形式表现和运行。模版的类型有 类模版，函数模版， 成员模版等。

模版的实例化是从模版构建出一个真正函数或类的过程。模版被编译了两次。没有被实例化之前，检查模版代码本身是否有语法错误，在实例化期间，检查对模版代码的调用是否合法。

函数模版是参数化的一族函数。通过模版函数，可以定义一系列函数。这些函数都是基于同一套代码，但是可以作用在不同型别的参数上

C++类模版，与函数模版类似，类也可以通过参数泛化，从而可以构建出一族不同型别的类实例。类模版实参可以是某一型别或常量。

类模版的特化，允许对一个类模版的某些模版参数类型做特化。特化的作用在于：对于某种特殊的型别，可能可以做些特别的优化或提供不同的实现；避免在实例化类的时候引起一些可能产生的诡异行为。类模版同样可以特化或者偏特化。 如果有不止一个偏特化铜等程度地能匹配某个应用，那么该调用具有二义性，会产生编译错误。

C++类模版参数可以有默认值。

Traits(特性)

Traits在面向对象程序设计中，是一个不可实例化（uninstantiable）的方法与类型的集合，为一个对象或算法提供了策略（policy）或实现自身界面的细节功能。

Traits作为模板类，既声明了统一的界面（包括类型、枚举、函数方法等），又可以通过模板特化，针对不同数据类型或其他模板参数，为类、函数或者通用算法在因为使用的数据类型不同而导致处理逻辑不同时，提供了区分不同类型的具体细节，从而把这部分用Traits实现的功能与其它共同的功能区分开来。例如，容器的元素的不同数据类型，或者iostream是使用char还是wchar_t。

C++标准模板库中大量使用了traits。将因为模板形参（包括类型形参、非类型形参）不同而导致的不同抽取到新的模板（即traits）中去；然后通过traits的模板特化来实现针对具体情况的优化实现。一个traits包括了enum、typedef、模板偏特化（template partial specialization）。其中，enum定义了各种类的标识的统一表示；typedef定义了各个类的各自不同的类型定义，这对于使用模板元编程（template meta-programming）的灵活性非常重要；模板偏特化用于实现各个类的不同功能。

Trabit Class 如何设计

确认若干希望将来可以取得的类型信息，比如对于Iterator而言，我们希望可以取得其category

为信息选择一个名称，例如 iterator_category

提供一个template和一组特化版本，内含你希望支持的类型相关信息

总结:

建立一组重载函数或者函数模板(例如doAdvance)，彼此之间的差异只在于各自的trabit参数。令各个函数实现码与其接受之trabits信息相应和

建立一个控制函数或者函数模板(例如advance)，它调用上述的"劳工函数"，并传递traits class提供的信息

迭代器 Iterator

迭代器是一种 Pointer-like class。是指针的泛化。迭代器本身是一个对象。在STL中迭代器是容器与算法之间的接口。在STL中，算法和容器是分离的，而迭代器就是它们之间的粘合剂。如 find 算法，接收一对迭代器作为参数，分别指向容器的开始和结束。

Iterator也是一种很长的设计模式的手法，用来遍历一个Resource，这样可以屏蔽很多内部操作，直接利用了C++的operator++/operator--/operator+/operator-重载。

当然C++的iterator也是有好几个分类的。

1.输入迭代器(input iterator)

2.输出迭代器(output iterator)

3.前向迭代器(forward iterator)

4.双向迭代器(bidirectional iterator)

5.随机存取迭代器(random access iterator)

输入迭代器(input iterator)

input iterator就像其名字所说的,工作的就像输入流一样.我们必须能

取出其所指向的值

访问下一个元素

判断是否到达了最后一个元素

可以复制

因此其支持的操作符有  *p,++p,p++,p!=q,p == q这五个.凡是支持这五个操作的类都可以称作是输入迭代器.当然指针是符合的.

输出迭代器(output iterator)

output iterator工作方式类似输出流,我们能对其指向的序列进行写操作,其与input iterator不相同的就是*p所返回的值允许修改,而不一定要读取,而input只允许读取,不允许修改.

支持的操作和上头一样,支持的操作符也是 *p,++p,p++,p!=q,p == q.

前向迭代器(forward iterator)

前向迭代器就像是输入和输出迭代器的结合体,其*p既可以访问元素,也可以修改元素.因此支持的操作也是相同的.

双向迭代器(bidirectional iterator)

双向迭代器在前向迭代器上更近一步,其要求该种迭代器支持operator--,因此其支持的操作有*p,++p,p++,p!=q,p == q,--p,p--

随机存取迭代器(random access iterator)

即如其名字所显示的一样,其在双向迭代器的功能上,允许随机访问序列的任意值.显然,指针就是这样的一个迭代器.

对于随机存取迭代器来说, 其要求高了很多:

可以判断是否到结尾(a==b or a != b)

可以双向递增或递减(--a or ++a)

可以比较大小(a < b or a > b or a>=b ...etc)

支持算术运算(a + n)

支持随机访问(a[n])

支持复合运算(a+= n)

容器 Containter

我们所用的常用的数据结构不外乎 array, list, tree, stack, queue, hash table, set, map 等。这些数据结构分为序列式（sequence）和关联式（associative）两种。

Sequence Container : array, vector, list, deque

Associative Containter : set, map, multimap, unordered map

对于Sequence Container，我们一般认为这个是一个动态的数组，只是实现上各有差异，可以为链表，这个差异就是索引时候的速度，数组是O(1), 链表是O(n)。且从空间上来说动态数组在capacity相同的时候空间占用会比链表要少一些。但是链表在指定位置插入的成本会比数组少很多，是O(1)。

题目说明：

给定一个 vector:v1 = [0, 0, 30, 20, 0, 0, 0, 0, 10, 0]，希望通过not_equal_to 算法找到到不为零的元素，并复制到另一个 vector: v2。

在查了not_equal_to用法后，写下的第一个版本：

#include <vector>

#include <functional>

#include <iostream>

using namespace std;

int main(intargc,char** argv)

{

vector v1 {0,0,30,20,0,0,0,0,10,0};

vector v2;

constintFIND_NUM =0;

for(inti : v1) 

{if(not_equal_to()(i, FIND_NUM)){            v2.push_back(i);        }    }for(inti : v2)cout<< i << endl;return0;}

也就是把i!=FIND_NUM改成了not_equal_to()(i, FIND_NUM)这样的判断条件，虽然符合题目要求，但不符合题目初衷。

进一步的，我使用了find_if算法进行不为0元素的查找，由于每次都只能找到第一个不为0，所以迭代器在每次找到一个元素后需要移动到下一个元素的位置。

也是符合题目要求，但不符合题目意图。我想这题是希望通过算法组合，直接一行代码搞定需求。所以像find_if这样只能寻找到第一个符合条件元素的也不适用于这题。继而我找到了copy_if。

其中的问题显而易见，由于无法使用push_back，必须先让v2拥有v1一样的大小，才能保证不溢出，并且需要一个迭代器记录copy后v2中符合条件的最后一个元素位置，进行resize。

尽管vector在内部处理的时候会向系统申请一块空间，本质上来说v2初始化为v1相同的大小不一定就浪费空间了，但是这样的做法还是过于麻烦。

上面的做法只差了一步，如何每次插入到v2后面一个位置，通过back_inserter可以解决。

由于copy_if是C++11才有的，之前可以用remove_copy_if替代，且筛选条件也需要做下修改,

用课上讲的erase+remove_if也可以，但需要事先拷贝v1所有元素到v2，或者先修改了v1的数据，留下的拷贝到v2.

改变原数组的方法并不可取。另外也可以使用partition_copy将v1分成0和非0元素两组，

以上所有代码当中的

for(inti:v2)

cout << i << endl;

也可以改成

copy(v2.begin(), v2.end(), ostream_iterator(cout,"\n"));

在有算法可以使用的时候，尽量使用算法，比如将v1有效的数据拷贝入v2的时候，不考虑用push_back/insert，因为后者相对来说效率低。