从具体开始
首先让我们先实现一个查找数组中是否存在一个数的例子开始：
int* find1(const int* array, int n, int x)
{
const int* p = array;
for(int i = 0; i < n; i++) {
if (*p == x) {
return p;
}
p++;
}
return nullptr;
}
在array这个数组中查找x，如果存在则返回位置p否则返回nullptr;
针对这个函数我们看看find1需要知道哪些信息：
- 元素类型需要为
int - 我们是在
int的数组类型中查找 - 需要知道数组一共有多少个元素
n - 还需要知道起始位置
array
下面我们看看怎么将这个算法泛型化。
首先就是要去掉对于元素类型的依赖，这个很容易想到采用模版来实现：
template <class T>
T* find2(T* array, int n, const T& x)
{
T* p = array;
for(int i = 0; i < n; i++) {
if (*p == x) {
return p;
}
p++;
}
return nullptr;
}
find2对比find1我们可以发现array的const属性被我们去掉了，因为函数模版的原因，如果传入的参数是一个携带const修饰的，那么T也会携带const修饰。
然后对于参数x我们采用了const T&是为了避免不必要的复制，并且可以让调用者传右值。
find2函数对类型T有以下的要求：
- T必须支持
operator== - T支持的
operator==必须返回一个可以转换为bool类型的类型。
目前find2依旧依赖与知道数组的起始位置和数组元素数量，我们来看看如何抽象掉关于数据结构存储的细节。
首先我们来考虑如何不再需要知道数组元素的个数。
如果我们知道数组的起始位置和终止位置循环里面就可以使用p != end进行判断是否终止循环了。所以我们修改find2为：
template <class T>
T* find3(T* start, T* end, const T& x)
{
T* p = start;
for(; p != end;) {
if (*p == x) {
return p;
}
p++;
}
return nullptr;
}
现在的问题是我们如何确定end的值。如果我们简单的将end当作数组最后一个元素的位置，那么如果数组是空数组会出现什么情况？因为根本不存在最后一个元素，会导致指向最后一个元素的指针将在指向第一个元素的指针之前：因为不存在最后一个元素所以指向最后一个元素的指针为nullptr，nullptr < start.。
所以我们采用更加符合常理的，end表示指向最后一个元素的下一个位置。
由此我们也可以修改find的含义：如果找不到返回end。
template <class T>
T* find4(T* start, T* end, const T& x)
{
T* p = start;
while( p != end && *p != x) {
p++;
}
return p;
}
经过我们的修改，现在find4()函数不在依赖于元素类型，数组中元素个数。但是我们还是依赖于这是个数组存储的数据结构，而且依赖于指针。
我们看看find4依赖了指针的什么操作：
- 解引用操作。
- 比较操作。
- 自增操作。
而且还依赖了入参需要为指针。
根据上一篇sum的抽象化，我们可以想到：如果使用的是迭代器类型，我们就不在依赖于指针了。由此得出：
template <class T, class Iter>
Iter find6(Iter start, Iter end, const T& x)
{
Iter p = start;
while( p != end && *p != x) {
p++;
}
return p;
}
只要这个迭代器实现了operator!=,operator++,operator*的操作，满足入参的值传递（支持拷贝构造）我们的算法就是可以正常运行的。无论底层的存储结构是什么。
查找非数组
假设我们采用链表存储数据：
struct Node
{
std::string value;
Node* next;
};
我们可以为这个链表构造一个满足上面要求的迭代器类：
class Node_pointer
{
public:
Node_pointer(Node* p):pt(p) {}
Node_pointer(const Node_pointer& other) = default;
std::string& operator*() { return pt->value; }
void operator++(int) { pt = pt->next; }
friend bool operator!=(const Node_pointer& op1, const Node_pointer& op2);
friend bool operator==(const Node_pointer& op1, const Node_pointer& op2);
private:
Node* pt;
};
bool operator!=(const Node_pointer& op1, const Node_pointer& op2)
{
return op1.pt != op2.pt;
}
bool operator==(const Node_pointer& op1, const Node_pointer& op2)
{
return !(op1 != op2);
}
此时我们使用find5(Node_pointer(p), Node_pointer(nullptr), x)就已经可以执行我们的算法了。
总结
我们采用模版的方式将find函数所依赖的事情降低到了最小的地步。对于编写通用的算法库来讲，我们取得了一些进展，但是针对算法的不同，可能并不能完全像find的依赖一样。更多的细节，我们在下一篇详细看看对于迭代器的进一步抽象：泛型迭代器。
