第三章 迭代器概念与traits编程技法
《Design Patterns》
中提供有23个设计模式的完整描述。
迭代器模式定义如下，提供一种方法，使之能够依序巡防某个聚合物(容器)所含的各个元素，而又无需暴露该聚合物的内部表述方式。
迭代器是一种Smart Pointer，迭代器是一种行为类似指针的对象，而指针的各种行为中最重要也是最常见的就是dereference和member access。
因此，迭代器最重要的工作就是对operator*和operator->进行重载。
auto_ptr的源码在<memory>中。
explicit修饰构造，只能显示调用。
我们需要为每个容器设计一个行为类似指针的外衣，也就是迭代器。满足以下功能:当我们dereference这一迭代器时，传回结点对象；当我们递增该迭代器时，应该指向下一个结点对象。为了满足任何形态的结点，该迭代器应该被设计成一个class template。
为了实现一个针对某容器的迭代器，我们暴露了太多的实现细节:
1.为了制作begin和end迭代器，暴露了结点;2.在迭代器中为了达成operator++，暴露了next()函数。
因此，把迭代器的设计工作交给容器设计者，这样就可以封装所有的实现细节。
迭代器相应类型
得到迭代器所指对象的类型，也就是该迭代器的value_type。
1.参数推导(个人理解，通过构建对应value_type类型的传入参数，在模板中使用value_type)
缺点，value_type用作返回值的时候，此方法无法做到。
2.声明内嵌类型，设计偏特化版本以适应原生指针的情况。
template <class I>
struct iterator_traits{ //特性萃取机
typedef typename I::value_type value_type;
}
可以有原生指针的偏特化版，和const指针的偏特化版。
traits可以萃取各个迭代器的特性，也就是迭代器的相应类型。
当然这个特性萃取机要想有效运作，每个迭代器必须遵守约定，自行以定义内嵌类型定义的方式定义出相应的类型。
常用的迭代器相应类型:value type,difference type,pointer,reference,iterator catagory。
iterator_traits必须为传入类型为指针和常量指针的情况，设计特化版本。
template <class T, class Alloc = alloc>
class list {
public:
typedef T value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef list_node* link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
//...
｝
1.
value type
所谓
value type，是指迭代器所指对象的类型。任何一个打算与STL算法有完美搭配的class，都应该定义自己的
value type内嵌类型。
2.
difference type
difference type用来表示两个迭代器之间的距离，因此它也可以用来表示一个空间容器的最大容量。因为对于连续空间的容器而言，头尾之间的距离就是其最大容量。
如STL的count()(在文件<stl_algo.h>中)，为什么计数器必须要用这个
difference type来表示？
针对相应类型
difference type，traits有两个针对原生指针而写的偏特化版。
如果是原生指针，则直接typedef ptrdiff_t difference_type;否则需要typedef typename I::
difference_type
difference_type。
3.
reference type NodeItem& 引用类型与左值？
从“迭代器所指之物的内容是否允许改变”的角度，迭代器分为两种:
不允许改变所指对象内容者，constant iterators;
允许改变所指对象内容者，mutable iterators
。
当我们对一个mutable
iterators进行dereference操作时，返回的应该是个左值，因此应该以by reference的方式进行。
当p是个mutable iterators，如果value type是T，*p应该是T&。
当p是个constant iterators，如果value type是T，*p应该是const T&。
针对相应类型
difference type，traits同样有两个针对原生指针而写的偏特化版。
4.pointer type
NodeItem*
我们可以传回一个pointer,指向迭代器所指之物。
针对相应类型
difference type，traits同样有两个针对原生指针而写的偏特化版。
5.
iterator_catagory
根据移动特性和施行操作，迭代器被分为五类:
1.Input Iterator read only
2.Output Iterator write only
3.Forward Iterator 允许写入型算法在此种迭代器所形成的区间上进行读写操作。
4.Bidirectional Iterator 可双向移动。某些算法需要逆向走访迭代器区间。
以上四种迭代器都只公寓一部分指针算术能力，前三种支持operator++,第四种再加上operator--。
5.Random Access Iterator 涵盖所有指针算术能力，包括p+n,p-n,p[n],p1-p2,p1<p2。
概念与强化，是架构STL的重要观念(Austern98)。
以上五种迭代器的分类和从属关系；
Input Iterator
Output Iterator
Forward Iterator
Bidirectional Iterator
Random Access Iterator
我们应该针对每一种寄存器，实现特定的算法，来达到最大的效率。
1.判断迭代器的类型，然后调用不同的算法实现函数。
但是这样在执行期间才确定使用哪个版本的算法函数，影响效率。
2.使用函数重载机制。
为五种类型的迭代器声明有从属关系的标记类型:
struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag::public input_iterator_tag{};
struct biddirectional_iterator_tag::public
forward_iterator_tag
{};
struct random_access_iterator_tag::
public
biddirectional_iterator_tag::
{};
然后为各个版本的算法实现函数，添加额外一个参数，来激活重载机制。
在各个版本的
算法实现函数之上，应该开放一个对外的控制接口，在此接口函数中，需要根据traits推导出迭代器类型。
iterator_traits<InputIterator>::iterator_category();
为此tratis中必须定义相应的类型:typedef typename I::iterator_category
iterator_category;
同样的，
针对相应类型
difference type，traits需要有两个针对原生指针而写的偏特化版。
注:1.任何一个迭代器，其类型永远应该落在“该迭代器所隶属的各种类型中，最强化的那个”。
2.STL命名规则，以算法所能接收的最低阶迭代器类型，来为其迭代器类型参数
命名。
消除单纯传递调用的函数，当参数未能完全吻合时，类的继承机制会自动传递调用，到其(迭代器类型)父类的相应匹配。
为了符合规范，任何迭代器都应该提供五个内嵌相应类型，以便traits萃取。
STL提供了一个iterator类，如果每个迭代器都继承自它，就可以符合STL所需规范。
template <class Category, class T, class Distance = ptrdiff_t,
class Pointer = T*, class Reference = T&>
struct iterator {
typedef Category iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef Pointer pointer;
typedef Reference reference;
};//<stl_iterator.h>
traits编程技法 利用内嵌类型的编程技巧与编译器的template参数推导功能，
增强C++未能提供的关于类型认证方面的能力，弥补C++不为强类型语言的遗憾。
__type_traits
//以下代码在<type_traits.h>
struct __true_type {};
struct __false_type {};
template <class type>
struct __type_traits {
typedef __true_type this_dummy_member_must_be_first;
typedef __false_type has_trivial_default_constructor;
typedef __false_type has_trivial_copy_constructor;
typedef __false_type has_trivial_assignment_operator;
typedef __false_type has_trivial_destructor;
typedef __false_type is_POD_type;
};
然后
<type_traits.h>还为所有C++的标量类型提供了
__type_traits的特化版本。
用法:首先用value_type()萃取出迭代器的value type，然后再利用
__type_traits判断该类型是否具备某种属性比如
is_POD_type。
从而可以对应不同的重载函数。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
