概念
- 之前已经介绍过迭代器，知道了不同的数据结构都有自己专属的迭代器，不同的迭代器也有不同的特性，由于算法的接口是统一的，通过迭代器的不同属性，算法自动选择正确的执行流程，在完全任务的同时，也尽可能提高算法的执行效率。
- 那算法如何获知迭代器的属性呢？这一光荣的任务就是traits完成的。
- 在STL实现中，traits编程技术得到大量的运用，它利用了“内嵌类型”的编程技巧与C++的template参数推导功能，弥补了C++类型识别方面的不足。
- 通过traits，算法可以原汁原味的将迭代器的属性萃取出来，帮助算法正确高效的运行。
引子
1.以迭代器所指对象的类型声明局部变量
下面是一个以迭代器为模板形参的函数模板：
template<typename Iterator>
void func(Iterator iter)
{
//函数体
}
假如现在算法中需要声明一个变量，而变量的类型是迭代器所指对象的类型，应该怎么处理呢？
template<typename Iterator>
void func(Iterator iter)
{
*Iterator var;//这样定义变量可以吗？
}
上面的代码是不可以通过编译的，虽然C++支持sizeof()，但是并不支持typeof()，就算是用到RTTI性质中的typeid()，获取到的也仅仅是类型的名字，因此不能直接用来声明变量。此时可以利用函数模板的参数类型推导机制解决问题，例如：
template<typename Iterator, typename T>
void func_impl(Iterator iter, T t)
{
T temp;//这里就解决了问题
//这里做原本func()的工作
}
template<typename Iterator>
void func(Iterator iter)
{
func_impl(iter, *iter);//func的工作全部都移到func_impl里面了
}
int main(int argc, const char *argv[])
{
int i;
func(&i);
}
- 函数func作为对外接口，实际的操作却由函数func_impl执行，通过函数func_impl的参数类型推导，获取到Iterator指向对象的类型T，从而解决了问题。
2.以迭代器所指对象的类型声明返回类型
现在通过函数模板的参数类型推导解决了函数体内声明变量的问题，但问题又来了，如果需要返回类型是迭代器所指对象的类型又可以怎样做呢？
template<typename Iterator>
(*Iterator) func(Iterator iter)
{
//这样定义返回类型可以吗？
}
在这种情况下，模板的参数类型推导机制也无能为力了，因为它只能推导参数，并不能推导函数的返回类型。STL解决这种问题的办法就是内嵌类型声明，即在迭代器内部添加一种“特性”，通过这种“特性”，算法可以很容易地获知迭代器所指对象的类型，请看下面的代码：
template<typename T>
class Iterator
{
public:
typedef T value_type;//内嵌类型声明
Iterator(T *p = 0) : m_ptr(p) {}
T& operator*() const { return *m_ptr;}
//...
private:
T *m_ptr;
};
template<typename Iterator>
typename Iterator::value_type //以迭代器所指对象的类型作为返回类型，长度有点吓人！！！
func(Iterator iter)
{
return *iter;
}
int main(int argc, const char *argv[])
{
Iterator<int> iter(new int(10));
cout<<func(iter)<<endl; //输出：10
}
注意：
- 此处typename语法为说明Iterator::value_type为一种数据类型
- 函数func()的返回类型前面必须加上关键词typename，因为T是一个template参数，编译器在编译实例化func之前，对T一无所知，就是说，
- 编译器并不知道Iterator::value_type是一个类型，
- 或者是一个静态成员函数，
- 还是一个静态数据成员，
- 关键词typename的作用在于告诉编译器这是一个类型，这样才能顺利通过编译。
原生指针也是一种迭代器
- 之前在介绍迭代器的分类之时说过，原生指针也是一种迭代器，
- 此时问题就来了，原生指针并不是一种类类型，它是无法定义内嵌类型的。
- 因此，上面的内嵌类型实现还不能完全解决问题，那可不可以针对原生指针做特殊化的处理呢？
- 答案是肯定的，利用模板偏特化就可以做到了。
《泛型思维》一书对模板偏特化的定义是：
针对template参数更进一步的条件限制所设计出来的一个特化版本。
//这个泛型版本允许T为任何类型
template<typename T>
class C
{
//...
};
我们很容易接受上面的类模板有一个形式如下的偏特化版本：
template<typename T>
class C<T*>
{
//...
};
- 这个特化版本仅适用于T为原生指针的情况，
- ”T为原生指针”就是“T为任何类型”的一个更进一步的条件限制。
- 那如何利用模板偏特化解决原生指针不能内嵌类型的问题呢？
- 下面介绍的iterator_traits就是关键了。
另外说明
template <class T>
struct MyIter {
typedef T value_type; // 内嵌型别声明
// ...
};
template <class I>
typename I::value_type
func(I ite) {
return *ite;
}
// ...
MyIter<int> ite(new int(8));
cout << func(ite);
//看起来不错，但是并不是所有迭代器都是class type，原生指针就不行！如果不是class type，就无法为它定义内嵌型别。这时候就需要 偏特化 出现。
偏特化
- 偏特化就是在特化的基础上再加一点限制，但它还是特化的template。
template <class I>
struct iterator_traits {
typedef typename I::value_type value_type;
};
template <class I>
struct iterator_traits<T*> {
typedef T value_type;
};
template <class I>
typename iterator_traits<I>::value_type
func(I ite) {
return *ite;
}
- func在调用 I 的时候，
- 首先把 I 传到萃取器中，
- 然后萃取器就匹配最适合的 value_type。
- （萃取器会先匹配最特别的版本）
- 这样当你传进一个原生指针的时候，首先匹配的是带<T*>的偏特化版本，
- 这样 value_type 就是 T，而不是没有事先声明的 I::value_type。
- 这样返回值就可以使用 typename iterator_traits::value_type 来知道返回类型。
迭代器萃取机–iterator_traits
原生指针并不是一种类类型
标准库中声明如下：
template <class Category, // iterator::iterator_category
class T, // iterator::value_type
class Distance = ptrdiff_t, // iterator::difference_type
class Pointer = T*, // iterator::pointer
class Reference = T& // iterator::reference
> class iterator;
template <class Iterator> class iterator_traits;
template <class T> class iterator_traits<T*>;
template <class T> class iterator_traits<const T*>;
STL里面使用iterator_traits这个结构来专门“萃取”迭代器的特性，前面代码中提到的value_type就是迭代器的特性之一：
template<typename Iterator>
struct iterator_traits
{
typedef typename Iterator::value_type value_type;
};
如果Iterator有定义value_type，那么通过iterator_traits作用之后，得到的value_type就是Iterator::value_type，比较之前写的版本和经iterator_traits作用后的版本：
template<typename Iterator>
typename Iterator::value_type //这行是返回类型
func(Iterator iter)
{
return *iter;
}
//通过iterator_traits作用后的版本
template<typename Iterator>
typename iterator_traits<Iterator>::value_type //这行是返回类型
func(Iterator iter)
{
return *iter;
}
从长度上看，好像需要敲的代码更多了，为什么要这么麻烦加上一层间接层呢？由于原生指针也是一种迭代器，而且不是一种类类型，因此原生指针并不能定义内嵌类型。这里通过实现iterator_traits的一个偏特化版本就可以解决这个问题了，具体的实现如下：
//iterator_traits的偏特化版本，针对迭代器是个原生指针的情况
template<typename T>
struct iterator_traits<T*>
{
typedef T value_type;
};
iterator_traits中定义的类型
STL根据经验，定义了迭代器最常用到的五种类型：value_type、difference_type、pointer、reference、iterator_category，任何开发者如果想将自己开发的容器与STL结合在一起，就一定要为自己开发的容器的迭代器定义这五种类型，这样都可以通过统一接口iterator_traits萃取出相应的类型，下面列出STL中iterator_traits的完整定义：
tempalte<typename I>
struct iterator_traits
{
typedef typename I::iterator_category iterator_category;
typedef typename I::value_type value_type;
typedef typename I:difference_type difference_type;
typedef typename I::pointer pointer;
typedef typename I::reference reference;
};
下面会分别介绍一下这五种类型：
(1) value_type
- value_type就是指迭代器所指对象的类型，
- 例如，原生指针也是一种迭代器，对于原生指针int*，int即为指针所指对象的类型，也就是所谓的value_type。
(2)difference_type
difference_type用来表示两个迭代器之间的距离，例如：
int array[5] = {1, 2, 3, 4, 5};
int *ptr1 = array + 1;//指向2
int *ptr2 = array + 3;//指向4
ptrdiff_t distance = ptr2 - ptr1;//结果即为difference_type
- 上面代码中，指针ptr2与ptr1相减的结果的类型就是difference_type，
- 对于原生指针，STL以C++内建的ptrdiff_t作为原生指针的difference_type。
(3) reference_type
- reference_type是指迭代器所指对象的类型的引用，
- reference_type一般用在迭代器的*运算符重载上，
- 如果value_type是T，那么对应的reference_type就是T&；
- 如果value_type是const T，那么对应的reference_type就是const T&。
(4) pointer
- pointer就是指迭代器所指的对象，也就是相应的指针，
- 对于指针来说，最常用的功能就是operator*和operator->两个运算符。
- 因此，迭代器需要对这两个运算符进行相应的重载工作：
T& operator*() const { return *ptr; } // T& is reference type
T* operator->() const { return ptr; } // T* is pointer type
5) iterator_category
- iterator_category的作用是标识迭代器的移动特性和可以对迭代器执行的操作，
- 从iterator_category上，可将迭代器分为
- Input Iterator、
- Output Iterator、
- Forward Iterator、
- Bidirectional Iterator、
- Random Access Iterator五类，
- 具体为什么要这样分类，简单来说，就是为了尽可能地提高效率，这也是STL的宗旨之一。
iterator_traits完整定义
为了保证iterator_traits可以正常工作，STL提供了一个iterator类，所有自定义的迭代器都必须继承自它，这样才能保证这些自定义的迭代器可以顺利地狱其它STL组件进行协作，iterator类具体定义如下：
template<typename Category,
typename T,
typename Distance = ptrdiff_t,
typename Pointer = T*,
typename Reference = T&>
struct iterator
{
typedef Category iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef Pointer pointer;
typedef Reference reference;
};
类iterator不包含任何成员变量，只有类型的定义，因此不会增加额外的负担。由于后面三个类型都有默认值，在继承它的时候，只需要提供前两个参数就可以了，如：
template <typename T>
class ListIter : public std::iterator<std::forward_iterator_tag, T>
{
//...
}
例子
容器实现
template<typename T>
class ListItem
{
public:
ListItem() { m_pNext = 0;}
ListItem(T v, ListItem *p = 0) { m_value = v; m_pNext = p;}
T Value() const { return m_value;}
ListItem* Next() const { return m_pNext;}
private:
T m_value; //存储的数据
ListItem* m_pNext; //指向下一个ListItem的指针
};
template<typename T>
class List
{
public:
//从链表尾部插入元素
void Push(T value)
{
m_pTail = new ListItem<T>(value);
m_pTail = m_pTail->Next();
}
//打印链表元素
void Print(std::ostream &os = std::cout) const
{
for (ListItem<T> *ptr = m_pHead; ptr; ptr = ptr->Next())
os<<ptr->Value<<" ";
os<<endl;
}
//返回链表头部指针
ListItem<T>* Begin() const { return m_pHead;}
//返回链表尾部指针
ListItem<T>* End() const { return 0;}
//其它成员函数
private：
ListItem<T> *m_pHead; //指向链表头部的指针
ListItem<T> *m_pTail; //指向链表尾部的指针
long m_nSize; //链表长度
};
迭代器实现
template<typename T>
class ListIter
{
public:
ListIter(T *p = 0) : m_ptr(p){}
//解引用，即dereference
T& operator*() const { return *m_ptr;}
//成员访问，即member access
T* operator->() const { return m_ptr;}
//前置++操作
ListIter& operator++()
{
m_ptr = m_ptr->Next(); //暴露了ListItem的东西
return *this;
}
//后置++操作
ListIter operator++(int)
{
ListIter temp = *this;
++*this;
return temp;
}
//判断两个ListIter是否指向相同的地址
bool opeartor==(const ListIter &arg) const { return arg.m_ptr == m_ptr;}
//判断两个ListIter是否指向不同的地址
bool operator!=(const ListIter &arg) const { return arg.m_ptr != m_ptr;}
private:
T *m_ptr;
};
测试代码
int main(int argc, const char *argv[])
{
List<int> mylist;
for (int i = 0; i < 5; ++i)
{
mylist.push(i);
}
mylist.Print(); //0 1 2 3 4
//暴露了ListItem
ListIter<ListItem<int> > begin(mylist.Begin());
ListIter<ListItem<int> > end(mylist.End());
ListIter<ListItem<int> > iter;
iter = find(begin, end, 3);//从链表中查找3
if (iter != end)
cout<<"found"<<endl;
else
cout<<"not found"<<endl;
}
- 上面使用迭代器的测试代码给人的第一感觉就是好麻烦，
- 首先需要声明和定义了begin和end两个ListIter<ListItem >类型的迭代器，分别用来标识所操作容器List的头部和尾部，这时候暴露了ListItem；
- 在ListIter的实现中，为了实现operator++的功能，我们又暴露了ListItem的函数Next()。
- 另外，细心的你可能发现，算法find是通过*first != value用来判断元素是否符合要求，而上面测试代码中，first的类型为ListItem，而value的类型为int，两者之间并没有可用的operator!=函数，因此，需要另外声明一个全局的operator!=重载函数，代码如下：
template<typename T>
bool operator!=(const ListItem<T> &item, T n)
{
return item.Value() != n;
}
为了实现迭代器ListIter，我们在很多地方暴露了容器List的内部实现ListItem，这违背一开始说的迭代器模式中不暴露某个容器的内部表现形式情况下，使之能依次访问该容器中的各个元素的定义。为了解决这种问题，STL将迭代器的实现交给了容器，每种容器都会以嵌套的方式在内部定义专属的迭代器。各种迭代器的接口相同，内部实现却不相同，这也直接体现了泛型编程的概念。