[关闭]
@markheng 2018-08-04T02:59:42.000000Z 字数 4319 阅读 894

STL源码剖析笔记 - traits编程技法

C++


设计目的

STL中,算法(algorithm)和容器(container)是分离的,如何再两者之间实现合适的“粘合剂”是一个关键问题。Iterator就是这个“粘合剂”,如何在Iterator中获得container需要的类型,就要借助traits

traits编程技法

通常模板编程可以用来将不同类型的逻辑进行复用,但是有些情况下简单的类型推倒不能完成我们的需求。比如需要根据返回值的类型进行不同处理的情况。

将类型声明内嵌是个解决方法:

  1. template <class T>
  2. struct MyIter{
  3. typedef T value_type; // 内嵌型别声明
  4. T* ptr;
  5. MyIter(T* p = 0): ptr(p){}
  6. T& operator*() const {return *ptr;}
  7. //...
  8. };
  9. template <class I>
  10. typename I::value_type // 函数的返回值,typename是告诉编译器,这是一个型别
  11. func(I ite)
  12. { return *ite; }
  13. //...
  14. MyIter<int> ite(new int(8));
  15. cout << func(ite); // 输出 8

上述方法有一个缺陷,每个迭代器必须是类别(class type),但是原生指针并不是,因此无法定义内嵌型别。为了兼容原生指针作为迭代器的情况,需要用到偏特化的特性。

偏特化

下面是一个偏特化的例子,注意偏特化不能在函数中使用,需要用重载来替代偏特化,更多偏特化支持,请参考其他资料。

  1. // 接受T为任何类型
  2. template <typename T>
  3. class C {...}
  4. // 只接受T为原生指针的类型
  5. template <typename T>
  6. class C<T*>{...}

利用这种偏特化的特性,可以解决上述原生指针引出的问题。

traits

接下来是traits的核心

  1. template <class I>
  2. struct iterator_traits{
  3. typedef typename I::value_type value_type;
  4. };

上述func调用可以写为

  1. template<class I>
  2. typename iterator_traits<I>::value_type //这是返回值
  3. func (I ite)
  4. { return *ite; }

上述返回值多了一层间接地调用,这一层就可以进行特化,比如针对原生指针,我们提供如下特化版本

  1. template<class T>
  2. struct iterator_traits<T*>{
  3. typedef T value_type;
  4. };

此时,模板参数为原生指针时(比如int*),通过这个特化版本,就将value_type萃取为int。需要注意,以上的方案面对如下情况时不太合理。

  1. iterator_traits<const int*>::value_type; //萃取到 const int

萃取到const型别没什么用,因此,再添加一个特化版本,解决这个问题

  1. template <class T>
  2. struct iterator_traits<const T*>{
  3. typedef T value_type;
  4. };

这时,两种情况都可以处理。
上述traits方法扮演了“型别萃取机”的角色,可以想到,若要这个“萃取机”正常运行,每个迭代器必须定义自己的型别(value_type),这是STL的约定。

traits中的型别

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

value_type

如之前所述

different_type

该类型表示两个迭代器之间的距离,也可以用来表示容器的最大容量。例如,count函数

  1. template<class I, class T>
  2. typename iterator_traits<I>::different_type
  3. count(I first, I end, const T& value){
  4. typename iterator_traits<I>::different_type count = 0;
  5. for(; first != end; ++first)
  6. {
  7. if(*first == value) count ++;
  8. }
  9. return n;
  10. }

也需要提供原生指针的特化版本和point-to-const版本

  1. template <class I>
  2. struct iterator_traits{
  3. ...
  4. typedef typename I::different_type different_type;
  5. };
  6. template <class T>
  7. struct iterator_traits<T*>{
  8. ...
  9. typedef ptrdiff_t different_type; // ptrdiff_t是C++内建的类型
  10. };
  11. // pointer-to-const 的特化版
  12. template <class T>
  13. struct iterator_traits<const T*>{
  14. ...
  15. typedef ptrdiff_t different_type;
  16. };

pointer, reference

迭代器应该有提领和指针操作,通常如下

  1. Item& operator*() const { return *ptr; }
  2. Item* operator->() const { return ptr; }

这里Item&是Iter的reference type,而Iter*pointer type
将这两个类型放入traits内

  1. template<class I>
  2. struct iterator_traits{
  3. ...
  4. typedef I::pointer pointer;
  5. typedef I::reference reference;
  6. };
  7. // 原生指针的偏特化版本
  8. template<class T>
  9. struct iterator_traits<T*>{
  10. ...
  11. typedef T* pointer;
  12. typedef T& reference;
  13. };
  14. // pointer-to-const的偏特化版本
  15. template<class T>
  16. struct iterator_traits<const T*>{
  17. ...
  18. typedef const T* pointer;
  19. typedef const T& reference;
  20. };

iterator_category

该类型表示迭代器的类型,根据移动和施行的操作,迭代器被分为五类:

介绍这些概念是因为,依照不同类型的迭代器类型,提供运算的效率是不同的,我们需要合适的函数里用最高的效率解决问题。我们可以在运行时根据不同类型选择不同的算法进行计算,但是这样有损效率。使用函数重载的方法可以高效的解决这个问题,定义下面五个class

  1. struct input_iterator_tag {};
  2. struct output_iterator_tag {};
  3. struct forward_iterator_tag : public input_iterator_tag {};
  4. struct input_iterator_tag : public forward_iterator_tag {};
  5. struct input_iterator_tag : public bidirectional_iterator_tag {};

依照不同的迭代器类型,可以调用不同版本的函数,以advance函数为例

  1. // 2
  2. template <class InputIterator, class Distance>
  3. inline void advance(InputIterator& i, Distance n)
  4. {
  5. // 1
  6. __advance(i, n, iterator_traits<InputIterator>::iterator_category());
  7. }
  8. template <class InputIterator, class Distance>
  9. inline void __advance(InputIterator& i, Distance n, input_iterator_tag)
  10. {
  11. while (n--) ++i;
  12. }
  13. template <class ForwardIterator, class Distance>
  14. inline void __advance(ForwardIterator& i, Distance n, forward_iterator_tag)
  15. {
  16. advance(i, n, input_iterator_tag());
  17. }
  18. template <class BidirectionalIterator, class Distance>
  19. inline void __advance(BidirectionalIterator& i, Distance n, bidirectional_iterator_tag)
  20. {
  21. if(n >= 0)
  22. while(n--) ++i;
  23. else
  24. while(n++) --i;
  25. }
  26. template <class RandomAccessIterator, class Distance>
  27. inline void __advance(RandomAccessIterator& i, Distance n, random_access_iterator_tag)
  28. {
  29. i += n;
  30. }
  1. 这里iterator_traits::iterator_category()生成临时对象,用以进行重载判决
  2. 这里typename 为InputIterator是STL命名规则,以接受最低阶的类型为参数命名

总结

用编程实现traits技法不难看出,traits充分利用了偏特化的特点实现了容器和算法之间的桥梁作用,代码实现traits的功能,也让自己对模板特化属性有了进一步的理解。

参考

侯捷. STL源码剖析[M]. 华中科技大学出版社, 2002.

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注