C++进阶与拔高（五）（C++ STL utility和iterator）

2.3 utility

utility是一个很小的头文件，它包括了贯穿使用在STL中的几个模版的声明。现在utility中只有模板类pair、一些与之相关的模版函数和操作符，以及其他四个模版操作符了。pair模板类用于将2个对象表示成一个对象。四个模版操作符赋予了”==”和”<”新的内涵。

pair<T,U>	构造模板类pair，x为pair的一个对象，x的第一个成员对象可以写为x.first，其类型是T。
make_pair	使用该工具可以实时产生一个pair对象。但不能依赖make_pair产生一个含有一个或多个常量成员的pair对象，因为模版函数在检测模版时将忽略掉所有的const属性。
operator==	比较2个对象是否相等，若x和y对应的成员都相等的话，则可以说x和y是相等的。
operator<	假设在pair的2个成员对象中，第一个成员对象的权重总是大于第二个的，若在此情况下可以确定x.first<y.first的话，那x就小于y。 template<class T,class U> inline bool operator<(const pair<T,U>& x, const pair<T,U>& y) {return (x.first<y.first\|\|!(y.first<x.first)&&x.second<y.second);}
operator!=
operator>
operator<=
operator>=

2.3.1 功能描述

utility里包含两样东西：通用关系比较操作符和pair。常用的比较操作符如上表所示，pair则是可以通纳2种类型的容器。

namespace std
{
template<class T, class U>
    struct pair;
//TEMPLATE FUNCTION
template<class T, class U>
pair<T,U> make_pair(const T& x, const U& y);//该模板函数返回pair<T,U>(x,y)
template<class T, class U>
bool operator==(const pair<T,U>& x, const pair<T,U>& y) //该模板函数返回!(x==y)
template<class T, class U>
bool operator!=(const pair<T,U>& x, const pair<T,U>& y)
template<class T, class U>
bool operator<(const pair<T,U>& x, const pair<T,U>& y)
……//此处省去了对另外4个模板类的声明
namespace rel_ops
{
template<class T>
bool operator!=(const T& x, const T& y);
template<class T>
bool operator<=(const T& x, const T& y);
template<class T>
bool operator>(const T& x, const T& y);
template<class T>
bool operator>=(const T& x, const T& y);
} //namespace rel_ops
} //namespace std

rel_ops嵌套定义于命名空间std中，若想使用这些模板操作符，就需要在程序中写出以下声明：

using namespace std::rel_ops;

2.3.2 使用utility

模板类pair可以用于调用返回一对相关值的函数，若这2个类型均不是常量类型，就可以通过调用make_pair(x,y)实时地产生一个pair对象来存储x和y。

模板类pair中关于pair结构体的定义。

//utility standard header
#ifndef UTILITY_
#define UTILITY_
#include<iosfwd>
namespace std
{  
  //TEMPLATE STRUCT pair
template<class T1, class T2> 
struct pair
{
  typedef T1 first_type;
  typedef T2 second_type;
pair(): first(T1()), second(T2()) {}
pair(const T1& V1, const T2& V2): first(V1),second(V2){}
  template<class U1, class U2>
pair(const pair<U1,U2>& x): first(x.first), second(c.second){}
  T1 first;
  T2 second;
}//pair TEMPLATE

2.4 iterator

整个STL几乎都是由模板组成的，模版所能够知道的就是被用来特化它的那些类型如果想传递更多的信息通常有两种做法：一是在模版中新增模版参数，来夹带所需的信息；二是让迭代器本身就包含这些信息，简单的来说，就是让所定义的所有迭代器类型都派生于同一个基类，然后在这个基类中定义所有必要的属性。这个基类的一个原型就是模板类iterator。代码如下：

2.4.1 迭代器标签

模版参数定义的迭代器类型，必须是在下面已经定义好的几种迭代器标签之一：

struct output_iterator_tag{};
struct input_iterator_tag{};
struct forward_iterator_tag: public input_iterator_tag{};
struct bidirectional_iterator_tag: public forward_iterator_tag{};
struct random_access_iterator_tag: public bidirectional_iterator_tag{};
class My_it: public iterator<forward_iterator_tag, char, long>{……}//在此基础上构造一个前向迭代器，可以用来遍历元素类型为char的二进制文件，差距类型为long

这样，算法就可以从类型My_it::iterator_category中检测到迭代器的种类信息，从My_it::distance_type中得到差距类型信息。按照一般的惯例，输出迭代器都是由基类iterator <output_iterator,void,void,void,void>所派生出来的。我们唯一能用输出迭代器完成的操作是存储一个元素，而且这个值不能再读回来。

例 2.4.1 模版函数reverse用来反转一个序列，即第一个元素与最后一个元素交换，第二个与倒数第二个交换，依此类推。通过使用模版函数iter_swap来进行实际的交换操作，可以使用2个双向迭代器来完成这项工作。

template<class BidIt> inline
void reverse(BidIt first, BidIt last)
{
  for(;first!=lase&&first!=--last;++first)
iter_swap(first,last);
}
这2个迭代器实际上是随机存取迭代器，上述代码可以修改如下：
template<class BidIt> inline
void reserve(RanIt first, RanIt last)
{
  for(;first<last;++first)
iter_swap(first,--last);
}

上述的模版特化机制可以视为一种switch语句，允许我们在任意可以使用迭代器的地方使用对象指针来替代迭代器。但是上述方案不适合单纯由指针构成的迭代器。解决方案是引入称为iterator_traits的另一个模板类。它不仅可以返回iterator中定义的5种基本类型，也可以对指针进行特化。

template<class It>
struct iterator_traits
{
  typedef typename It::iterator_category iterator_category;
  typedef typename It::value_type value_type；
typedef typename It::distance_type distance_type;
typedef typename It::pointer pointer;
typedef typename It::reference reference;
};
template<class It>
struct iterator_traits<T *>
{
  typedef random_access_iterator_tag iterator_category;//所有的指针都是随机存取迭代器
  typedef T value_type；
typedef ptrdiff_t distance_type;
typedef T *pointer;
typedef T& referenc;
};

2.4.2 Val_type

如果想知道一个类型为It的迭代器所关联的元素类型为T，原则上可以写出它的类型名称：iterator_traits<It>::value_type。但是当It是一个对象指针时，还需要依赖于部分特化。如果编译器支持部分特化，我们就可以使用模版函数Val_type，程序如下。

template<class It> inline
  typename iterator_traits<It>::value_type *Val_type(It) 
  {rerurn 0;}

2.4.3 Dist_type

同样如果想确定两个类型为It的迭代器之间差距类型时，可以直接简单的写出类型名称：iterator_traits<It>::distance_type。实际中，使用的是模板函数Dist_type。