泛型编程也是C++多态的一种重要形式，其通过模板来实现代码的重用。一般而言，泛型编程将算法与数据结构分离，通过Template的形式，使得算法能够特化成不同的数据类型。下面来感受一下泛型编程的神奇之处。
实现一个线性Find函数
template <class Iterator, class T>
Iterator Find(Iterator begin, Iterator end, const T& value)
{
while(begin != end && *begin != value)
begin++;
return begin;
};
上述是一个泛型函数，通过传入所要查询的数据集的起点与终点迭代器，以及目标值，如查询到目标值，则返回对应的迭代器，否则返回end。只要我们传入的数据集的迭代器支持线性的迭代，就都可以使用这个Find函数来进行查询，如：
vector<int> data = {1, 2, 3 ,4 ,5};
auto res = Find(data.begin(), data.end(), 4);
/// list<int> data = {1, 2, 3, 4, 5};
/// auto res = Find(data.begin(), data.end(), 4);
/// array<string, 10> data = { "hello", "world"};
/// auto res = tfind(data.begin(), data.end(), "hello");
if(res != data.end())
cout << *res << endl;
else
cout << "Not Found" << endl;
return 0;
如上，因为vector, array等支持线性迭代，所以可以在不用更改Find的情况下实现不同类型数据的查询。那这个迭代器能否用于二叉树，邻接表等更加复杂的数据结构呢？当然可以，只要我们实现按照这些数据结构的遍历方式，实现一个对应的Iterator，便可将上面的Find函数用于这些数据结构上了。
那为了让我们的Iterator能够用于上面的Find函数，我们需要什么接口呢？仔细观察，需要：
- 重载
==和!= - 重载
++ - 重载
*
下面，我们来实现一个链表的Iterator
实现一个链表的Iterator
首先，定义一个链表的节点：
template <typename T>
class list_node
{
public:
T value;
list_node* next;
explicit list_node(T t)
{
value = t;
next = nullptr;
}
bool operator == (const T t)const
{
return value == t;
}
bool operator != (const T t)const
{
return value != t;
}
};
上述是一个模板类，内部有一个模板变量，并重载了==和!=操作符。接下来，我们来实现上述list_node的Iterator:
template <typename node>
class list_iterator
{
private:
node* curr_ptr;
public:
explicit list_iterator(node* p = nullptr) : curr_ptr(p){};
node& operator * () const
{
return *curr_ptr;
}
node* get () const
{
return curr_ptr;
}
node* operator -> () const
{
return curr_ptr;
}
list_iterator<node>& operator ++ ()
{
curr_ptr = curr_ptr->next;
return *this;
}
list_iterator<node>& operator ++ (int)
{
this->operator++();
return *this;
}
bool operator == (const list_iterator<node>& src) const
{
return src.get() == curr_ptr;
}
bool operator != (const list_iterator<node>& src) const
{
return src.get() != curr_ptr;
}
};
在重载++时，我们依据list_node的实际情况，使用next指针得到下一个元素，测试如下：
int main()
{
auto n1 = new list_node(1);
auto n2 = new list_node(2);
auto n3 = new list_node(3);
n1->next = n2;
n2->next = n3;
auto res = Find(list_iterator<list_node<int>>(n1),
list_iterator<list_node<int>>(),
3);
if (res.get())
cout << res->value << endl;
else
cout << "Not found" << endl;
return 0;
}
这里使用list_iterator<list_node<int>>()作为end，注意，Find返回的是一个Iterator,而这个Iterator具体有什么方法使我们自己来实现的。
