C++泛型编程原理

1.什么是泛型编程
前面我们介绍的vector,list,map都是一种数据结构容器,
容器本身的存储结构不同,各容器中存在的数据类型也可以不同。
但我们在访问这些容器中数据时,拥有相同的方式。
这种方式就叫做“泛型编程”,顾名思义,不同的类型采用相同的方式来操作。

2.泛型编程的原理。
我们先看下面的两个分别访问数组和链表中元素的示例。
示例1,数组类型遍历

void show(double* arr,int n)
{
for(int i=;i<n;i++)
cout<<arr[i]<<" ";
}

示例2,链表类型遍历

struct Node
{
double item;
Node * p_next;
};
void show(Node* head)
{
for(Node* start=head;start!=;start=start->p_next)
cout<<start.item<<" ";
}

我们可以看到,数组和链表的访问方式是完全不同的。
那么,如何使用相同的方式去访问呢?
这两种数据结构的共同点是,它们都是一个顺序存储数据的容器,
所以我们可为每一种容器中定义一个相应的指针类p,在泛型编程中,叫做“迭代器类(iterator)”
该指针类中需要重载两个操作符,
1)*p,访问数据元素内容
2)p++,访问下一个数据元素
示例1,数组容器(double *本身具有*p,p++操作符):

typedef double* iterator;
void show(iterator head,int n)
{
int i=;
for(iterator start=head;i<n;++start)
{
cout<<*start<<" ";
i++
}
}

示例2,链表容器:

struct Node
{
double item;
Node * p_next;
};
class iterator
{
Node *pt;
public:
double operator*()
{
return pt->item;
}
iterator& operator++()
{
pt=pt->p_next;
return *this;
}
};
void show(iterator head)
{
for(iterator start=head;start!=;++start)
{
cout<<*start<<" ";
}
}

我们看到这两种容器的show()方法已基本相同,唯一的区别是结束判断。
在数组中,根据数组长度来判断结尾。
在链表中,根据最后一个元素指向的下一个元素指针为空来判断。
链表比数组多出来一个指向null的指针。

在泛型编程中,使用了“超尾”的概率来解决这个问题,
“超尾”是指在容器的最后一个元素后面,还有一个额外的元素,该元素表示结束。
这样数组和链表都有这个超尾指针。我们统一使用这个超尾指针来判断结尾。

3.泛型编程中迭代器的使用
C++为每个容器类(vector,list,deque等)定义了相应的迭代器类型,
其begin()返回指向第一个元素的迭代器,end()返回指向超尾元素(额外添加的元素)的迭代器。
如下例所示:

vector<double>::iterator pr;
for(pr=scores.begin();pr!=scores.end();pr++)
cout<<*pr<<endl;

在C++11中,简化了迭代器类型的定义,使用auto自动类型

for(auto pr=scores.begin();pr!=scores.end();pr++)
cout<<*pr<<endl;

4.建议使用的遍历方式
很多语言,如C#,并没有使用迭代器iterator,而是使用for,foreach等来遍历数据元素。
所以,C++中最好也避免直接使用迭代器,而尽可能使用for_each()。
C++11中,新增了for循环,如下例所示:

for(auto x:scores)
cout<<x<<endl;

参考资料:《C++ Primer.Plus》 pp.685-688

上一篇:LeetCode算法题 菜鸟总结


下一篇:Redis配置文件 Redis.conf详解