STL中迭代器与traits编程的技巧

ゝ一世哀愁。 2022-06-01 01:11 156阅读 0赞

## 迭代器设计模式 ##

1、什么是迭代器？

> 一种抽象的设计概念，iterator模式定义就是提供一种方法，使之能够依序访问某个容器所有的各个元素，而又不用暴露容器内部的表达方式。

2、迭代器如何实现？

> 在内部就是通过指针实现迭代器，将编程全部泛化，抽象出共同拥有的东西，可以提供类似指针的操作，实质上就是操作符重载，实现对容器内部数据的操作功能。在STL中，如果将迭代器独立出来设计，那么就必须知道容器内部的很多细节，这种做法不好，所以迭代器的实现就交给了具体的容器设计者。

3、一个自己实现的简单List含有迭代器的版本  
从这里面可以看出，自己独立处理的迭代器，需要指定链表里面的很多细节，这种设计模式不好。  
4、一个好的迭代器里面应该定义5个型别  
为什么需要有这个5个型别呢？因为定义的容器一般是模板，我们先前不知道用户将传递什么模板参数来实例化模板，所以我们需要一种方式在实例化的类中保存用户传递进来的类型信息，最简单的处理方式就是在模板里面内嵌型别，当然STL也是通过这种方式处理。内嵌了型别之后，通过萃取器就可以萃取出这些信息，然后通用处理算法就可以根据这些信息选择最有效的方式处理，做到了容器和通用算法之间的彻底分离，这种方式真的很重要。

*  value\_type：迭代器所指对象的类型，这个通过在通用算法里面有使用。
 *  difference\_type：表示两个迭代器之间的距离，其实就是两个迭代器相减存放的数值类型也就是容器内部一个成员占用了多少字节。对应原始指针是`ptrdiff_t类型`，原始定义是`signed`则应保证足以存放同一数组中两个指针之间的差距可以为负值。
 *  pointer：定义指针类型，可以用来定义和模板参数类型的变量，在通用算法里面使用。
 *  reference：定义引用类型，可以用来定义和模板参数类型的变量，在通用算法里面使用。
 *  iterator\_category：迭代器类别，因为迭代器类别不同，可以实现的操作也不同。在算法设计里面，通过获取迭代器类别选择合适的操作，下面就是对应的型别定义，将其定义成类，那么可以在编译之前就可以根据不同类别选择不同函数，避免了在函数运行过程中通过判断选择合适的函数执行。

//5个作为标记用的型别，不需要任何成员，因为只是为了让编译器重载函数，使得我们可以接口做得统一。
    //把迭代器当做指针，因此将迭代器分为5大类，有利于设计代码
    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 {};// 支持 ++ -- p+n p-n p[n] p1-p2 p1<p2 各种操作

5个型别中前面4个是为了算法可以定义变量以及返回值使用，后面则是为了通用算法可以选择最有效率的算法方式。

6、STL规定对于任何迭代器都必须包含上述5中内嵌型别，为了防止用户出错，STL专门设计了一个类，只需要公用继承这个类即可包含5中型别。

//为避免写代码忘记，自行开发迭代器最后继承此类
    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;
    };

这是为用户定义的模板类，可以实例化对应迭代器5个型别，通过公用继承即可。

## traits编程 ##

迭代器是为了得到一种遍历容器内部的方法，而traits编程是需要获取迭代器的类型，以及迭代器所指的数据类型等等相关的信息。  
1、什么是traits？

> traits，又被叫做特性萃取技术，是模板具体化的一个应用，说得简单点就是提取“被传进的对象”的类型。当函数，类或者一些封装的通用算法中的某些部分会因为数据类型不同而导致处理或逻辑不同（而我们又不希望因为数据类型的差异而修改算法本身的封装时），traits会是一种很好的解决方案。traits可以萃取迭代器的所有特性，供通用算法使用。**为了traits用法可以得到实现，就必须就必须在类里面内嵌型别，然后可以供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;//萃取迭代器引用类别
    };

上面是一个通用萃取模板，根据`Iterator`参数实例化成对应的类。这个可以萃取出迭代器中定义的各种迭代器属性。

//原生指针偏特化版本
    template <class T>
    struct iterator_traits<T*> {
       //为原始指针特例化的模板
      typedef random_access_iterator_tag iterator_category;//原生指针必然是随机访问类型
      typedef T                          value_type;
      typedef ptrdiff_t                  difference_type;
      typedef T*                         pointer;
      typedef T&                         reference;
    };

但是当迭代器不属于类的时候就不能存放对应的迭代器属性，那么就需要特例化一个针对原始指针的萃取模板，这就是所谓的模板偏特例化。当编译器在实例化的类的时候，根据模板参数的不同，选择对应的参数选择对应的模板实例化。上面是针对原始指针的特例化版本。

//原生const指针偏特化版本
    template <class T>
    struct iterator_traits<const T*> {
       //为原始const 指针，特例化的版本
      typedef random_access_iterator_tag iterator_category;
      typedef T                          value_type;
      typedef ptrdiff_t                  difference_type;
      typedef const T*                   pointer;
      typedef const T&                   reference;
    };

这是针对`const int *`指针类型特例化的版本，如果没有这个版本，那么萃取出`value_type`将会是`const int`，定义这种变量，在算法里面并不能当做左值，所以需要特例化此版本，使得`value_type`为`int`，这样就可以满足实际需求了。

//模板函数方便获取迭代器iterator_category
    template <class Iterator>//萃取迭代器的类型
    inline typename iterator_traits<Iterator>::iterator_category
    iterator_category(const Iterator&) {
      typedef typename iterator_traits<Iterator>::iterator_category category;
      return category();//产生一个临时对象，主要返回类别
    }
    
    //模板函数方便获取迭代器difference_type
    template <class Iterator>
    inline typename iterator_traits<Iterator>::difference_type*
    distance_type(const Iterator&) {
      return static_cast<typename iterator_traits<Iterator>::difference_type*>(0);
    }
    
    //模板函数方便获取迭代器value_type
    template <class Iterator>
    inline typename iterator_traits<Iterator>::value_type*
    value_type(const Iterator&) {
      return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
    }

这是萃取出迭代器类型，并通过类型产生一个临时的对象，通过这个对象的类型就可以选择对应的模板函数。通常调用方法如下`iterator_category(i)等效于iterator_traits<Iterator>::iterator_category()`。

## 运用迭代器和萃取的函数 ##

### 1、distance函数模板 ###

//获取两个迭代器直接的距离，__distance是内部版本，通过萃取迭代器类型选择不同__distance
    template <class InputIterator>
    inline iterator_traits<InputIterator>::difference_type
    distance(InputIterator first, InputIterator last) {
       //通过重载调用不同模板
      typedef typename iterator_traits<InputIterator>::iterator_category category;
      return __distance(first, last, category());
    }
    
    template <class InputIterator, class Distance>
    inline void distance(InputIterator first, InputIterator last, Distance& n) {
      __distance(first, last, n, iterator_category(first));
    }
    
    //是input_iterator_tag型别，那么++
    template <class InputIterator>
    inline iterator_traits<InputIterator>::difference_type
    __distance(InputIterator first, InputIterator last, input_iterator_tag) {
      iterator_traits<InputIterator>::difference_type n = 0;
      while (first != last) {
        ++first; ++n;
      }
      return 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, 
                           input_iterator_tag) {
      while (first != last) { ++first; ++n; }
    }
    
    //是RandomAccessIterator型别，那么直接相减就可以，例如指针
    template <class RandomAccessIterator>
    inline iterator_traits<RandomAccessIterator>::difference_type
    __distance(RandomAccessIterator first, RandomAccessIterator last,
               random_access_iterator_tag) {
      return last - first;
    }

### 2、advance函数模板 ###

//迭代器向前移动n步，通过萃取迭代器类型选择不同__advance
    template <class InputIterator, class Distance>
    inline void advance(InputIterator& i, Distance n) {
       //通过重载调用不同模板
      __advance(i, n, iterator_category(i));
    }//iterator_category(i)产生临时对象，通过其类型，重载不同的模板函数版本
    
    
    //input_iterator_tag,直接加加必须在类里面重载，这里传递i的引用，可以修改参数i的值。
    template <class InputIterator, class Distance>
    inline void __advance(InputIterator& i, Distance n, input_iterator_tag) {
      while (n--) ++i;
    }
    
    //bidirectional_iterator_tag双向移动，那么支持--和++
    template <class BidirectionalIterator, class Distance>
    inline void __advance(BidirectionalIterator& i, Distance n, 
                          bidirectional_iterator_tag) {
      if (n >= 0)
        while (n--) ++i;
      else
        while (n++) --i;
    }
    
    //RandomAccessIterator双向移动，那么直接+=即可
    template <class RandomAccessIterator, class Distance>
    inline void __advance(RandomAccessIterator& i, Distance n, 
                          random_access_iterator_tag) {
      i += n;
    }

以上是根据迭代器型别不用，在在迭代器执行相同的操作时候，选择不同的方式，可以最大的提高效率。STL就是在底层通过这种实现效率最优的问题。

## 萃取型别特性 ##

### 1、\_\_type\_traits ###

`iterator_traits`负责萃取迭代器的特性，`__type_traits`负责萃取这个类别是否含有无用的默认构造函数、无用的拷贝构造函数、无用的赋值运算符、无用的析构函数。这种功能是为了在对这个型别进行构造、析构、拷贝、赋值等操作时候可以采取最有效的措施。例如当准备对一个元素类型未知的数组指向copy操作时，因为事先不知道是否构造函数有意义，所以不确定是否可以使用快速的memcpy或memmove。通过这个型别萃取，可以统一两种操作，在编译期间依据型别，选择不同的构造、析构、拷贝、赋值操作。很有用的哦。  
is\_POD\_type：A Plain Old Data Structure in C++ is an aggregate class that contains only PODS as members, has no user-defined destructor, no user-defined copy assignment operator, and no nonstatic members of pointer-to-member type，通俗的讲，一个类或结构体通过二进制拷贝后还能保持其数据不变，那么它就是一个POD类型。

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;
    };
    
    
    
    // Provide some specializations. This is harmless for compilers that
    // have built-in __types_traits support, and essential for compilers
    // that don't.
    
    __STL_TEMPLATE_NULL struct __type_traits<char> {
       typedef __true_type    has_trivial_default_constructor;
       typedef __true_type    has_trivial_copy_constructor;
       typedef __true_type    has_trivial_assignment_operator;
       typedef __true_type    has_trivial_destructor;
       typedef __true_type    is_POD_type;
    };
    
    __STL_TEMPLATE_NULL struct __type_traits<signed char> {
       typedef __true_type    has_trivial_default_constructor;
       typedef __true_type    has_trivial_copy_constructor;
       typedef __true_type    has_trivial_assignment_operator;
       typedef __true_type    has_trivial_destructor;
       typedef __true_type    is_POD_type;
    };
    
    __STL_TEMPLATE_NULL struct __type_traits<unsigned char> {
       typedef __true_type    has_trivial_default_constructor;
       typedef __true_type    has_trivial_copy_constructor;
       typedef __true_type    has_trivial_assignment_operator;
       typedef __true_type    has_trivial_destructor;
       typedef __true_type    is_POD_type;
    };
    
    __STL_TEMPLATE_NULL struct __type_traits<short> {
       typedef __true_type    has_trivial_default_constructor;
       typedef __true_type    has_trivial_copy_constructor;
       typedef __true_type    has_trivial_assignment_operator;
       typedef __true_type    has_trivial_destructor;
       typedef __true_type    is_POD_type;
    };
    
    __STL_TEMPLATE_NULL struct __type_traits<unsigned short> {
       typedef __true_type    has_trivial_default_constructor;
       typedef __true_type    has_trivial_copy_constructor;
       typedef __true_type    has_trivial_assignment_operator;
       typedef __true_type    has_trivial_destructor;
       typedef __true_type    is_POD_type;
    };
    
    __STL_TEMPLATE_NULL struct __type_traits<int> {
       typedef __true_type    has_trivial_default_constructor;
       typedef __true_type    has_trivial_copy_constructor;
       typedef __true_type    has_trivial_assignment_operator;
       typedef __true_type    has_trivial_destructor;
       typedef __true_type    is_POD_type;
    };
    
    __STL_TEMPLATE_NULL struct __type_traits<unsigned int> {
       typedef __true_type    has_trivial_default_constructor;
       typedef __true_type    has_trivial_copy_constructor;
       typedef __true_type    has_trivial_assignment_operator;
       typedef __true_type    has_trivial_destructor;
       typedef __true_type    is_POD_type;
    };
    
    __STL_TEMPLATE_NULL struct __type_traits<long> {
       typedef __true_type    has_trivial_default_constructor;
       typedef __true_type    has_trivial_copy_constructor;
       typedef __true_type    has_trivial_assignment_operator;
       typedef __true_type    has_trivial_destructor;
       typedef __true_type    is_POD_type;
    };
    
    __STL_TEMPLATE_NULL struct __type_traits<unsigned long> {
       typedef __true_type    has_trivial_default_constructor;
       typedef __true_type    has_trivial_copy_constructor;
       typedef __true_type    has_trivial_assignment_operator;
       typedef __true_type    has_trivial_destructor;
       typedef __true_type    is_POD_type;
    };
    
    __STL_TEMPLATE_NULL struct __type_traits<float> {
       typedef __true_type    has_trivial_default_constructor;
       typedef __true_type    has_trivial_copy_constructor;
       typedef __true_type    has_trivial_assignment_operator;
       typedef __true_type    has_trivial_destructor;
       typedef __true_type    is_POD_type;
    };
    
    __STL_TEMPLATE_NULL struct __type_traits<double> {
       typedef __true_type    has_trivial_default_constructor;
       typedef __true_type    has_trivial_copy_constructor;
       typedef __true_type    has_trivial_assignment_operator;
       typedef __true_type    has_trivial_destructor;
       typedef __true_type    is_POD_type;
    };
    
    __STL_TEMPLATE_NULL struct __type_traits<long double> {
       typedef __true_type    has_trivial_default_constructor;
       typedef __true_type    has_trivial_copy_constructor;
       typedef __true_type    has_trivial_assignment_operator;
       typedef __true_type    has_trivial_destructor;
       typedef __true_type    is_POD_type;
    };
    
    
    template <class T>
    struct __type_traits<T*> {
       typedef __true_type    has_trivial_default_constructor;
       typedef __true_type    has_trivial_copy_constructor;
       typedef __true_type    has_trivial_assignment_operator;
       typedef __true_type    has_trivial_destructor;
       typedef __true_type    is_POD_type;
    };
    
    #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    
    struct __type_traits<char*> {
       typedef __true_type    has_trivial_default_constructor;
       typedef __true_type    has_trivial_copy_constructor;
       typedef __true_type    has_trivial_assignment_operator;
       typedef __true_type    has_trivial_destructor;
       typedef __true_type    is_POD_type;
    };
    
    struct __type_traits<signed char*> {
       typedef __true_type    has_trivial_default_constructor;
       typedef __true_type    has_trivial_copy_constructor;
       typedef __true_type    has_trivial_assignment_operator;
       typedef __true_type    has_trivial_destructor;
       typedef __true_type    is_POD_type;
    };
    
    struct __type_traits<unsigned char*> {
       typedef __true_type    has_trivial_default_constructor;
       typedef __true_type    has_trivial_copy_constructor;
       typedef __true_type    has_trivial_assignment_operator;
       typedef __true_type    has_trivial_destructor;
       typedef __true_type    is_POD_type;
    };

上述就定义了不同型别，是否含有无用的默认构造函数、无用的拷贝构造函数、无用的赋值运算符、无用的析构函数，POD数据等信息，通过萃取，可以实现不同的操作。

### 2、\_\_type\_traits的使用案例 ###

1、uninitialized\_copy函数

template <class InputIterator, class ForwardIterator>
    inline ForwardIterator
      uninitialized_copy(InputIterator first, InputIterator last,
                         ForwardIterator result) {
     return __uninitialized_copy(first, last, result, value_type(result));
    }
    
    inline char* uninitialized_copy(const char* first, const char* last,
                                    char* result) {
      memmove(result, first, last - first);
     return result + (last - first);
    }
    
    inline wchar_t* uninitialized_copy(const wchar_t* first, const wchar_t* last,
                                       wchar_t* result) {
      memmove(result, first, sizeof(wchar_t) * (last - first));
     return result + (last - first);
    }

1、uninitialized\_fill函数

template <class ForwardIterator, class T>
    inline void uninitialized_fill(ForwardIterator first, ForwardIterator last, 
                                   const T& x) {
      __uninitialized_fill(first, last, x, value_type(first));
    }