C++ STL源码剖析之实现一个简单的iterator_category

0.导语

本节使用上节Traits特性，研究iterator源码，来实现一个简单的iterator_category，同时对iterator的源码结构进行分析。

知其然，知其所以然，源码面前了无秘密！

1.利用萃取机实现一个简单的iterator_category识别

上一节指出了迭代器的作用，依旧如下图所示：

iterator - 图1

迭代器是指向序列元素的指针的一种抽象。通过使用迭代器，我们可以访问序列中的某个元素、改变序列中的某个元素的值、使迭代器向前或向后行走等等。

迭代器有常见有五种类型: value_type, difference_type, reference_type, pointer_type都比较容易在 traits 和相应偏特化中提取。

但是，iterator_category一般也有5个，这个相应型别会引发较大规模的写代码工程。

  • 单向移动只读迭代器 Input Iterator
  • 单向移动只写迭代器 Output Iterator
  • 单向移动读写迭代器 Forward Iterator
  • 双向移动读写迭代器 Bidirectional Iterator

iterator - 图2

例如：我们实现了 advanceII, advanceBI, advanceRAI 分别代表迭代器类型是Input Iterator，Bidirectional Iterator和Random Access Iterator的对应实现。

  1. template<class Iterator>
  2. void advance(Iterator& i) {
  3.     if (is_random_access_iterator(i))
  4.         advanceRAI(i,n);
  5.     if (is_bidirectional_iterator(i))
  6.         advanceBI(i,n);
  7.     else
  8.         advanceII(i,n);
  9. }

但这样在执行时期才决定使用哪一个版本，会影响程序效率。最好能够在编译期就选择正确的版本。

而重载这个函数机制可以达成这个目标。

而对于advanceXX()都有两个函数参数，型别都未定(因为都是模板参数)。为了令其同名，形成重载函数，我们必须加上一个型别已确定的函数参数，使函数重载机制得以有效运作起来。

设计如下：如果traits有能力萃取出迭代器的种类，我们便可利用这个"迭代器类型"相应型别作为advancexx的第三个参数，而这个相应型别必须是一个class type，不能只是数值号码类的东西，因为编译器需依赖它来进行重载决议。

下面来进行实现，首先给出一个总体结构图：

iterator - 图3

定义出下面tag：

  1. struct input_iterator_tag {};
  2. struct output_iterator_tag {};
  3. struct forward_iterator_tag : public input_iterator_tag {};
  4. struct bidirectional_iterator_tag : public forward_iterator_tag {};
  5. struct random_access_iterator_tag : public bidirectional_iterator_tag {};
  6. // 继承的好处就是，当函数需要用 input_iterator_tag 的时候
  7. // 假设你传进一个forward_iterator_tag，它会沿继承向上找，知道符合条件

声明了一些列 tag 之后，我们就可以重载 advance函数，我们把这些函数用下滑线来定义，表示在内部使用，外部不可见。

  1. // 继承的好处就是，当函数需要用 input_iterator_tag 的时候
  2. // 假设你传进一个forward_iterator_tag，它会沿继承向上找，知道符合条件
  3. // input iterator
  4. template<class inputIterator, class distance>
  5. inline void __advance(inputIterator&i, distance n,
  6.                       input_iterator_tag) {
  7.     std::cout << "input tag" << std::endl;
  8. }
  9. // output iterator
  10. template<class outputIterator, class distance>
  11. inline void __advance(outputIterator&i, distance n,
  12.                       output_iterator_tag) {
  13.     std::cout << "output tag" << std::endl;
  14. }
  16. // forward iterator
  17. template<class ForwardIterator, class Distance>
  18. inline void __advance(ForwardIterator &i, Distance n,
  19.                       forward_iterator_tag) {
  20.     std::cout << "forward tag" << std::endl;
  21. }
  23. // bidrectional iterator
  24. template<class BidiectionalIterator, class Distance>
  25. inline void __advance(BidiectionalIterator &i, Distance n,
  26.                       bidiectional_iterator_tag) {
  27.     std::cout << "bidrectional tag" << std::endl;
  29. }
  31. // RandomAccess iterator
  32. template<class RandomAccessIterator, class Distance>
  33. inline void __advance(RandomAccessIterator &i, Distance n,
  34.                       random_access_iterator_tag) {
  35.     std::cout << "randomaccess tag" << std::endl;
  37. }

定义萃取机：

  1. // traits 型别
  2. template<class I>
  3. struct Iterator_traits {
  4.     typedef typename I::iterator_category iterator_category;
  5. };
  7. // 针对原生指针设计的"偏特化版"
  8. template<class I>
  9. struct Iterator_traits<I *> {
  10.     typedef random_access_iterator_tag iterator_category;
  11. };
  12. template<class I>
  13. struct Iterator_traits<const I *> {
  14.     typedef random_access_iterator_tag iterator_category;
  15. };

对外暴露接口：

  1. // 对外接口
  2. template<class InputIterator, class Distance>
  3. inline void advance(InputIterator &i, Distance n) {
  4.     // 通过Ierator_traits询问它的iterator_category是谁
  5.     typedef typename Iterator_traits<InputIterator>::iterator_category category;
  6.     __advance(i, n, category()); // 各型别的重载
  7. }

定义class type：

  1. // class type
  2. template<class Category>
  3. struct iterator {
  4.     typedef Category iterator_category;
  5. };

开始测试，我们使用上述定义的class type与原生指针来测试，分别进入萃取机的普通萃取机与偏特化萃取机，看看是否得到相应的Tag。

  1. int main() {
  2.     iterator<input_iterator_tag> input;
  3.     iterator<output_iterator_tag> output;
  4.     iterator<forward_iterator_tag> forward;
  5.     iterator<bidiectional_iterator_tag> bidect;
  6.     iterator<random_access_iterator_tag> random;
  7.     advance(input, 10);
  8.     advance(output, 10);
  9.     advance(forward, 10);
  10.     advance(bidect, 10);
  11.     advance(random, 10);
  12.     int *p=NULL;
  13.     advance(p,10);
  14.     return 0;
  15. }

输出结果：

  1. input tag
  2. output tag
  3. forward tag
  4. bidrectional tag
  5. randomaccess tag
  6. randomaccess tag

一切如我们预期一样，通过萃取机，我们获得了每个迭代器的tag，以及原生指针的tag。

我们再想得复杂一些，如果我们想知道advance的返回类型，那如何做呢？

首先修改advance返回：

  1. // 对外接口
  2. template<class InputIterator, class Distance>
  3. inline typename Iterator_traits<InputIterator>::iterator_category
  4. advance(InputIterator &i, Distance n) {
  5.     // 通过Ierator_traits询问它的iterator_category是谁
  6.     typedef typename Iterator_traits<InputIterator>::iterator_category category;
  7.     return __advance(i, n, category()); // 各型别的重载
  8. }

紧接着修改__advance返回：

  1. // input iterator
  2. template<class inputIterator, class distance>
  3. inline typename Iterator_traits<inputIterator>::iterator_category
  4. __advance(inputIterator &i, distance n,
  5.           input_iterator_tag) {
  6.     std::cout << "input tag" << std::endl;
  7.     return input_iterator_tag();
  8. }
  10. // output iterator
  11. template<class outputIterator, class distance>
  12. inline typename Iterator_traits<outputIterator>::iterator_category
  13. __advance(outputIterator &i, distance n,
  14.           output_iterator_tag) {
  15.     std::cout << "output tag" << std::endl;
  16.     return output_iterator_tag();
  17. }
  19. // forward iterator
  20. template<class ForwardIterator, class Distance>
  21. inline typename Iterator_traits<ForwardIterator>::iterator_category
  22. __advance(ForwardIterator &i, Distance n,
  23.           forward_iterator_tag) {
  24.     std::cout << "forward tag" << std::endl;
  25.     return forward_iterator_tag();
  26. }
  28. // bidrectional iterator
  29. template<class BidiectionalIterator, class Distance>
  30. inline typename Iterator_traits<BidiectionalIterator>::iterator_category
  31. __advance(BidiectionalIterator &i, Distance n,
  32.           bidiectional_iterator_tag) {
  33.     std::cout << "bidrectional tag" << std::endl;
  34.     return bidiectional_iterator_tag();
  35. }
  37. // RandomAccess iterator
  38. template<class RandomAccessIterator, class Distance>
  39. inline typename Iterator_traits<RandomAccessIterator>::iterator_category
  40. __advance(RandomAccessIterator &i, Distance n,
  41.           random_access_iterator_tag) {
  42.     std::cout << "randomaccess tag" << std::endl;
  43.     return random_access_iterator_tag();
  44. }

只需要把void修改为相应的萃取机即可。

最后测试修改，添加上返回：

  1. int main() {
  2.     iterator<input_iterator_tag> input;
  3.     iterator<output_iterator_tag> output;
  4.     iterator<forward_iterator_tag> forward;
  5.     iterator<bidiectional_iterator_tag> bidect;
  6.     iterator<random_access_iterator_tag> random;
  7.     input_iterator_tag inputIteratorTag = advance(input, 10);
  8.     output_iterator_tag outputIteratorTag = advance(output, 10);
  9.     forward_iterator_tag forwardIteratorTag = advance(forward, 10);
  10.     bidiectional_iterator_tag bidiectionalIteratorTag = advance(bidect, 10);
  11.     random_access_iterator_tag randomAccessIteratorTag = advance(random, 10);
  12.     int *p = NULL;
  13.     random_access_iterator_tag v = advance(p, 10);
  14.     return 0;
  15. }

至此，一个简单的迭代器类型在编译器判别实现完毕。

2.STL源码剖析Iterator

在bits/stl_iterator_base_types.h中也是如上述所示(实际上，上面就是STL源码的简单版，很接近)，来我们一起来看。

（1）tag

  1.  ///  Marking input iterators.
  2.   struct input_iterator_tag { };
  4.   ///  Marking output iterators.
  5.   struct output_iterator_tag { };
  7.   /// Forward iterators support a superset of input iterator operations.
  8.   struct forward_iterator_tag : public input_iterator_tag { };
  10.   /// Bidirectional iterators support a superset of forward iterator
  11.   /// operations.
  12.   struct bidirectional_iterator_tag : public forward_iterator_tag { };
  14.   /// Random-access iterators support a superset of bidirectional
  15.   /// iterator operations.
  16.   struct random_access_iterator_tag : public bidirectional_iterator_tag { };

与我上面用的一样。

（2）iterator_traits萃取机，里面包含五种，而上面只是实现其中的一种：iterator_category。所以在STL中容器与算法之间的桥梁iterator必须包含下面五种 typedef。

  1. template<typename _Iterator>
  2. struct iterator_traits
  3. {
  4.   typedef typename _Iterator::iterator_category iterator_category;
  5.   typedef typename _Iterator::value_type        value_type;
  6.   typedef typename _Iterator::difference_type   difference_type;
  7.   typedef typename _Iterator::pointer           pointer;
  8.   typedef typename _Iterator::reference         reference;
  9. };

（3）iterator

上面提到的class type为下面的简单版，对比一下，没有啥区别，就是模板参数多了一些，typedef多了。

  1. template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
  2.        typename _Pointer = _Tp*, typename _Reference = _Tp&>
  3. struct iterator
  4. {
  5.   /// One of the @link iterator_tags tag types@endlink.
  6.   typedef _Category  iterator_category;
  7.   /// The type "pointed to" by the iterator.
  8.   typedef _Tp        value_type;
  9.   /// Distance between iterators is represented as this type.
  10.   typedef _Distance  difference_type;
  11.   /// This type represents a pointer-to-value_type.
  12.   typedef _Pointer   pointer;
  13.   /// This type represents a reference-to-value_type.
  14.   typedef _Reference reference;
  15. };

至此，iterator与traits特性分析完毕。欢迎与我共同探讨STL源码奥秘，如侯捷老师所说：源码面前了无秘密。