一、迭代器的概念

1. 设计目标：提供一种顺序访问聚合对象的元素而不暴露其底层表示的方法
2. 迭代器的使用方式应尽量与指针贴近，包括通过运算符重载实现 ++、 * 、 -> 等

// 定义 list 迭代器
template <class T>
class ListIter
{
private:
	ListItem<T> *ptr;
public:
	ListIter(ListItem<T> *p = 0): ptr(p) {}
	ListIter<T>& operator++()
	{ 
		ptr = ptr->next(); 
		return *this;
	}
	bool operator==(const ListIter& i) const
	{
		return ptr == i.ptr;
	}
	T& operator*()
	{
		return ptr->val();
	}
	T* operator->()
	{
		return &(**this);
	}
}

// 定义 find 函数
template <class Iterator, class T>
Iterator find(Iterator first, Iterator last, const T& value)
{
	while (first != last && *first != value) ++first;
	return first;
}

// Usage
vector<int> vecTemp;
if(find(vecTemp.begin(), vecTemp.end(), 3) == vecTemp.end())
	cout << "3 not found" << endl;

二、关联类型 Associated Type

1. 问题描述

• 问题：不知道 iter 指向的数据类型，需要借助另一个变量 v 推导出类型 T

  template <class I, class T>
  void func_impl(I iter, T& v)
  {
    T tmp;
    tmp = *iter;
    // 处理代码
  

• 包装一层，自动推导类型：

  template <class I>
  void func(I iter)
  {
    func_impl(iter, *iter);
    // 处理代码
  }
  

2. 改进：在迭代器内部显式定义类型

• 在迭代器内部，使用 typedef 显式定义类型：

  template <class T>
  struct myIter {
    typedef T value_type;
    T* ptr;
    myIter(T *p = 0) : ptr(p) {}
    T& operator*() { return *ptr; }
  };
  

• 使用：

  template <class I>
  typename I::value_type func(I iter) {
    return *iter;
  }
  
  myIter<int> iter(new int(8));
  cout << func(iter);
  

• **问题：**指针不是结构体，不能在指针内部使用 Typedef 显式定义类型，从而只支持迭代器，而无法支持指针类型（如 int* 、double* ），影响 STL 编程

3. 改进：iterator_traits

• 定义通用模板：

  template <class I>
  struct iterator_traits {
    typedef typename I::value_type value_type;
  };
  

• 使用：

  template <class I>
  typename iterator_traits<I>::value_type func(I iter) {
    return *iter;
  }
  
  myIter<int> iter(new int(8));
  cout << func(iter);
  
  int* p = new int[20]();
  cout << func(p); // 需要处理指针类型，详见下文
  

4. 模板特化 Template Specialization

• 完全特化（Full Specialization）：

  template<>
  class A<int, double, 5> { /*...*/ };
  

• 部分特化（Partial Specialization）：

  template<class T2>
  class A<int, T2, 3> { /*...*/ };
  

5. 针对指针的 iterator_traits 特化