泛型编程也是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
具体有什么方法使我们自己来实现的。
网友评论