Traits-STL

背景

在STL迭代器中，为了适配不同类型的容器，常常需要迭代器主动获取 迭代器指向的类型，并且申明该类型的变量。模板函数的参数推导功能可用于推导变量类型

template <class IT>
void func_impl(IT itval) { // 迭代器指向对象的类型
	IT a = itval;
	cout << "获得了迭代器所指类型并申明了该类型变量,该类型长度为 " << sizeof(a) << endl;
}

template <class T>
void func(T iter) {    // 迭代器类型
	func_impl(*iter);  // 添加了一层间接性
}

int main() {
	int a = 3;
	double b = 0.1l;
	func(&a);
	func(&b);
	return 0;
}

//////////////////////
4
8

可以看出，通过加一层函数模板的封装，可以推导出迭代器所指对象类型并定义变量，然而如果想要函数返回迭代器所指类型的变量却不可行，因为在调用这个函数模板前，我们并不能得到返回对象的类型，因此无法确定func的返回类型。

在func中，我们可以通过模板参数推导立即得到迭代器的类型，如果可以通过迭代器直接获取它所指对象的类型，那么便能达成我们的目的。内嵌型别声明可以完成这一任务

template <class T> 
struct Iter {
  typedef T value_type;   // 内嵌型别声明
  T *ptr;
  Iter(T *p = 0) : ptr(p) {}
  T &operator*() const { return *ptr; }
};

template <class I> 
typename I::value_type    // 通过推导出类型为Iter，然后根据Iter内部定义的value_type得到指向类型
func(I it) { 
	return *it; 
}

int main() {
  Iter<int> it(new int(1));
  cout << func(it) << endl;
  return 0;
}

那么现在只要迭代器在内部定义了value_type，那么就能通过模板推导出其指向类型。但是有个问题是原生指针并未定义该type，那么传入原生指针的时候，该函数就失效了。模板分为函数模板和类模板，它们都可以进行偏特化，先看看一个直接的做法，直接对该函数进行特化

template <class T> struct Iter {
  typedef T value_type; // 内嵌型别声明
  T *ptr;
  Iter(T *p = 0) : ptr(p) {}
  T &operator*() const { return *ptr; }
};

template <class I> typename I::value_type func(I ite) {
  std::cout << "class version" << std::endl;
  return *ite;
}

// 直接对func函数偏特化
template <class I> I func(I *ite) {
  std::cout << "pointer version" << std::endl;
  return *ite;
}
template <class I> I func(const I *ite) {
  std::cout << "const pointer version" << std::endl;
  return *ite;
}
int main() {
  Iter<int> ite(new int(8));
  cout << func(ite) << endl;
  int *p = new int(52);
  cout << func(p) << endl;
  const int k = 3;
  cout << func(&k) << endl;
}

这样该函数传入原生指针也能够正常工作了，但是缺点是如果func代码量很长，就会多出两个影响阅读的函数代码。而且不够泛型化，要求之后所有基于该迭代器的函数都要提供两个特化版本，降低开发效率。与之前类似，可以对提取类型这件事加一层封装，让这层封装来处理这两个特化版本，后续函数调用该封装就不用自己特化。于是定义专门用于类型提取的类模板：

template <class T> struct Iter {
  typedef T value_type; // 内嵌型别声明
  T *ptr;
  Iter(T *p = 0) : ptr(p) {}
  T &operator*() const { return *ptr; }
};

//！！！ 用于中间层的类模板
template <class T> struct iterator_traits {
  typedef typename T::value_type value_type;
  int a;
};

// 偏特化1
template <class T> struct iterator_traits<T *> { typedef T value_type; };
// 偏特化2
template <class T> struct iterator_traits<const T *> { typedef T value_type; };

template <class I>
typename iterator_traits<I>::value_type
func(I ite) {  // 通过类模板iterator_traits去提取迭代器类型，函数模板func本身不用操心
  std::cout << "normal version" << std::endl;
  return *ite;
}
int main() {
  Iter<int> ite(new int(8));
  std::cout << func(ite) << std::endl;
  int *p = new int(52);
  std::cout << func(p) << std::endl;
  const int k = 3;
  std::cout << func(&k) << std::endl;
}

category

算法在使用不同迭代器的时候，应该有能力根据不同迭代器类型选择不同的方案，因为可以随机访问的迭代器往往比挨个访问要快。那么就要求我们能够提取出迭代器本身的类型，那么可用同样的方法——在迭代器内部定义自己的类型，这个类型往往是人为分类的，也需要事先定义出来，不过是一个空类，只用于类型区分：

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_iterator_tag : public bidirectional_iterator_tag {};

定义好用于区分的类后，在自己的迭代器类中进行内嵌型别声明，然后就可以通过iterator_traits提取类型，并且为了避免在运行时判断是哪个类型再去调用，可以通过函数重载实现该静态多态，于是需要再添加一层封装。

在实现自己的迭代器时，我们可以手动给每类iter都声明category

template <typename T> struct InputIter {
  typedef input_iterator_tag category;  // 手动声明
  typedef T value_type;
  InputIter() = default;
  T *ptr;
  InputIter(T *p = 0) : ptr(p) {}
  T &operator*() const { return *ptr; }
};

！！

但是这样容易忘记，且增加代码量，因此可以实现一个迭代器基类，在其中包含关于category的模板参数，然后真正的迭代器在继承它的时候，特化这个参数即可，该基类一般定义如下

template<class Category, class T, class Difference = ptrdiff_t, class Pointer =T*,class Reference = T&> struct iterator
{
    typedef T value_type;
    typedef Difference difference_type;
    typedef Pointer pointer;
    typedef Reference reference;
    typedef Category iterator_category
}；

继承时特化该 类别参数

template <typename T> struct InputIter : public iterator<input_iterator_tag, T> {
  InputIter() = default;
  T *ptr;
  InputIter(T *p = 0) : ptr(p) {}
  T &operator*() const { return *ptr; }
};

template <typename T> struct ForwardIter : public iterator<forward_tag, T> {
  ForwardIter() = default;
  T *ptr;
  ForwardIter(T *p = 0) : ptr(p) {}
  T &operator*() const { return *ptr; }
};

template <typename T> struct iterator_traits {
  typedef typename T::value_type value_type;
  typedef typename T::category category;
};
// 偏特化1
template <typename T> struct iterator_traits<T *> {
  typedef T value_type;
  typedef random_iterator_tag category;
};
// 偏特化2
template <typename T> struct iterator_traits<const T *> {
  typedef T value_type;
  typedef random_iterator_tag category;
};

// 针对不同category的具体实现
template <typename InputIter> void _func(InputIter &i, input_iterator_tag) {
  std::cout << "inputiter" << std::endl;
  return;
}

template <typename ForwardIter> void _func(ForwardIter &i, forward_iterator_tag) {
  std::cout << "forwarditer" << std::endl;
  return;
}

template <typename RandomIter> void _func(RandomIter &i, random_iterator_tag) {
  std::cout << "randomiter" << std::endl;
  return;
}

// 声明函数的方法来返回该类型的一个实例, 或用# 方法
// template <typename I>
// inline typename iterator_traits<I>::category category(const I &) {
//   typedef typename iterator_traits<I>::category category;
//   return category();
// }

template <typename I>
typename iterator_traits<I>::value_type
// 通过类模板iterator_traits去提取迭代器类型，函数模板func本身不用操心
func(I ite) {
  typedef typename iterator_traits<I>::category category; // #.事先声明category为一个类型
  _func(ite, category());
  return *ite;
}
int main() {
  InputIter<int> ite(new int(8));
  std::cout << func(ite) << std::endl;
  ForwardIter<int> iter(new int(2));
  std::cout << func(iter) << std::endl;
  std::cout << func(new int(1)) << std::endl;
}