（四）泛型编程
STL是一种泛型编程，面向对象的编程关注的是数据结构，而泛型编程关注的是算法。它们的共同点是抽象和创建可重用代码。
1.迭代器
基于算法的要求，来设计基本迭代器的特征和基本容器的特征。容器类模板是将算法独立于存储的数据类型，而迭代器是将算法独立于各种容器类模板，使得某种算法可以使用各容器类的迭代器用相同的方式来处理不同的容器类型。模板提供了存储在容器中的数据类型的通用表示，使得算法独立于不同的数据类型，而迭代器则提供了遍历不同容器类数据的通用表示，使得算法独立于不同容器（比如数组和链表）的具体的数据结构。
对于普通的数组来说，相应类型的数组指针就可以作为迭代器，而对于更一般的类对象来说，迭代器也是相应的类对象（但是具有与指针相似的性质），可以对迭代器使用解除引用运算符（解除引用后就是相应的存储的数据）以及++运算符等（这些运算符在迭代器类中进行了重载），一般来说，每个容器类都定义了自己的迭代器，而且迭代器的类型各不相同，为的是可以实现不同的功能。
为了区分++运算符的前缀版本和后缀版本，c++中规定了将operator++作为前缀版本，将operator++（int）作为后缀版本（括号中的参数永远不会用到，只是后缀版本的一种标识，因此不必有变量名称），前缀版本是先加后返回加了之后的值，而后缀版本是返回加之前的值，并进行++操作。
为了能够统一不同的容器类，c++规定迭代器都有起始迭代器和超尾迭代器（超尾标记），比如链表容器类就要有个没有数据的超尾结点。begin()和end()就是指向起始位置和超尾位置的迭代器，我们无需知道超尾是如何实现的，也无需知道迭代器是如何实现的，我们仅仅知道迭代器的通用方法即可。注意，一个类的迭代器，我们仅需要这样使用，比如vector<double>::iterator pp;就是一个指向vector<double>类对象的迭代器，其他模板类也是如此。
2.迭代器的类型
输入迭代器：这个输入是对程序而言的，即从容器中读取数据，解除引用可以让迭代器得到容器的数据。输入迭代器是单向迭代器，可以递增，但不可以倒退。输入迭代器还是单通行的，也就是说不依赖于前一次遍历的值也不依赖于本次已经遍历的值。
输出迭代器：表示程序用这个迭代器将内容输出到容器（也是对程序而言的），对其解除引用可以让程序修改容器值，而不是读取。简而言之，对于单通行，只读算法，可以使用输入迭代器；而对于单通行，只写算法，可以使用输出迭代器。
正向迭代器：和输入迭代器与输出迭代器相同，正向迭代器只使用++运算符来遍历容器，正向迭代器可以读取也可以写入，如果使用const修饰可以设置成只能读取。正向迭代器就是输入迭代器和输出迭代器的结合体，并且正向迭代器是多次通行的。
双向迭代器：可以双向遍历容器，比如前一个递加，后一个递减。
随机访问迭代器：也就是可以跳到容器中的任何一个元素，上面的迭代器可以递加递减等，但不可以加上一个整型，也就是随机访问。这里的随机并不是指随机指向一个元素，而是我希望指向哪个元素都可以立即指向它，也就是直接跳到容器的任何一个元素，这就叫作随机访问。随机访问迭代器支持上面的双向迭代器的所有功能，同时还支持重载的加法运算，并且迭代器可以进行比较运算。
3.迭代器的层次结构
高层次的迭代器拥有低层次迭代器的全部功能，输入和输出迭代器是最低层次的迭代器；再是正向迭代器；再是双向迭代器；再是随机访问迭代器。一般我们可以直接使用随机访问迭代器，只有在特定的具有安全性要求的场合下我们才使用特定类型的迭代器。随机访问迭代器层次下的迭代器没有[]运算和加法减法等运算。
4.概念，改进和模型
各种迭代器的类型只是一种概念性的描述，并不是目前已经实现和存在的，比如list<double> a;就是一个双向迭代器，而vector<double> b;就是一个随机访问迭代器。
上面讲到的迭代器是更多的是一种要求，而不是类型，这种要求就是概念。概念的类似继承的关系叫作改进，比如双向迭代器就是正向迭代器的改进；概念的具体化叫作模型。比如指向一个int类型的常规指针就是一个随机访问迭代器的模型。
可以将STL算法用于常规数组，因为数组指针可以看成是一种随机访问迭代器。STL提供了一组预定义的迭代器，比如copy（a,b,c）;函数就可以将迭代器a，b的内容复制到c迭代器位置，也就是将一个容器的内容复制到另一个容器的相应位置；使用这种copy的方法，我们可以将容器的内容输出到输出流中，首先我们要定义一个输出流的迭代器（或者可以被称为适配器），比如可以包含文件:
#include <iterator>
ostream_iterator<int,char> out_iter(cout,””);//定义输出流迭代器，输出类型为int，输出的字符类型为char，输出以空格分隔，使用cout输出到屏幕
copy(dice.begin(),dice.end(),out_iter);
这种方法可以使容器类的输入输出更为方便。
5.其他有用的迭代器
c++的STL中，迭代器也是一种类模板，比如istream_iterator<int,char> a(cout,”;”);这种输出流迭代器。STL提供了一系列的迭代器来方便对数据的处理和输入输出等操作。除了istream_iterator和ostream_iterator迭代器之外，还有reverse_iterator,back_insert_iterator，front_insert_iterator和insert_iterator。
reverse_iterator：对reverse_iteratora执行递增操作导致它递减，这主要是为了简化已有的函数（通过这种反转的迭代器可以使递增输出的函数来递减输出）。比如vector模板类中有一个rebegin()和rend()的函数，这两个函数分别返回超尾迭代器和指向第一个元素的迭代器，但是都是reverse_iterator类型的迭代器。因为对反向迭代器的递增操作就是递减，因此可以使用如下的方法来反向显示容器的内容：copy(dice.rebegin(),rend(),out_iter);这样甚至不必声明反向迭代器。这里要注意的是对于反向迭代器来说，对它使用解除引用，相当于对它递减1之后再使用解除引用（本质是指向它的前一个元素），这就是反向迭代器的特殊补偿。
back_insert_iterator，会将内容插入到容器的尾部；front_insert_iterator，会将内容插入到容器的头部；insert_iterator，可以将内容插入到容器的构造参数位置的前面，它有两个构造参数，一个是容器的名称，另一个是指向容器的要在前面插入内容的元素的迭代器。这三个迭代器都是输出容器迭代器的概念模型（输出迭代器就是只写）。使用方法：要为名为dice的vector<double>容器创建一个back_insert_iterator迭代器，可以使用如下的方式，back_insert_iterator<vector<double> > back_iter(dice);，可以看出，迭代器也是一种模板，需要使用具体化的容器模板来对它进行具体化，而构造函数的参数就是具体的容器对象。这个迭代器模板是在<interator>中定义的，而一般的迭代器是在相应的容器的模板文件中定义的。必须使用容器类型来进行声明的原因是迭代器必须使用合适的容器类的方法。
6.容器种类
（1）容器概念：容器是存储对象的对象。被存储的对象必须是同一种类型的，可以是内置数据类型，也可以是OOP意义上的对象。不是任意类型的对象都可以添加到容器中的，只有那些具有复制构造函数和可赋值的类对象才可以添加到容器中（也就是复制构造函数和赋值运算符都是公有的）。
（2）容器要求：复杂度要求（线性复杂度，固定复杂度）（编译时间就是在编译的时候已经计算了所有的计算量）；返回类型要求。
复制构造和复制赋值以及移动构造和移动赋值之间的差别主要是：复制操作保留源对象，而移动操作可能修改原对象，还可以转让所有权而不做任何复制。通常移动操作的效率要高于复制操作。
（3）序列：可以通过添加要求来改进基本的容器概念，序列是一种重要的改进。序列中的元素具有特定的顺序（这里的顺序并不是说要由小到大，而是具有固定的不变的顺序）。
（4）有七种序列容器类型，下面加以介绍。
Vector：除序列外，vector还是一个可反转容器，vector模板类是最简单的序列类型，除非其他序列的优点能更好满足程序的要求，否则我们优先选取vector模板类来构造对象。
Deque类：在头文件<deque>中定义，在头文件中定义，表示双端队列，类似于vector容器，但与vector类相比不同点是，从起始位置执行插入和删除操作的时间复杂度也是固定时间，而不是像vector类那样从结尾处是固定时间，从开头和中间是线性时间。
List类：表示双向链表。与vector的区别是，所有的节点的插入与删除的时间都是固定时间。而vector类只有在结尾处是固定时间的插入，但是在开头和中间是线性时间的插入。因此，vector强调的是通过随机访问进行快速访问，而list类（双向链表）强调的是元素的快速插入和删除（list双向链表在任何位置的插入和删除都是固定时间）。list的典型的成员函数：sort()排序，splice(iterator pos,list<T,Alloc> x)将链表x插入到迭代器pos之前，并且是移动插入（不改变指向x的迭代器），unique()函数，就是将连续的相同的元素合并成一个。需要注意的是非成员的函数sort，因为sort函数需要随机访问迭代器，而链表可以执行快速插入的代价就是放弃随机访问，因此不能将链表应用于非成员的sort函数。
Foward_list类：每个节点只连接到下一个节点，而没有链接到上一个节点，因此是不可反转的容器。
Queue容器类：队列，功能更少，甚至不能遍历容器。它是一个适配器接口，功能是让底层类，默认为让deque展示典型的队列接口。也即是队列只能进行从结尾加，从开头删，是否非空等操作。
Priority_queue类：也是在queue头文件中声明的。默认的底层类是vector，功能与queue差不多，不同点或者说最大特点是最大的元素被移到队首（比如队列中的vip用户要优先服务）。使用方法：priority_queue<int> a;或者priority_queue<int> b(greater<int>);其中第二个构造函数是通过一个函数对象来进行初始化，里面的greater<int>()是一个预定义的函数对象，greater是一个函数对象类模板。
Stack：也是一个适配器类，它给底层类（我的理解是继承关系），默认为vector类提供了典型的栈接口。方法有压入，弹出，查看栈顶值（不能进行遍历，也就是不能查找，只能查看栈顶这元素），检查元素数目和检查是否为空等。函数分别是push,pop,top,size,empty等。
Array类：在头文件<array>中定义的，它并非STL容器，因为它的长度是固定的，也因此不能使用push_back和insert等调整容器大小的操作。但是它定义了operator []和at()函数，并且可以将很多标准STL算法用于对象，比如for_each()和copy()。
6.关联容器和无序关联容器
关联容器是对容器概念的另一个改进，关联容器将值与键关联在一起，可以用键来查看值。通常，对于一个容器X来说，X::value_type通常表示容器中储存的值的类型，对于关联容器来说，表达式X::key_type表示容器中的键的类型。关联容器的优点在于快速的检索信息，一般来说，关联容器有快速确定数据位置的算法，以便可以快速的插入和检索信息。关联容器通常是使用某种树来实现的（也就是数据结构中的树或二叉数的逻辑形式）。
STL提供有四种典型的关联容器：set，multiset,map,multimap这四种。set和multiset是在头文件<set>中定义的，而map和multimap是在头文件<map>中定义的。set是键和值的类型相同的一种关联容器，而multiset键和值的类型也是相同的，但是值可以有多个。同样，map是键和值类型不同的关联容器，值只有一个，multimap值可以有多个，键只能有一个。
set不能存储多个相同的值，因为它的键和值其实是一样的，而键只能有一个，是唯一的。set的模板构造函数和vector，list相似，都是用存储的类型来进行模板具体化，还有另外一个模板参数，就是指定用来进行比较的函数，默认就是less<>模板函数，如set<string,less<> > A;。set的构造函数也可以是两个迭代器，第一个指向第一个元素，第二个指向超尾元素，set的构造的对象会将相同的元素合并成一个，然后会将元素按照特定的规则排序（默认是less<>模板函数）。
无序关联容器是对容器概念的另一种改进，无序关联容器也将值和键连接在一起，并使用键来查找值。二者的区别是，关联容器是基于树结构的，而无序关联容器是基于数据结构哈希表的。旨在提高添加和删除元素的速度以及提高查找算法的效率。四种无序关联容器是：unordered_set,unordered_multiset,unordered_map,unordered_multimap。
网友评论