迭代器与相应类型推导

在写作泛型函数或代码时，我们可能存在这样的需要：与参数相关的其它类型，比如一个迭代器的值的类型，在算法中运用迭代器时，很可能会用到其也叫相应类型(associate type)。

什么是相应类型?
迭代器所指之物的类型就是其中一个。如果我们的算法中有必要声明一个变量，以”迭代器所指对象的类别”为型号。

本文要向大家展示一个函数模板推导机制使用技法，这个在STL的迭代器和许多排序算法中广泛使用。

考虑一个情况，我们在写一个泛型函数，它接受一对迭代器，要做的事就是对这一对迭代器之间的元素进行排序，其中将出现这幕：我需要对两个值进行交换。不知道大家有没有写过这样的代码，现在的问题是如何实现这两个值的交换？

如：

if(*itr > *(itr+1))
{
    //交换两个迭代器指向的值
    //注意此时我们并不（*itr)的类型
}

很显然我们需要了解到迭代器所指向的具体类型，这该怎么好呢

毕竟如果C++没有只支持sizeof()，并不支持typeof()

有些人说了我们有RTT1机制中的typeid()，是的很好，但是那获取到的也只是类型名称name，而不是类型type，更不可能来做变量声明

关于RTT1机制中的typeid()，请参见C++ typeid关键字详解

解决方法一函数模版的参数推导机制

解决的方法：利用函数模版（function template）的参数推导（argument deducation）机制。

示例

///理解模板类型推导
#include <iostream>

template <class Iter, class T>
void func_impl(Iter iter, T t)

{
    T tmp;              //  这里解决了问题, T就是迭代器所指之物的类型, 本例为int

    /// ...  这里做原来func应该做的全部工作
}




template<class Iter>
inline func(Iter iter)
{
    func_impl(iter, *iter);
}


int main( )
{
    int i;
    func(&i);
}

解析

参数推导机制，以func()为对外接口，却把实际的操作全部置于func_impl()之中，由于func_impl()是一个函数模版（function template），一旦被调用，编译器会自动进行template的参数推导，于是导出类型T的问题，顺利得到了解决。

问题

但是迭代器相应类型不只是“迭代器所指对象的类型”一种而已

根据经验，最常用的相应类型有5种，然而并非任何情况下任何一种都可利用函数模版的参数推导机制来取得。

因此我们需要更一般的解法。

解决方法二使用嵌套依赖类型(nested depended name)

也称为Traits编程技法，是STL中广泛使用的技巧

迭代器所指对象的类型，称为迭代器的value type，上述的参数类型推导技巧虽然可用于value type，却并不对所有的相应类型可用。

前面的情况，通过隐藏了中间层，通过函数模版自己去推导参数类型，我们的接口也只是关心迭代器而不在意其指向的，但是如果我们的对外接口不能不了解到其相应类型的时候，这种方法就不适用了。

比如如下情况，万一value type必须用于函数的返回值，就束手无策了。

毕竟函数的“template参数推导机制”推而导之的只是参数，无法推导函数的回返值类型。

我们需要其他方法，有什么好的方法呢，还记得之前提到的typename的以及嵌套依赖类型(nested depended name)么。

那不就可以么，我们不妨一试

参见 C++中typename和class在声明模板时的区别

示例

#include <iostream>
template <class T>
struct MyIter
{
    MyIter(T *p = NULL)
    :m_ptr(p)
    {
        /// NOP...
    }

    T& operator*( ) const
    {
        return *m_ptr;
    }



    typedef T value_type;       //  内嵌类型声明{nested type}
    T   *m_ptr;
};


template <class Iter>
typename Iter::value_type          ///  这一整行func的返回值类型
func(Iter iter)
{
    ///
    return *iter;
}


int main(void)
{
    MyIter<int> ite(new int(8));
    std::cout <<func(ite) <<std::endl;
    return 0;
}

解析

func()的返回值被定义为typename Iter::value_type

内嵌类型被定义为 typedef T value_type

由于T是一个template参数，在它被编译器具体化之前，编译器对T一无所知，换句话说，编译器此时并不知道MyIter<T>::value_type代表的是一个类型还是一个成员函数或者说是一个数据成员，

而这个typename关键字的用意就在于告诉编译器这个是一个类型，如敝才能顺利通过编译。

问题

这样我们的问题似乎得到了解决，但是这里有一个隐晦的陷阱：并不是所有的迭代器都是类class type，比如有原生的指针就不是。如果不是class type，就无法为它定义内嵌类型。

但是这显然不是我们做模版类所期待的，在STL（甚至于整个泛型思维）绝对接受原生的指针作为一种迭代器，所有我们上面的方法还不够，有没有什么方法可以让上述的一般化概念针对特定情况（比如原生的指针类型）做特殊化处理呢？

特性萃取机器–偏序化实现支持原生类型

那么这就是template partial specialization可以完成的

模版特化问题

如果class template拥有一个以上的template参数，那么可以针对其中某个（或者多个，但是不能全部）的参数进行特化工作。

换句话说，我们可以在泛化设计中提供一个特化的版本。即通过将泛化版本中的某些template参数赋予明确的指定。

/// 泛化的C接收任意类型
template <typename T>
class C             //  这个泛化版本允许接受T为任意类型
{
    // NOP...
};


/// 特化的类C接收原生的指针作为对象
template <typename T>
class C<T*>             //  这个泛化版本适用于"T为原生指针的情况"
{
    //  T为原生指针便是T为任何型别的一个更进一步的条件限制
    // NOP...
};

关于函数模版的特化问题，不是我们今天的重点，要了解详细信息，请参见
C++模板的特化详解（函数模版特殊，类模版特化）

通过针对任何template参数的模版，进行特化，得到一个限制了参数对象的特化版本。

有了这个利器，我们就可以解决前述的”内嵌类型”未能解决的问题，先前的问题是，原生的指针并非class，因此无法为他们定义内嵌型别。

现在我们可以通过对迭代器指针为参数的特化对象，来设计可以接收原生指针的特殊迭代器。

万能的中间层

因此我们设计出一个中间层，并添加一个value type内嵌对象

//  泛化的iterator_traits对象
template <typename Iter>
struct iterator_traits
{
    typedef typename I::value_type value_type；
};

这个所谓的traits迭代器说明，如果Iter定义有自己的value type，那么就通过这个traits的作用，萃取出来的value_type成员就是Iter::value_type。

换句话说，如果I定义有自己的value type，那么先前的那个func就成为

//  之前的func
template <class Iter>
typename Iter::value_type          ///  这一整行func的返回值类型
func(Iter iter)
{
    ///
    return *iter;
}


//  新的func
template <class Iter>
//typename Iter::value_type          ///  这一整行func的返回值类型
typename iterator_traits<Iter>::value_type
func(Iter iter)
{
    ///
    return *iter;
}

特化中间层以支持原生指针

增加iterator_traits这一中间层，现在我们为iterator_traits添加特化版本。

// 特化的iterator_traits接收<T*>参数
template<class T>
struct iterator_traits<T *>
{
    typedef T value_type;
};

通过这种方式，原生的指针比如int *虽然不是类对象class type，亦可通过traits取其value type。

于是我们的迭代器支持原生的指针类型了。

但是这样子够了么，请看下面的例子，

当我们使用指向const常数对象的指针时，看看发生了什么

iterator_traits<const int *>::value_type

获得到的是一个const int，而不是int。很显然这个并不是我们所期望？

比如我们利用这种方式来声明一个临时变量，使其类别与迭代器的value type相同，而现在，声明一个无法赋值（因const之故）的暂时变量，并没有什么卵用。

这一切的一切，就只是因为我们获取到的迭代器的value type是一个pointer-to-const

进一步特殊const

// 特化的iterator_traits接收<const T*>参数, 萃取出一个T型
template<class T>
struct iterator_traits<const T *>   /
{
    typedef T value_type;
};

现在OK了，不管是针对迭代器MyIterm，还是原生的指针int ，甚至是const int ，都可以通过traits取出正确的value type

代码

///c++11 条款1：理解模板类型推导
///http://blog.csdn.net/coolmeme/article/details/43986163
///http://blog.csdn.net/shinehoo/article/details/5722362
///  STL源码剖析 PDF-119/534

#include <iostream>
#include <typeinfo>


#include <iostream>
template <class T>
struct MyIter
{
    MyIter(T *p = NULL)
    :m_ptr(p)
    {
        /// NOP...
    }

    T& operator*( ) const
    {
        return *m_ptr;
    }



    typedef T value_type;       //  内嵌型别声明{nested type}
    T   *m_ptr;
};


///// 泛化的C接收任意类型
//template <typename T>
//class C             //  这个泛化版本允许接受T为任意类型
//{
//    // NOP...
//};
//
//
///// 特化的类C接收原生的指针作为对象
//template <typename T>
//class C<T*>             //  这个泛化版本适用于"T为原生指针的情况"
//{
//    //  T为原生指针便是T为任何型别的一个更进一步的条件限制
//    // NOP...
//};


//  泛化的iterator_traits对象
template <typename Iter>
struct iterator_traits
{
    typedef typename Iter::value_type value_type;
};

// 特化的iterator_traits接收<T*>参数, 萃取出一个T类型
template<class T>
struct iterator_traits<T *>
{
    typedef T value_type;
};

// 特化的iterator_traits接收<const T*>参数, 萃取出一个T型
template<class T>
struct iterator_traits<const T *>
{
    typedef T value_type;
};


template <class Iter>
//typename Iter::value_type          ///  这一整行func的返回值类型
typename iterator_traits<Iter>::value_type
func(Iter iter)
{
    ///
    return *iter;
}



int main(void)
{

    MyIter<int> ite(new int(8));
    std::cout <<func(ite) <<std::endl;


    std::cout <<typeid(iterator_traits< MyIter<int> >::value_type).name();
    std::cout <<typeid(iterator_traits<int *>::value_type).name();
    std::cout <<typeid(iterator_traits<const int *>::value_type).name();


    return 0;
}

最后通过traits这个特性萃取机角色，可以巧妙的萃取出各个迭代器的属性。

STL中迭代器的设计

这点我们可以在STL源码的找到对应的设计,参见 stl_iterator_base.h
由于

#ifdef __STL_USE_NAMESPACES
template <class _Category, class _Tp, class _Distance = ptrdiff_t,
          class _Pointer = _Tp*, class _Reference = _Tp&>
struct iterator {
  typedef _Category  iterator_category;
  typedef _Tp        value_type;
  typedef _Distance  difference_type;
  typedef _Pointer   pointer;
  typedef _Reference reference;
};
#endif /* __STL_USE_NAMESPACES */

#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION

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;
};

template <class _Tp>
struct iterator_traits<_Tp*> {
  typedef random_access_iterator_tag iterator_category;
  typedef _Tp                         value_type;
  typedef ptrdiff_t                   difference_type;
  typedef _Tp*                        pointer;
  typedef _Tp&                        reference;
};

template <class _Tp>
struct iterator_traits<const _Tp*> {
  typedef random_access_iterator_tag iterator_category;
  typedef _Tp                         value_type;
  typedef ptrdiff_t                   difference_type;
  typedef const _Tp*                  pointer;
  typedef const _Tp&                  reference;
};

转载:http://blog.csdn.net/gatieme/article/details/50950726

C++ Traits编程技法--从迭代器的设计看参数推导与类型推导

迭代器与相应类型推导

解决方法一函数模版的参数推导机制

示例

解析

问题

解决方法二使用嵌套依赖类型(nested depended name)

示例

解析

问题

特性萃取机器–偏序化实现支持原生类型

模版特化问题

万能的中间层

特化中间层以支持原生指针

进一步特殊const

代码

STL中迭代器的设计

热门文章

最新文章

相关课程

相关电子书

相关实验场景