咳咳,今天来说一下迭代器这个东西à iterator。
说实话,当初学stl的时候,就觉得这东西很神奇,很强大,但是又没有深入了解过这个东西,只是觉得这东西像个指针一样,但是又比指针好用。这次看完这这一章之后,对这个东西的理解又深刻了一点。
首先,iterator这个东西是为了将stl当中的容器与算法连接起来而出现的产物,具体开发工作由容器设计者来完成,大概如下:
这样做有两个好处:
1. 将容器的开发工作和算法的开发工作完全分离开来
2. 避免对外界暴露更多容器的实现细节
但是,这样做的话会有一个问题,当算法模板当中需要用到迭代器所指的对象的类型时,心里唱起了凉凉,哎,咋就这么惨呢?聪明的stl设计者们就设计了如下的思路来“萃取”出迭代器所指对象的类型和其他的一些特性,如下图和代码:
-
template <class Iterator>
-
struct iterator_traits{
-
typedef typename Iterator::value_type value_type;
-
typedef typename Iterator::iterator_category iterator_category;
-
typedef typename Iterator::difference_type difference_type;
-
typedef typename Iterator::pointer pointer;
-
typedef typename Iterator::reference reference;
-
…
-
};
这里要说明一下iterator_category, 其设计原由就是:stl设计者为了程序执行效率考虑,为每一种容器都设计了不同的迭代器,例如:只允许++操作的forward_iterator,允许++和 --操作的bidirectional_iterator,允许++、--、和+n,-n操作的random_access_iterator。
有了迭代器所指的对象的类型,以及其自身得性质,就轮到stl中算法大显身手了,由于函数模板是可以自行推导出参数类型,进而进行函数调用的,所以,我们只需要在stl函数模板中实现函数重载就ok了,这里就要用到上面说的iterator_category了,具体代码如下:
-
//先声明一堆空的结构体来确定各个iterator的category:
-
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 {};
-
//之后就是对各个函数的模板进行重载了:
-
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) {
-
n += last - first;
-
}
-
//甩给外界的接口就是:
-
template <class InputIterator, class Distance>
-
inline void distance(InputIterator first, InputIterator last, Distance& n) {
-
__distance(first, last, n, iterator_category(first));
-
}
当外界调用distance函数的时候,首先会根据输入的iterator类型,选区不同的category,进而调用不同的内嵌函数模板,这样就完成了之前所说的~~
阅读(1876) | 评论(0) | 转发(0) |