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 查找直至連結清單尾端。至此，我們重用了已有的算法來作用于連結清單上。

外覆類做了什麼？

他将我們原始的結點指針包裝了起來，同時定義或重載了一些操作，使得整個外覆類對外顯示出一個指針常見的操作接口，以便其他的元件可以透明的将他作為一個指針來使用。而因不同的資料組織方法而形成指針操作差異将由外覆類負責包裝和隐藏，并由他在類的内部将這種差異進行具體的實作，導緻最終的結果是，他将原本有差異的事物，統一了起來。

帶來的好處是什麼？

在考慮他帶來的好處之前，我們先想想沒有他是怎樣的情況。如果沒有外覆類的包裝，每當我們實作一個概念上相同的資料結構時，我們要将所有在這個資料結構上存在的算法實作一遍，即便已經存在相同概念的模型的算法，但是由于資料的組織方式不同存在的一些差異，我們很難重用這些算法。

外覆類帶來的好處顯而易見的是我們可以重用已經實作過的算法。而得以實作這一點的關鍵就在于外覆類消除了差異性，對外提供了統一的接口，而差異性越少，我們能重複利用的部分就越多。

感謝閱讀

轉載請注明出處

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