從具體開始
首先讓我們先實(shí)現(xiàn)一個(gè)查找數(shù)組中是否存在一個(gè)數(shù)的例子開始：
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這個(gè)數(shù)組中查找x，如果存在則返回位置p否則返回nullptr;
針對(duì)這個(gè)函數(shù)我們看看find1需要知道哪些信息：
- 元素類型需要為
int - 我們是在
int的數(shù)組類型中查找 - 需要知道數(shù)組一共有多少個(gè)元素
n - 還需要知道起始位置
array
下面我們看看怎么將這個(gè)算法泛型化谎柄。
首先就是要去掉對(duì)于元素類型的依賴丁侄，這個(gè)很容易想到采用模版來實(shí)現(xiàn)：
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對(duì)比find1我們可以發(fā)現(xiàn)array的const屬性被我們?nèi)サ袅耍驗(yàn)楹瘮?shù)模版的原因朝巫，如果傳入的參數(shù)是一個(gè)攜帶const修飾的鸿摇，那么T也會(huì)攜帶const修飾。
然后對(duì)于參數(shù)x我們采用了const T&是為了避免不必要的復(fù)制劈猿，并且可以讓調(diào)用者傳右值拙吉。
find2函數(shù)對(duì)類型T有以下的要求：
- T必須支持
operator== - T支持的
operator==必須返回一個(gè)可以轉(zhuǎn)換為bool類型的類型。
目前find2依舊依賴與知道數(shù)組的起始位置和數(shù)組元素?cái)?shù)量揪荣，我們來看看如何抽象掉關(guān)于數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)的細(xì)節(jié)庐镐。
首先我們來考慮如何不再需要知道數(shù)組元素的個(gè)數(shù)。
如果我們知道數(shù)組的起始位置和終止位置循環(huán)里面就可以使用p != end進(jìn)行判斷是否終止循環(huán)了变逃。所以我們修改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;
}
現(xiàn)在的問題是我們?nèi)绾未_定end的值必逆。如果我們簡(jiǎn)單的將end當(dāng)作數(shù)組最后一個(gè)元素的位置，那么如果數(shù)組是空數(shù)組會(huì)出現(xiàn)什么情況揽乱？因?yàn)楦静淮嬖谧詈笠粋€(gè)元素名眉，會(huì)導(dǎo)致指向最后一個(gè)元素的指針將在指向第一個(gè)元素的指針之前：因?yàn)椴淮嬖谧詈笠粋€(gè)元素所以指向最后一個(gè)元素的指針為nullptr，nullptr < start.凰棉。
所以我們采用更加符合常理的损拢，end表示指向最后一個(gè)元素的下一個(gè)位置。
由此我們也可以修改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;
}
經(jīng)過我們的修改福压，現(xiàn)在find4()函數(shù)不在依賴于元素類型，數(shù)組中元素個(gè)數(shù)或舞。但是我們還是依賴于這是個(gè)數(shù)組存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)荆姆，而且依賴于指針。
我們看看find4依賴了指針的什么操作：
- 解引用操作映凳。
- 比較操作胆筒。
- 自增操作。
而且還依賴了入?yún)⑿枰獮橹羔槨?br>
根據(jù)上一篇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;
}
只要這個(gè)迭代器實(shí)現(xiàn)了operator!=,operator++,operator*的操作矫渔，滿足入?yún)⒌闹祩鬟f（支持拷貝構(gòu)造）我們的算法就是可以正常運(yùn)行的彤蔽。無論底層的存儲(chǔ)結(jié)構(gòu)是什么。
查找非數(shù)組
假設(shè)我們采用鏈表存儲(chǔ)數(shù)據(jù)：
struct Node
{
std::string value;
Node* next;
};
我們可以為這個(gè)鏈表構(gòu)造一個(gè)滿足上面要求的迭代器類：
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);
}
此時(shí)我們使用find5(Node_pointer(p), Node_pointer(nullptr), x)就已經(jīng)可以執(zhí)行我們的算法了庙洼。
總結(jié)
我們采用模版的方式將find函數(shù)所依賴的事情降低到了最小的地步顿痪。對(duì)于編寫通用的算法庫來講镊辕，我們?nèi)〉昧艘恍┻M(jìn)展，但是針對(duì)算法的不同员魏，可能并不能完全像find的依賴一樣。更多的細(xì)節(jié)叠聋，我們?cè)谙乱黄敿?xì)看看對(duì)于迭代器的進(jìn)一步抽象：泛型迭代器撕阎。
