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

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);

其中第二个参数是利用 node_wrap 的缺省构造函数做出。他产生出一个内含 null 指针的 node_wrap。由于链表最后一个结点的 next 指针即为 null，所以我们会从 list_head 查找直至链表尾端。至此，我们重用了已有的算法来作用于链表上。

外覆类做了什么？

他将我们原始的结点指针包装了起来，同时定义或重载了一些操作，使得整个外覆类对外显示出一个指针常见的操作接口，以便其他的组件可以透明的将他作为一个指针来使用。而因不同的数据组织方法而形成指针操作差异将由外覆类负责包装和隐藏，并由他在类的内部将这种差异进行具体的实现，导致最终的结果是，他将原本有差异的事物，统一了起来。

带来的好处是什么？

在考虑他带来的好处之前，我们先想想没有他是怎样的情况。如果没有外覆类的包装，每当我们实现一个概念上相同的数据结构时，我们要将所有在这个数据结构上存在的算法实现一遍，即便已经存在相同概念的模型的算法，但是由于数据的组织方式不同存在的一些差异，我们很难重用这些算法。

外覆类带来的好处显而易见的是我们可以重用已经实现过的算法。而得以实现这一点的关键就在于外覆类消除了差异性，对外提供了统一的接口，而差异性越少，我们能重复利用的部分就越多。