C++泛型线性查找算法——find

《泛型编程和STL》笔记及思考。

线性查找可能是最为简单的一类查找算法了。他所作用的数据结构为一维线性的空间。这篇文章主要介绍使用 C++ 实现泛型算法 find的过程。

C 版本

首先介绍 C find 算法的实现，用以引入 C++ 版本。
char *find1(char *first,char *last,int c) {
  while(first != last && *first != c)
    ++first;
  return first;
}

该版本的算法循环检查每个元素，尾后指针(last)作为结束标识。

使用举例如下：
char A[N];
...
char *result = find1(A,A + N,c);
if(result == A + N)
  printf("search failed\n");
else printf("found it");

C 实现的 find 算法实现很简单，但使用范围很局限，只能应用于字符数组中对指定字符的查找。

C++ 版本

由于 C 版本 find 的使用范围局限性，在 C++ 中，我们可以使用泛型对策，利用 template 将函数的参数类型参数化。

首先，我们可以考虑设计一个类似 C 版本的 find 算法，以任意类型 T 的指针作为参数，代替原来的 char 指针。所以该方法声明如下：
template<class T>
T *find2(T *first,T *last,T value);

这样 find 方法就不在局限于一种类型可以使用了。

不过，STL 的泛型做法不像上述那般显而易见。STL 的线性查找算法是这样定义的：
template<class Iterator,class T>
Iterator find(Iterator first,Iterator last,const T& value) {
    while(first != last && *first != value)
        ++first;
    return first;
}

为什么是 find 而不是看起来更浅显的 find2 呢？

原因简单的说，是因为这样的函数比 find2 更加的一般化。这种一般化的一个主要体现就是，它不再依赖数据结构的具体实现。比如，在链表上的线性查找。

链表上的查找

我们将把 find 用于单链表的线性查找，来证实 find 的一般性。虽然数组和链表对元素的组织方式不同，但是 基于线性序列的 find 仍可以适用于二者。

下面是一个链表结点的数据结构：
struct int_node {
  int val;
  int_node* next;
};

链表的遍历方法：
int_node* p;
for (p = list_head; p != NULL; p = p->next)
    //pass

单链表是一个线性序列，线性查找是一种常见的行为。既然是线性查找，而我们之前又写过线性查找算法，那么我们不应该编写重复的代码，而是考虑重用这个函数。

首先考虑我们实现过的第一个泛型查找算法 find2。find2 接受的参数为一个范围 [first,last)，这个范围通过传递两个指针来界定。但是这里有个显而易见的问题，指向结点的指针如何在单链表上前进？假设我们有一个 int_node 指针 first 并传递给 find2 函数，然后我们希望通过 first++ 来实现指针的移动，注意问题便在这里，first ++ 操作无法到达下一个元素。因为 find2 算法应对的是线性序列使用数组实现的情况，而现在，序列元素的组织方式为链式结构，指针前进的方式不再是通过增加元素指针的值（first++）来实现。对于链表，操作应当是 first = first->next。

如何解决这个问题？

方案一 ：使用 C++ 中的操作符重载

如果上述的 operator++ 行为不符合需要，那么就重新定义他的行为，

也即：
原 ++ 操作：    a = a + 1;
现 ++ 操作：    a = a->next;

使得 find2 可以正常工作。

然而，重新定义参数类型为 int_node* 类型的 operator++ 操作符是不可能的，C++ 允许我们定义操作符的表达式意义，单不允许变动既有的语法意义（我们不能随便的将一个指针的自加行为改变为其他的操作，就像不能将整数 + 运算符定义为 减、乘操作，这是不合适的）。

方案二  : 增加一个包装类（外覆类 wrapper class）

我们通过编写一个简单的外覆类（wrapper class）使他看起来像一个 int_node* ,而他的 operator++ 有更为合适的定义。

外覆类的定义：
template<class Node>            //这里传递的参数是 类型 int_node
struct node_wrap {
    Node* ptr;
   
    node_wrap(Node* p = 0) : ptr(p) { }
    Node& operator* const { return *ptr; }
    Node* operator-> const { return ptr; }
   
    node_wrap& oeprator++() { ptr = ptr->next; return *this; }
    node_wrap operator++(int) { node_wrap tmp = *this; ptr = ptr->next; return tmp; }
   
    bool operator== (const node_wrap& i) const { return ptr == i.ptr; }
    bool operator!= (const node_wrap& i) const { return ptr != i.ptr; }
};

事实上我们还是重载了 operator++ 的行为，但是现在是在外覆类上的重载，而不是指针上的重载，对于外覆类来说，这种行为是合适的。

最后，由于 find 函数中的
while(... *first != value)

语句中，*first != value 这个不等运算符的操作并没有定义，所以下面对他进行定义：
bool operator!= (csonst node_wrap& i,int n) const { return i.value != n; }

那么现在，我们欲查找 int_node 中的某一个特定值，我们不需要在重复编写任何代码了，我们可以重复利用 find，将查找动作写成单一函数调用：
find(node_wrap<int_node>(list_head),node_wrap<int_node>(),val);