14000+字详解SGI-STL迭代器，走进traits编程技法
迭代器设计理念 - STL关键所在
STL的中心思想在于，将容器(container)和算法(algorithm)分开，彼此独立设计，最后再用粘合剂粘合到一起，而这个
粘合剂就是iterator(迭代器)
下面从stl_algo.h截取一下容器、算法、迭代器合作的展示，以find()为例，它接受两个迭代器和一个目标
template <class _InputIter, class _Tp>
inline _InputIter find(_InputIter __first, _InputIter __last,
const _Tp &__val,
input_iterator_tag)
{
while (__first != __last && !(*__first == __val))
++__first;
return __first;
}
// 结合容器使用
int ia[7] = {0, 1, 2, 3, 4, 5, 6};
vector<int> v(ia, ia + 7);
list<int> l(ia, ia + 7);
deque<int> dq(ia, ia + 7);
vector<int>::iterator it1 = find(v.begin(), v.end(), 4);
list<int>::iterator it2 = find(l.begin(), l.end(), 4);
deque<int>::iterator it3 = find(dq.begin(), dq.end(), 4);
从上面的例子可以看出来，不同类型的容器，可以通过迭代器使用相同的算法进行处理，这就是迭代器设计精妙所在
迭代器是一种smart-pointer
迭代器是一种行为类似于指针的对象，而原生指针的主要工作就是内容提领(解引用)和成员访问，所以迭代器的首要目标
是重载operator*() 和 operator->()，关于这一点，C++标准库中auto_ptr(不过已经废弃，被unique_ptr代替)
可以提供参考，下面为auto_ptr实现源码
template <class _Tp>
class auto_ptr
{
private:
_Tp *_M_ptr;
public:
typedef _Tp element_type;
// explicit: 禁止隐式类型转换，即禁止auto_ptr<int> p = new int(10)这种语法
// 因为上述语句会转化为auto_ptr<int> p = auto_ptr<int>(new int(10));
// 为什么禁止隐式类型转换？因为会导致所有权转移
// auto_ptr<int> p1(new int(10));
// auto_ptr<int> p2 = p1;
// 执行后对象所有者就会从p1转为p2
// 如果支持隐式类型转换，在下面这段代码执行结束后，对象就会从p转移到函数参数中
// void func(auto_ptr<int> p);
// auto_ptr<int> p(new int(10));
// func(p); // p 被偷偷 transfer ownership
explicit auto_ptr(_Tp *__p = 0) __STL_NOTHROW : _M_ptr(__p) {}
auto_ptr(auto_ptr &__a) __STL_NOTHROW : _M_ptr(__a.release()) {}
auto_ptr &operator=(auto_ptr &__a) __STL_NOTHROW
{
if (&__a != this)
{
delete _M_ptr;
_M_ptr = __a.release();
}
return *this;
}
~auto_ptr() { delete _M_ptr; }
_Tp &operator*() const __STL_NOTHROW // 主要重载了* 和->这两个运算符
{
return *_M_ptr;
}
_Tp *operator->() const __STL_NOTHROW
{
return _M_ptr;
}
_Tp *get() const __STL_NOTHROW
{
return _M_ptr;
}
_Tp *release() __STL_NOTHROW
{
_Tp *__tmp = _M_ptr;
_M_ptr = 0;
return __tmp;
}
void reset(_Tp *__p = 0) __STL_NOTHROW
{
if (__p != _M_ptr)
{
delete _M_ptr;
_M_ptr = __p;
}
}
};
迭代器的内置型别
在算法中运用迭代器的时候，很可能会用到相应型别，那什么是相应型别？迭代器所指之物就是其一。假如算法中有必要
声明一个变量，以"迭代器所指对象的型别"为型别，怎么办呢？C++只有sizeof()并没有typeof()。这里给出一个解决方
法->使用function template的参数推导机制，在模版实例化的时候，我们就可以知道它是什么类型了
template<class I, class T>
void func_impl(I iter, T t)
{
T tmp = t; // 在这里解决问题，T就是我们想知道的迭代器所指之物的类型
// ... 这里做func原本要做的事
}
template<class I>
void func(I iter)
{
func_impl(iter, *iter);
}
int main()
{
int i = 0;
func(&i);
}
上面这段demo可以很好的展现出怎么通过模版的参数推导完成类型判断的，但是问题来了，所有的迭代器的内置型别都可以
用上述模版参数推导来取得吗？答案是不可以的，所以我们需要更全面的解法
在这里，为了防止读者不理解“迭代器的内置型别”究竟是何物，我将列出常见的五种迭代器的内置型别
- value_type (上文所说迭代器所指之物)
- differnce_type (两个迭代器之间的距离)
- pointer (指针 *)
- reference (引用 ->)
- iterator catagoly(迭代器类型)
至于他们具体是什么，请继续往下看
Traits编程技法 - STL源代码之钥
迭代器所指对象型别，称为value_type，上述通过模版参数推导机制获得value_type的方法并不能全面覆盖，如果
value_type必须用为函数的传回值，就无法使用了，因为模版类型推导只能作用于参数，无法推导返回值类别
那我们怎么办呢? STL的大佬想出一种方式 -> 在iterator的定义内部，内嵌型别声明(nested type)
在这里截出一段input_iterator(在这里可以先把它看作普通的iterator，后面会细说)的源码可以观察到，
SGI-STL的实现确实就是这样的
template <class _Tp, class _Distance>
struct input_iterator
{
typedef input_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Tp * pointer;
typedef _Tp & reference;
};
// 搭配源码我自己补充一段，体现类型的获取过程
template<class I>
typename I::value_type value_type // 这里一行都是返回值类型
func(I it)
{
return *it;
}
注意，在使用I::value_type的时候必须要加上typename的声明，因为编译器不知道input_iterator<_Tp>在实例
化前到底是什么，typename的作用是告诉编译器这是一个类型
看起来这个方式确实不错，但是这里面有一个隐晦的陷阱，即只有class type才有内嵌类别，但并不是所有的迭代器都是
class type，原生指针就不是！！！(int*, double*, char* 等)，但是迭代器必须要接受原生指针，这时，我们可以
想到一种方式template partial specializtion(模版的偏特化)
partial specializtion(偏特化)的意义
在讲解这小节之前，我们先来看C++提供的对模版的两种特化方式
// 普通泛化版本(template)
template<class T>
struct Printer
{
void print()
{
std::cout << "generic type" << std::endl;
}
};
// 1. 全特化: 使用者想在使用某种类型的时候，使用特别的Print函数
template<>
struct Printer<int> // 特化类型为int
{
void print()
{
std::cout << "int type" << std::endl;
}
};
// 当其他类型调用这个函数的时候，会打印generic type，而int类型则会输出int type
// 2. 偏特化: 当使用者想在使用某一大类的时候(如*, const *类型)
template<class T>
struct iterator_traits<T*>
{
typedef T value_type;
};
// 这时候就是对指针类型的一种偏特化
在了解上述特化机制后，我们就可以明白为什么STL要使用偏特化的方法来解决原生指针没有class的难题
现在我们就可以对迭代器参数为指针者设计特化版的迭代器
注意，下面这种class template转门用来"萃取"迭代器类型的特性
template<class I>
struct iterator_traits{ // traits意为特质
typedef typename I::value_type value_type;
}
所谓的traits，就是当迭代器I有自己的value_type类型的时候就会通过上面这个iterator_traits萃取出来
有了这个，上面的func函数就可以被改写
// 原func函数
// template<class I>
// typename I::value_type value_type // 这里一行都是返回值类型
// func(I it)
// {
// return *it;
// }
template <class I>
typename iterator_traits<I>::value_type
func(I it)
{
return *it;
}
这时有人会问，多包一层的意义在哪？这时偏特化就该登场了!!!
template<class T>
struct iterator_traits<T*>{
typedef T value_type;
}
经过这一层偏特化，原生指针int* 虽然没有class type，但是也可以通过iterator_traits萃取出value_type
但是如果传入的是const int* 呢？得到的是const int，我们只是想知道运算的类型是什么，所以得到const int
并没有什么用，那就再将const T*偏特化一下！！！
template<class T>
struct iterator_traits<const T*>{
typedef T value_type;
}
这时不管我们传入的是const int* 还是int*，我们都可以获得对应的value_type.
五种迭代器相应型别
除了value_type之外，我们在上面说了，迭代器的相应型别还有differnce_type, pointer, reference,
iterator_category，这里贴出文件stl_iterator_base中iterator_traits的实现及其特化版本
template <class _Iterator>
struct iterator_traits {
typedef typename _Iterator::iterator_category iterator_category;
typedef typename _Iterator::value_type value_type;
typedef typename _Iterator::difference_type difference_type;
typedef typename _Iterator::pointer pointer;
typedef typename _Iterator::reference reference;
};
// pointer特化
template <class _Tp>
struct iterator_traits<_Tp*> {
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};
// pointer to const特化
template <class _Tp>
struct iterator_traits<const _Tp*> {
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef const _Tp* pointer;
typedef const _Tp& reference;
};
-
value_type
上面大量说的"迭代器所指之物"的类型，就是value_type -
difference_type
用来代表两个迭代器的距离，如果一个STL的泛型算法想提供计数功能，如count()，它的返回值应该是difference_typestl_algo文件中count()实现如下
template <class _InputIter, class _Tp>
typename iterator_traits<_InputIter>::difference_type
count(_InputIter __first, _InputIter __last, const _Tp &__value)
{
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_REQUIRES(typename iterator_traits<_InputIter>::value_type,
_EqualityComparable);
__STL_REQUIRES(_Tp, _EqualityComparable);
typename iterator_traits<_InputIter>::difference_type __n = 0;
for (; __first != __last; ++__first)
if (*__first == __value)
++__n;
return __n;
}
- reference type
要理解这个reference type，我们要先知道C++中的左值和右值分别代表什么，
C++中的左值/右值本质要解决：对象的生命周期 + 是否可以被修改 + 是否可以被绑定引用
左值: 生命周期稳定，可以被修改，可以被绑定引用
右值: 生命周期短(表达式结束后就销毁)，不可以被修改，不可以绑定引用
举例子来看
int a = 10;
// 在上述表达式中，a就是左值(有名字，有地址，可以修改)，而10就是右值，不可以修改，表达式结束后销毁
// &a是合法的，而&10则不可以
int a = 10;
int& r = a;
// 上面就是左值引用，a是一个左值，而int& r = 10则是不被允许的，因为10是一个右值，表达是结束后会被释放
const int& r = 10;
// 但是这个是被允许的，因为编译器会根据10来生成一个临时变量
// 即const int temp = 10; const int& r = temp;
总结一下:
左值可以看作一个对象，右值则代表一个值
T& 只允许绑定左值，const T& 允许绑定左值和右值
有了以上知识，我们可以得知: 在C++ 中，函数如果要传回左值，都是以 by reference 的方式进行，所以当P是个 mutable iterators 时，如果其 value type 是T，那么*p的型别不应该是T，应该是T&。将此道理扩充，如果p是一个 constant iterators，其 value type 是T，那么 *p 的型别不应该是 const T，而应该是 const T&。
// 假如我们有这个迭代器了，我们想得到它的值，我们就会这样使用*p
vector<int>::iterator p;
*p;
// 但是*p是什么类型呢？int？int&？举个例子
vector<int> v = {1,2,3};
vector<int>::iterator p = v.begin();
*p = 10;
// 这是正确的语法，如果*p的类型是int的话，根据我们上面左右值的讲解会得到下面的结论
// 1 = 10，这是在给临时对象赋值，是不被允许的，所以很显然*p返回值是int& 即必须是一个左值也就是T&(reference type)
- pointer type
与reference type相似，reference type代表的是*p的返回值类型，而pointer type代表的是p->的返回类型
vector<int>::iterator it = v.begin();
*it // 解引用
it->xxx // 成员访问
// it->member实际上会被编译器解释为(*it).member
- iterator category
根据移动特性和实施操作，iterator被分为五类
- input iterator 仅读
- output iterator 仅写
- forward iterator 可读写，但是只能单向移动
- bidirection iterator 可以双向移动
- random access iterator 涵盖上面所有能力，并加上p + n, p - n, p1 - p2, p1 + p2的能力
可能会有读者疑问，为什么要有这些类型的迭代器，都设置成相同不好吗？大错特错，迭代器设计的时候需要考虑的是设计适当的相应型别，而迭代器怎么设计是根据不同容器来的(我很喜欢)
不同容器为了实现一些特性肯定要使用不同特点的迭代器，那么设计不同的迭代器类型又有什么用呢？这样设计的原因是在设计算法的时候，我们会尽量根据不同迭代器类型明确一个定义(类似特化)
举个例子，如果一个算法可以接受input iterator那么这个算法肯定也可以接收random access iterator，但是可用并不代表最佳！！！
以advanced()为例
advance()有两个参数，一个是迭代器p，另一个是n，它的的作用是将迭代器p向后移动n次(也有可能是后退)，下面有三份定义，分别针对input iterator、bidirection iterator、
random access iterator(至于为什么不设计forward iterator则是因为它的实现与input iterator相同，这里记住，后面要考)
// input iterator
template <class InputIterator, class Distance>
void advance_II(InputIterator it, Distance n)
{
while(n--)
++it; // 注意这里前置++效率比后置要高
}
// bidirection iterator
template <class BidirectionIterator, class Distance>
void advance_BI(BidirectionIterator it, Distance n)
{
if(n >= 0)
while(n--) ++it;
else
while(n++) --it;
}
// random access iterator
template <class RandomAccessIterator, class Distance>
void advance_RAI(RandomAccessIterator it, Distance n)
{
it += n
}
现在，当程序调用advance的时候，我们应该选择哪份函数呢？如果选择advance_II()的话，那么RandomAccessIterator的时间复杂度将会从O(1)退化到O(N)
如果选择advance_RAI()呢？那么InputIterator则无法使用这个函数，我们需要将它们三合一，有人肯定想到用if - else判断iterator类型，再分别判断
但是那样会损失效率，最好要在编译阶段我们就知道要选择哪个函数。
这时我们应该想到一个C++重要特性，函数重载!!!，上述函数前两个参数都是不确定的，所以我们需要一个确定的第三个参数来构成函数重载
这也是迭代器设计五种迭代器类型的原因，通过之前说过的traits机制，我们可以很轻松的萃取出迭代器的类型，下面给出源码中迭代器类型标记
struct input_iterator_tag {};
struct output_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没有任何成员，只用作标记，这里直接贴出advance的源码实现了。
// 因为__advance只在内部使用所以给它加上前导符
// input iterator实现
template <class _InputIter, class _Distance>
inline void __advance(_InputIter &__i, _Distance __n, input_iterator_tag)
{
while (__n--)
++__i;
}
// bidirection iterator实现
template <class _BidirectionalIterator, class _Distance>
inline void __advance(_BidirectionalIterator &__i, _Distance __n,
bidirectional_iterator_tag)
{
__STL_REQUIRES(_BidirectionalIterator, _BidirectionalIterator);
if (__n >= 0)
while (__n--)
++__i;
else
while (__n++)
--__i;
}
// random access iterator实现
template <class _RandomAccessIterator, class _Distance>
inline void __advance(_RandomAccessIterator &__i, _Distance __n,
random_access_iterator_tag)
{
__STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);
__i += __n;
}
template <class _InputIterator, class _Distance>
inline void advance(_InputIterator &__i, _Distance __n)
{
__STL_REQUIRES(_InputIterator, _InputIterator);
__advance(__i, __n, iterator_category(__i));
}
细心的读者可能已经发现了，上面的__advance()实现中，没有重载forward iterator类型的，难道是源码作者忘掉了？
而实际上，在之前就已经说过，input iterator与forward iterator的实现是相同的，这里我自己杜撰一下如果有
forward iterator重载版本的__advance()将会是什么样子的
template <class _ForwardIter, class _Distance>
inline void __advance(_ForwardIter &__i, _Distance __n, forward_iterator_tag)
{
__advanc(__i, __n, input_iterator_tag);
}
我们发现这只是一种单纯的传递调用函数，这样会有损性能，违背了STL的初心，这时之前所说的继承，就是在这里起的作用
struct input_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
// 为了更好的实验效果，我们将 input_iterator_tag 比喻为B，forward_iterator_tag比喻为D1，bidirectional_iterator_tag比喻为D2
struct B { };
struct D1 : public B { };
struct D2 : public D1 { };
template <class T
void func(I& p, B)
{
cout << "B version" << endl;
}
template <class T
void func(I& p, D2)
{
cout << "D2 version" << endl;
}
int main()
{
int* p;
func(p, B()); // 这里的B，D1，D2都是临时对象，仅为了观察实验效果
func(p, D1());
func(p, D2());
}
// 经实验，func(p, B()); 与参数完全匹配，输出B version，
// func(p, D1()); 与参数未能完全吻合，但是因为继承关系会自动传递调用，输出B version，
// func(p, D2()); 与参数完全吻合，输出D2 version
将上述实验代码复制运行后，我们会神奇的发现D1()的重载函数不存在的时候会自动传递调用父类的对应函数
这也是__advance没有forward iterator版本的原因
回归到advance函数，上层调用的时候，肯定只能传两个参数，那么第三个参数怎么办？很显然，交给traits即可！！！
为了方便获取迭代器内置类型，SGI还特意将iterator_traits封装成几个函数，可以通过调用直接返回类型
template <class _Tp, class _Distance>
inline input_iterator_tag
iterator_category(const input_iterator<_Tp, _Distance> &)
{
return input_iterator_tag();
}
inline output_iterator_tag iterator_category(const output_iterator &)
{
return output_iterator_tag();
}
template <class _Tp, class _Distance>
inline forward_iterator_tag
iterator_category(const forward_iterator<_Tp, _Distance> &)
{
return forward_iterator_tag();
}
template <class _Tp, class _Distance>
inline bidirectional_iterator_tag
iterator_category(const bidirectional_iterator<_Tp, _Distance> &)
{
return bidirectional_iterator_tag();
}
template <class _Tp, class _Distance>
inline random_access_iterator_tag
iterator_category(const random_access_iterator<_Tp, _Distance> &)
{
return random_access_iterator_tag();
}
template <class _Tp>
inline random_access_iterator_tag iterator_category(const _Tp *)
{
return random_access_iterator_tag();
}
template <class _Tp, class _Distance>
inline _Tp *value_type(const input_iterator<_Tp, _Distance> &)
{
return (_Tp *)(0);
}
template <class _Tp, class _Distance>
inline _Tp *value_type(const forward_iterator<_Tp, _Distance> &)
{
return (_Tp *)(0);
}
template <class _Tp, class _Distance>
inline _Tp *value_type(const bidirectional_iterator<_Tp, _Distance> &)
{
return (_Tp *)(0);
}
template <class _Tp, class _Distance>
inline _Tp *value_type(const random_access_iterator<_Tp, _Distance> &)
{
return (_Tp *)(0);
}
template <class _Tp>
inline _Tp *value_type(const _Tp *) { return (_Tp *)(0); }
template <class _Tp, class _Distance>
inline _Distance *distance_type(const input_iterator<_Tp, _Distance> &)
{
return (_Distance *)(0);
}
template <class _Tp, class _Distance>
inline _Distance *distance_type(const forward_iterator<_Tp, _Distance> &)
{
return (_Distance *)(0);
}
template <class _Tp, class _Distance>
inline _Distance *
distance_type(const bidirectional_iterator<_Tp, _Distance> &)
{
return (_Distance *)(0);
}
template <class _Tp, class _Distance>
inline _Distance *
distance_type(const random_access_iterator<_Tp, _Distance> &)
{
return (_Distance *)(0);
}
template <class _Tp>
inline ptrdiff_t *distance_type(const _Tp *) { return (ptrdiff_t *)(0); }
上述函数经过封装后可以通过简单的iterator_category()，value_type()，distance_type()调用
在advance()就有体现这点
除此之外，我们发现advance的template中写的是InoutIter，其实这是STL的规定，以算法能接受的
最低阶的迭代器类型，来为其迭代器类型参数命名
以distance()为例
与advance()相似，distance()也是一个使用频率极高的算法，用来计算两个迭代器的距离，设计模式与advance()类似
这里贴出源码，剩余不过多赘述
template <class _InputIterator, class _Distance>
inline void __distance(_InputIterator __first, _InputIterator __last,
_Distance &__n, input_iterator_tag)
{
while (__first != __last)
{
++__first;
++__n;
}
}
template <class _RandomAccessIterator, class _Distance>
inline void __distance(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Distance &__n, random_access_iterator_tag)
{
__STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);
__n += __last - __first;
}
template <class _InputIterator, class _Distance>
inline void distance(_InputIterator __first,
_InputIterator __last, _Distance &__n)
{
__STL_REQUIRES(_InputIterator, _InputIterator);
__distance(__first, __last, __n, iterator_category(__first));
}
std::iterator的保证
为了保证规范，任何iterator都应该有五种内嵌类型，以便于traits进行萃取，为了防止遗漏
STL提供了iterators class，如果新设计的迭代器都继承于它，则保证符合规范
template <class _Category, class _Tp, class _Distance = ptrdiff_t,
class _Pointer = _Tp*, class _Reference = _Tp&>
struct iterator {
typedef _Category iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Pointer pointer;
typedef _Reference reference;
};
如果我们自己要设计迭代器，一般只需要填前两个参数即可(后三个给缺省了)
总结
设计适当的相应型别（associated types），是迭代器的责任。设计适当的选代器，则是容器的责任。
唯容器本身，才知道该设计出怎样的迭代器来遍历自己，并执行迭代器该有的各种行为（前进、后退、取值、取用成员）
至于算法，完全可以独立于容器和迭代器之外自行发展，只要设计时以迭代器对外接口就行。
traits编程技法大量运用于STL实现品中。它利用“内嵌型别”的编程技巧与编译器的 template 参数推导功能，
增强C++未能提供的关于型别认证方面的能力，弥补C++ 不为强型别（strong typea）语言的遗憾。
了解 traits 编程技法，就像获得“芝麻开门”的口诀一样，从此得以一窥STL源代码堂奥。
— 节选自侯捷《STL源码剖析》
事实上，SGI STL不止在迭代器中使用了traits，它更是单独抽出了一个__type_traits，它可以负责萃取别的类型
如果读者以后有时间，可以单独再看一下type_traits.h这个文件中的__type_traits，相信你肯定会有更多收获
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
1
0- 0
已为社区贡献1条内容
所有评论(0)