本文共 8628 字，大约阅读时间需要 28 分钟。

在STL编程中，算法和容器时独立设计的，容器里面存放的是数据，而算法则是提供了对数据的操作，在算法操作数据的过程中，要用到迭代器，迭代器可以看作是算法和容器之间的桥梁

迭代器设计模式

在设计模式中，有一个迭代器设计模式。它一种能够顺序访问容器中每个元素的方法，使用该方法不能暴露容器内部的表达方式。而类型萃取技术就是为了解决和iterator相关的问题的。

那C++ STL实现的iterator和GOF介绍的迭代器实现方法有什么区别呢？那首先我们需要了解C++中的两个编程范式的概念：OOP（面向对象编程）和GP（泛型编程）

• OOP：将method和datas关联到一起（通俗的讲就是方法和成员变量放到一个类中实现），通过继承的方式，利用虚函数表（virtual）来实现运行时类型的判定，也叫做“动态多态”，由于运行过程中需要根据类型去检索虚函数表，因此效率较低
• GP：泛型编程，也叫做“静态多态”，多种数据类型在同一种算法或者结构上都可以操作，其效率与针对某特定数据类型而设计的算法或者结构相同，具体数据类型在编译期确定，编译器承担更多，代码执行效率高。在STL中利用GP将method和datas实现了分而治之

⽽ C++ STL 库的整个实现采⽤的就是 GP（Generic Programming） ，⽽不是 OOP（Object Oriented Programming） 。而GOF设计模式采用的就是继承关系实现的，因此，相对来讲，C++ STL的实现效率会相对较高，而且也更利用维护。

在STL编程结构里面，迭代器其实也是一种模板class，迭代器在STL中得到了广泛的应用，通过迭代器、容器和算法可以有机的绑定在一起，只要对算法给与不同的迭代器，比如vector::iterator、list::iterator，std::find()就能对不同的容器进行查找，而无需针对某个容器来设计多个版本

智能指针

STL是泛型编程的产物，是以泛型编程为指导而产生的。具体来说，STL中的迭代器将泛型算法（find、count、find_if）等应用于某个容器中，给算法提供一个访问容器元素的工具，iterator就扮演者这个重要的角色。

稍微看过 STL 迭代器源码的，就明白迭代器其实也是一种智能指针，因此，因此，它也就拥有了⼀般指针的所有特点——能够对其进⾏ * 和 -> 操作。

template
   
    class ListIterator {
   //mylist迭代器public: ListIterator(T *p = 0) : m_ptr(p){
   } //构造函数 T& operator*() const {
    return *m_ptr;} //取值，即dereference T* operator->() const {
    return m_ptr;} //成员访问，即member access //...};
   

但是在遍历容器的时候，不可避免的要对遍历的容器内部有所了解，所以，干脆把迭代器的开发工作交给容器的设计者，如此，所有实现细节反而得以封装起来不被使用者看到，这也是为什么每一种STL容器都提供有专属迭代器的缘故。好处比如：

• 不⽤担⼼内存泄漏（类似智能指针，析构函数释放内存）
• 提供统⼀接⼝

template 参数推导

参数类型推导能够帮我们解决什么问题呢？

在算法中，你可能会定义一个简单的中间变量或者设定算法的返回变量类型，这时候，你可能会遇到这样的问题，假如你需要知道迭代器所指元素的类型是什么，进而获取这个迭代器的算法的返回类型，但是问题是C++没有typeof这类判断类型的函数，也无法直接获取，那该如何是好？

注意是类型，不是迭代器的值，虽然C++提供了一个typeid()的操作符，但是这个操作符只能获得类型的名称，但是不能用来声明变量。要想获得迭代器型别，这个时候要怎么办呢？

可以通过function templete的参数类型推导。

比如：如果 I 是某个指向特定对象的指针，那么在 func 中需要指针所指向对象的型别的时候，怎么办呢？这个还⽐较容易，模板的参数推导机制可以完成任务，

template 
   
    inline void func(I iter) {
    func_imp(iter, *iter); // 传⼊ iter 和 iter 所指的值，class ⾃动推导}
   

通过模板的推导机制，就能轻⽽易举的获得指针所指向的对象的类型。

template 
   
    void func_imp(I iter, T t) {
    T tmp; // 这⾥就是迭代器所指物的类别 // ... 功能实现}int main() {
    int i; func(&i);//这⾥传⼊的是⼀个迭代器（原⽣指针也是⼀种迭代器）}
   

上⾯的做法呢，通过多层的迭代，很巧妙地导出了 T ，但是却很有局限性，⽐如，我希望 func() 返回迭代器的value type 类型返回值，** 函数的 " template 参数推导机制" 推导的只是参数，⽆法推导函数的返回值类型。万⼀需要推导函数的返回值，好像就不⾏了，那么⼜该如何是好？**

这就引出了下⾯的内嵌型别。

声明内嵌型别

上述所说的迭代器所指对象的型别，称之为迭代器的 value type 。

尽管在func_impl中我们可以把T作为参数的返回值，但是问题是用户需要调用func而不是func_impl。

如果在参数的类型推导上加上内嵌级别typedef呢？为指定的对象类型定义一个别名，然后直接获取，这样来看一下实现：

template
   
    class MyIter {
   public:	 typedef T value_type; //内嵌类型声明	 MyIter(T *p = 0) : m_ptr(p) {
   }	 T& operator*() const {
    return *m_ptr;}private:	 T *m_ptr;};//以迭代器所指对象的类型作为返回类型//注意typename是必须的，它告诉编译器这是⼀个类型template
    
     typename MyIter::value_type Func(MyIter iter) {
   	return *iter; }int main(int argc, const char *argv[]) {
   	 MyIter
     
       iter(new int(666));	 std::cout<
      
       <
       
         666}
       
      
     
    
   

上⾯的解决⽅案看着可⾏，但其实呢，实际上还是有问题，这⾥有⼀个隐晦的陷阱：实际上并不是所有的迭代器都是 class type ，原⽣指针也是⼀种迭代器，由于原⽣指针不是 class type ，所以没法为它定义内嵌型别。

因为 func 如果是⼀个泛型算法，那么它也绝对要接受⼀个原⽣指针作为迭代器，下⾯的代码编译没法通过：

int *p = new int(5);cout<
   
    <
   

要解决这个问题， Partial specialization （模板偏特化）就出场了

Partial specialization（模板偏特化）

所谓偏特化是指如果一个class template拥有一个以上的template参数，我们可以针对其中某个（或者多个，但不是全部）template参数进行特化，比如下面：

template 
   
    class C {
   ...}; //此泛化版本的 T 可以是任何类型template 
    
     class C
     
       {
   ...}; //特化版本，仅仅适⽤于 T 为“原⽣指针”的情况，是泛化版本的限制版
     
    
   

所谓特化，就是特殊情况特殊处理`，第一个类为泛化版本，T可以是任意类型，第二个类为特化版本，是第一个类的特殊情况，值针对原生指针

原生指针怎么办？特性“萃取”traits

还记得前⾯说过的参数推导机制+内嵌型别机制获取型别有什么问题吗？问题就在于原⽣指针虽然是迭代器但不是 class ，⽆法定义内嵌型别，⽽偏特化似乎可以解决这个问题。

有了上⾯的认识，我们再看看 STL 是如何应⽤的。STL定义了下面的类模板，它专门用来“萃取”迭代器的特性，而value type就是迭代器的特性之一。

traits 在 bits/stl_iterator_base_types.h 这个⽂件中：

template
   
    struct iterator_traits<_Tp*> {
    typedef ptrdiff_t difference_type; typedef typename _Tp::value_type value_type; typedef typename _Tp::pointer pointer; typedef typename _Tp::reference reference; typedef typename _Tp::iterator_category iterator_category;};
   

template
   
    struct iterator_traits {
    //类型萃取机 typedef typename Iterator::value_type value_type; //value_type 就是 Iterator 的类型型别}
   

加⼊萃取机前后的变化：

template
   
     //萃取前typename Iterator::value_type func(Iterator iter) {
   	 return *iter; }//通过 iterator_traits 作⽤后的版本template
    
      //萃取后typename iterator_traits
     
      ::value_type func(Iterator iter) {
   	 return *iter; }
     
    
   

看到这⾥也许你会问了，这个萃取前和萃取后的 typename ：iterator_traits::value_type 跟Iterator::value_type 看起来⼀样啊，为什么还要增加 iterator_traits 这⼀层封装，岂不是多此⼀举？

回想萃取之前的版本有什么缺陷：不⽀持原⽣指针。⽽通过萃取机的封装，我们可以通过类模板的特化来⽀持原⽣指针的版本！如此⼀来，⽆论是智能指针，还是原⽣指针，iterator_traits::value_type 都能起作⽤，这就解决了前⾯的问题。

//iterator_traits的偏特化版本，针对迭代器是原⽣指针的情况template
   
    struct iterator_traits
    
      {
   	 typedef T value_type;};
    
   

const 偏特化

通过偏特化添加⼀层中间转换的 traits 模板 class，能实现对原⽣指针和迭代器的⽀持，有的读者可能会继续追问：对于指向常数对象的指针⼜该怎么处理呢？⽐如下⾯的例⼦

iterator_traits
   
    ::value_type // 获得的 value_type 是 const int，⽽不是 int
   

const变量只能初始化不能赋值，这将带来下⾯的问题：

template
   
    typename iterator_traits
    
     ::value_type func(Iterator iter) {
   	 typename iterator_traits
     
      ::value_type tmp;	 tmp = *iter; // 编译 error}int val = 666 ;const int *p = &val;func(p); // 这时函数⾥对 tmp 的赋值都将是不允许的
     
    
   

那该如何是好呢？答案还是偏特化，来看实现：

template
   
    struct iterator_traits
    
      {
    //特化const指针 typedef T value_type; //得到T⽽不是const T}
    
   

traits编程技法总结

通过上⾯⼏节的介绍，我们知道，所谓的traits编程技法无非就是增加了一层中间的模板class，以解决获取迭代器中型别中的原生指针问题。利用一个中间层iterator_traits固定了func的形式，使得重复的代码大量减少，唯一要做的是稍微特化一下iterator_traits使其支持pointer和const pointer

#include 
   
    template 
    
     struct MyIter {
   	 typedef T value_type; // 内嵌型别声明	 T* ptr;	 MyIter(T* p = 0) : ptr(p) {
   }	 T& operator*() const {
    return *ptr; }};// class typetemplate 
     
      struct my_iterator_traits {
   	 typedef typename T::value_type value_type;};// 偏特化 1template 
      
       struct my_iterator_traits
       
         {
    	typedef T value_type;};// 偏特化 2template 
        
         struct my_iterator_traits
         
           { typedef T value_type;};// ⾸先询问 iterator_traits
          ::value_type,如果传递的 I 为指针,则进⼊特化版本,iterator_traits直接回答;如果传递进来的 I 为 class type,就去询问 T::value_type.template 
           
            typename my_iterator_traits
            ::value_type Func(I ite) { std::cout << "normal version" << std::endl; return *ite; }int main(int argc, const char *argv[]) { MyIter
             
               ite(new int(6)); std::cout << Func(ite)<
              
                6 int *p = new int(7); std::cout<
               
                <
                
                  7 const int k = 8; std::cout<
                 
                  <
                  
                    8}
                  
                 
                
               
              
             
           
         
        
       
      
     
    
   

上述的过程是⾸先询问 iterator_traits::value_type ，如果传递的 I 为指针,则进⼊特化版本,iterator_traits 直接回答 T ；如果传递进来的 I 为 class type ，就去询问 T::value_type 。

总结：核⼼知识点在于 模板参数推导机制+内嵌类型定义机制， 为了能处理原⽣指针这种特殊的迭代器，引⼊了偏特化机制。 traits 就像⼀台 “特性萃取机”，把迭代器放进去，就能榨取出迭代器的特性。

这种偏特化是针对可调⽤函数 func 的偏特化，想象⼀种极端情况，假如 func 有⼏百万⾏代码，那么如果不这样做的话，就会造成⾮常⼤的代码污染。同时增加了代码冗余。

迭代器的型别和种类

迭代器的型别和种类

我们再来看看迭代器的型别，常⻅迭代器相应型别有 5 种：

• value_type ：迭代器所指对象的类型，原⽣指针也是⼀种迭代器，对于原⽣指针 int*，int 即为指针所指对象的类型，也就是所谓的 value_type 。
• difference_type ： ⽤来表示两个迭代器之间的距离，对于原⽣指针，STL 以 C++ 内建的 ptrdiff_t 作为原⽣指针的 difference_type。
• reference_type ： 是指迭代器所指对象的类型的引⽤，reference_type ⼀般⽤在迭代器的 * 运算符重载上，如果 value_type 是 T，那么对应的 reference_type 就是 T&；如果 value_type 是 const T，那么对应的reference_type 就是 const T&
• pointer_type ： 就是相应的指针类型，对于指针来说，最常⽤的功能就是 operator* 和 operator-> 两个运算符。
• iterator_category ： 的作⽤是标识迭代器的移动特性和可以对迭代器执⾏的操作，从 iterator_category上，可将迭代器分为 Input Iterator、Output Iterator、Forward Iterator、Bidirectional Iterator、Random Access Iterator 五类，这样分可以尽可能地提⾼效率。

template
   
    struct iterator //迭代器的定义{
    typedef Category iterator_category; typedef T value_type; typedef Distance difference_type; typedef Pointer pointer; typedef Reference reference;};
   

iterator class 不包含任何成员变量只有类型的定义，因此不会增加额外的负担。由于后⾯三个类型都有默认值，在继承它的时候，只需要提供前两个参数就可以了。这个类主要是⽤来继承的，在实现具体的迭代器时，可以继承上⾯的类，这样⼦就不会漏掉上⾯的 5 个型别了。

对应的迭代器萃取机设计如下：

tempalte
   
    struct iterator_traits {
   //特性萃取机，萃取迭代器特性 typedef typename I::iterator_category iterator_category; typedef typename I::value_type value_type; typedef typeanme I:difference_type difference_type; typedef typename I::pointer pointer; typedef typename I::reference reference;};//需要对型别为指针和 const 指针设计特化版本看
   

迭代器的分类

最后，我们来看看，迭代器型别 iterator_category 对应的迭代器类别，这个类别会限制迭代器的操作和移动特性。

除了原生指针之外，迭代器被分为五类：

• Input Iterator ： 此迭代器不允许修改所指的对象，是只读的。⽀持 ==、!=、++、*、-> 等操作。
• Output Iterator ：允许算法在这种迭代器所形成的区间上进⾏只写操作。⽀持 ++、* 等操作
• Forward Iterator ：允许算法在这种迭代器所形成的区间上进⾏读写操作，但只能单向移动，每次只能移动⼀步。⽀持 Input Iterator 和 Output Iterator 的所有操作。
• Bidirectional Iterator ：允许算法在这种迭代器所形成的区间上进⾏读写操作，可双向移动，每次只能移动⼀步。⽀持 Forward Iterator 的所有操作，并另外⽀持 – 操作。
• Random Access Iterator ：包含指针的所有操作，可进⾏随机访问，随意移动指定的步数。⽀持前⾯四种 Iterator 的所有操作，并另外⽀持 [n] 操作符等操作。

STL六⼤组件的关系：

• container（容器） 通过 allocator（配置器） 取得数据储存空间
• algorithm（算法）通过 iterator（迭代器）存取 container（容器） 内容
• functor（仿函数） 可以协助 algorithm（算法） 完成不同的策略变化
• adapter（配接器） 可以修饰或套接 functor（仿函数）。

转载地址：https://blog.csdn.net/zhizhengguan/article/details/122650645 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！