“感覺(jué)這一家有做大的趨勢(shì)……”老C一邊喝茶消食一邊對(duì)小P發(fā)表自己的看法。
“的確，他家已經(jīng)把旁邊的店生意快搶光了，估計(jì)過(guò)一些時(shí)間就會(huì)把隔壁的店買下來(lái)了。”小P亦有同感，“怪不得最近食堂的刀削面師傅辭工，可能創(chuàng)業(yè)去了……”
“？是么？呵呵，也許吧。”老C笑道，“不過(guò)看在你請(qǐng)客的面子上，我決定和你多聊幾句……”
“哦，是的是的。你要告訴我如何更好的實(shí)現(xiàn)線性表。”小P接道。
“嘻嘻，是的是的。不過(guò)這次我要先寫一段代碼……”老C說(shuō)道。
“……是啊……”小P于是很自覺(jué)的將白板擦干凈，并拉到兩人面前。
“我們現(xiàn)在的題目是，寫一個(gè)函數(shù)，作用是在一個(gè)線性表中查找某一個(gè)特定元素。”老C說(shuō)道，“我們先從數(shù)組開(kāi)始，這樣比較簡(jiǎn)單。”
int* find (int* first, int* last, const int val);
int* find(int* first, int* last, const int val)
{
for (; first != last; ++first)
{
if (val == *first)
{
break;
}
}
return first;
}
“在這里我們用[first, last)表示需要查找的區(qū)間，如果找到就返回元素的指針，否則返回last。”老C解釋，“為了更清楚的表明此函數(shù)所在的應(yīng)用環(huán)
境，我們?cè)賮?lái)一段使用它的代碼。”
#include <iostream>
int* find (int* first, int* last, const int val);
const int MAX_SIZE = 5;
int main()
{
int a[MAX_SIZE] = {0, 1, 2, 3, 4};
const int* iter = find(&a[0], &a[MAX_SIZE], 3);
if (iter != &a[MAX_SIZE])
{
std::cout << "The element is at NO. " << (iter - &a[0]) + 1 << " position." << std::endl;
}
else
{
std::cout << "Not be found!" << std::endl;
}
}
int* find(int* first, int* last, const int val)
{
for (; first != last; ++first)
{
if (val == *first)
{
break;
}
}
return first;
}
“看，find()函數(shù)就是這樣被使用的。”老C說(shuō)道，“同時(shí)我要提醒一下你，數(shù)組類型與指針類型是不同的類型，因?yàn)閿?shù)組類型還帶有數(shù)組長(zhǎng)度的信息。比如
int a[2] 與 int* a，這是兩種類型，其中int a[]可以被內(nèi)部轉(zhuǎn)型為int*
，但是反之則不行。可惜的是數(shù)組類型無(wú)法作為函數(shù)參數(shù)，在使用函數(shù)對(duì)數(shù)組進(jìn)行操作的時(shí)候不得不將其轉(zhuǎn)型為指針……這個(gè)就是C中的數(shù)組降維問(wèn)題……總之你要
明白，數(shù)組與指針是不同的類型，但數(shù)組可以被轉(zhuǎn)型為指針——代價(jià)是丟失長(zhǎng)度信息——反之則不行。”
“好，我了解了。”小P回答，心想好像在哪本書上說(shuō)過(guò)貌似數(shù)組和指針沒(méi)有什么區(qū)別的。為了確認(rèn)這個(gè)事情，他決定再google一下。
“喏，如果我們使用了[first,
last)的表達(dá)形式，很多對(duì)線性表的操作就可以統(tǒng)一起來(lái)，這樣我們將指向線性表元素的指針提取出來(lái)，就使得用戶使用這些線性表就好像在使用一個(gè)數(shù)組似
的。這樣會(huì)大大減輕用戶記憶的難度，同時(shí)也使得編程人員避免了很多下意識(shí)的錯(cuò)誤——比如過(guò)一錯(cuò)誤。”老C說(shuō)道，“而這個(gè)被提煉出來(lái)的指針，我們就叫它
iterator。”
“是么？”小P道，“原來(lái)iterator就是這樣來(lái)的啊。”
“剛才的例子是trivial的，我們?cè)偕钊胍稽c(diǎn)點(diǎn)。”老C說(shuō)道，“如果我們希望find()函數(shù)可以被運(yùn)用到所有類型的線性表，那么可以怎么做呢？”看
到小P有些槑，老C自問(wèn)自答，“其實(shí)方法有很多，我們可以將find()看成對(duì)象——一切皆為對(duì)象——如果使用面向?qū)ο蟮姆椒ǎ缓筇釤挸鲆粋€(gè)find
類，讓findVector和findList成為它的子類，find類中的操作寫為虛函數(shù)，然后讓findVector子類和findList子類去修
改這些虛函數(shù)以滿足自己的實(shí)際需要，這可以被稱為strategy模式的一個(gè)簡(jiǎn)單應(yīng)用。但是這個(gè)方法我們先避開(kāi)不談，在這里我們采用另外一個(gè)方法。”他找
到茶杯喝了一口，“我們將這個(gè)iterator提煉為一個(gè)類，同時(shí)保持find()函數(shù)的實(shí)現(xiàn)不變，然后在這個(gè)iterator上動(dòng)腦筋。”
“那么應(yīng)當(dāng)怎么做呢？”小P問(wèn)道。
“嗯，如果find()函數(shù)的代碼不變，那么我們可以這么做。”老C說(shuō)著打開(kāi)了電腦，新建立了一個(gè)工程開(kāi)始敲鍵盤，一邊敲一邊給小P解釋著。
find.h:
#if !defined(FIND_H_)
#define FIND_H_
#include "iterator.h"
Iterator& find(Iterator& first, Iterator& last, const ValueType& val)
{
for (; first != last; ++first)
{
if (val == *first)
{
break;
}
}
return first;
}
#endif // FIND_H_
“看，我們希望的finde()函數(shù)可以是這樣的一種接口和實(shí)現(xiàn)。”老C解釋，“而且希望它可以這樣被使用。”
main.cpp:
#include "implement.h"
#include "find.h"
#include <iostream>
const int MAX_SIZE = 5;
int main()
{
IntValueType a[MAX_SIZE] = {0, 1, 2, 3, 4};
IntVector intVec(&a[0], &a[MAX_SIZE]);
IntList intList(&a[0], &a[MAX_SIZE]);
//IntVectorIter first = intVec.begin();
//IntVectorIter last = intVec.end();
IntListIter first = intList.begin();
IntListIter last = intList.end();
Iterator& it = find(first, last, IntValueType(4));
if (it != last)
{
std::cout << "Find " << (*it) << std::endl;
}
else
{
std::cout << "Cannot find " << std::endl;
}
return 0;
}
“在這里我們假設(shè)find()函數(shù)即可以用在vector上，也可以用在linked list上，橋梁就是Iterator類。”老C解釋道，“這下我們就可以根據(jù)find()函數(shù)的實(shí)現(xiàn)看看我們需要什么樣子的Iterator類的接口了。”
class Iterator
{
public:
virtual Iterator& operator++() = 0;
virtual ValueType& operator*() = 0;
virtual bool operator==(Iterator& rhs) = 0;
virtual bool operator!=(Iterator& rhs) = 0;
protected:
~Iterator() {}
};
“根據(jù)find()函數(shù)的實(shí)現(xiàn)，我們知道Iteratro類必須擁有上面列出的接口。在這里我把Iterator類設(shè)計(jì)為抽象類，因?yàn)樗皇翘峁┮粋€(gè)接口規(guī)范而已。”老C解釋。
“那么為什么它的析構(gòu)函數(shù)是protected的呢？”小P問(wèn)。
“哦，這是一個(gè)習(xí)慣用法。一般的抽象類的析構(gòu)函數(shù)要么是public virtual的，要么是protected
非virtual的。我在這里將它設(shè)計(jì)為protected
非virtual是因?yàn)槲也幌胱孖terator動(dòng)態(tài)生成，就是說(shuō)不希望Iterator的繼承類的對(duì)象是在堆上創(chuàng)建的。”看到小P還是有些莫名其妙，老
C接著說(shuō)，“關(guān)于這個(gè)小技巧，我會(huì)在后面一段時(shí)間……一個(gè)月后吧……跟一些其他的小技巧一起總結(jié)一下，在這里你就先將就著看吧。”
“也好……”小P槑。
“接下來(lái)的代碼……很傻很天真……”老C解釋道，“因?yàn)樵谶@里只是說(shuō)明問(wèn)題而已，你可不要學(xué)習(xí)這種設(shè)計(jì)啊。”
class ValueType
{
friend std::ostream& operator<<(std::ostream& os, const ValueType& value);
public:
virtual ~ValueType() {}
virtual bool operator==(const ValueType& rhs) const = 0;
virtual void print(std::ostream& os) const = 0;
};
std:: ostream& operator<<(std::ostream& os, const ValueType& valueType)
{
valueType.print(os);
return os;
}
“因?yàn)槲覀儧](méi)有辦法在系統(tǒng)定義類型——比如int——與用戶定義類型——比如Student——間保持一致，而我們又希望對(duì)于int數(shù)組和Student
數(shù)組都可以使用find()函數(shù)……不得以，我設(shè)計(jì)了一個(gè)叫做ValueType的傻傻基類，并將int用IntValueType類包裹了一下，使得類
似int這種系統(tǒng)定義類型也可以加入到我們的組織當(dāng)中。”老C解釋，“為了便于屏幕輸出，我還重載了ostream的輸出函數(shù)。”他撓撓頭，“最后我又畫
蛇添足的寫了一個(gè)Container的基類，用于存放我們的數(shù)據(jù)結(jié)構(gòu)。其實(shí)它什么也沒(méi)有做，只是為了統(tǒng)一下類型而已。”
class Container
{
public:
virtual ~Container() {}
};
“最后我們把這些接口放入一個(gè)文件當(dāng)中。”老C新建了一個(gè)頭文件，將類的定義放入其中。
iterator.h:
#if !defined(ITERATOR_H_)
#define ITERATOR_H_
#include <iostream>
class Iterator;
class Container;
class ValueType;
//////////////////////////////////////////////////////////////////////////
// Base classes.
//
class Iterator
{
public:
virtual Iterator& operator++() = 0;
virtual ValueType& operator*() = 0;
virtual bool operator==(Iterator& rhs) = 0;
virtual bool operator!=(Iterator& rhs) = 0;
protected:
~Iterator() {}
};
class Container
{
public:
virtual ~Container() {}
};
class ValueType
{
friend std::ostream& operator<<(std::ostream& os, const ValueType& value);
public:
virtual ~ValueType() {}
virtual bool operator==(const ValueType& rhs) const = 0;
virtual void print(std::ostream& os) const = 0;
};
std:: ostream& operator<<(std::ostream& os, const ValueType& valueType)
{
valueType.print(os);
return os;
}
#endif // ITERATOR_H_
“下來(lái)又是一些天真的實(shí)現(xiàn)代碼，”老C不好意思的撓頭，“就先作為說(shuō)明示例代碼吧，等我們掌握了更多的知識(shí)后再來(lái)修改這些代碼吧。”
implement.h:
#if !defined(IMPL_H_)
#define IMPL_H_
#include "iterator.h"
#include <cassert>
#include <typeinfo>
//////////////////////////////////////////////////////////////////////////
// Derived classes.
//
// IntVector.
//
class IntValueType : public ValueType
{
public:
IntValueType(int content = 0) : content_(content) {}
virtual bool operator==(const ValueType& rhs) const
{
try
{
const IntValueType& intValue = dynamic_cast<const IntValueType&>(rhs);
return content_ == intValue.content_;
}
catch (std::bad_cast e)
{
std::cout << "Bad cast, this object is not of type IntValue! " << std::endl;
return false;
}
}
virtual void print(std::ostream& os) const
{
os << content_;
}
private:
int content_;
};
class IntVectorIter : public Iterator
{
public:
IntVectorIter(IntValueType* ptr = 0) : ptr_(ptr) {}
virtual Iterator& operator++()
{
++ptr_;
return *this;
}
virtual ValueType& operator*()
{
return *ptr_;
}
virtual bool operator==(Iterator& rhs)
{
try
{
IntVectorIter& intIter = dynamic_cast<IntVectorIter&>(rhs);
return ptr_ == intIter.ptr_;
}
catch (std::bad_cast e)
{
std::cout << "Bad cast, this object is not of type IntVectorIter! " << std::endl;
return false;
}
}
virtual bool operator!=(Iterator& rhs)
{
return !(operator==(rhs));
}
private:
IntValueType* ptr_;
};
class IntVector : public Container
{
public:
IntVector(IntValueType* first, IntValueType* last)
: size_(0), array_(0)
{
size_ = last - first;
assert(size_ > 0);
array_ = new IntValueType[size_];
for (size_t i = 0; i < size_; ++i)
{
*(array_ + i) = *(first + i);
}
}
~IntVector()
{
if (array_)
{
delete[] array_;
array_ = 0;
}
size_ = 0;
}
virtual IntValueType* begin()
{
return &array_[0];
}
virtual IntValueType* end()
{
return &array_[size_];
}
private:
size_t size_;
IntValueType* array_;
};
//
// IntList
//
struct IntNode
{
IntNode* prev_;
IntNode* next_;
IntValueType content_;
};
class IntListIter : public Iterator
{
public:
IntListIter(IntNode* intNode = 0) : nodePtr_(intNode) {}
virtual Iterator& operator++()
{
nodePtr_ = nodePtr_->next_;
return *this;
}
virtual ValueType& operator*()
{
return nodePtr_->content_;
}
virtual bool operator==(Iterator& rhs)
{
try
{
IntListIter& it = dynamic_cast<IntListIter&>(rhs);
return nodePtr_ == it.nodePtr_;
}
catch (std::bad_cast e)
{
std::cout << "Bad cast, this object is not of type IntListIter! " << std::endl;
return false;
}
}
virtual bool operator!=(Iterator& rhs)
{
return !(operator==(rhs));
}
private:
IntNode* nodePtr_;
};
class IntList : public Container
{
public:
IntList(IntValueType* first, IntValueType* last)
: size_(0), list_(0)
{
size_ = last - first;
assert(size_ > 0);
list_ = new IntNode;
list_->prev_ = list_;
list_->next_ = list_;
for (size_t i = 0; i < size_; ++i)
{
IntNode* newNode = new IntNode;
newNode->content_ = *(first + i);
newNode->next_ = list_;
newNode->prev_ = list_->prev_;
newNode->prev_->next_ = newNode;
newNode->next_->prev_ = newNode;
}
}
~IntList()
{
while (list_->next_ != list_)
{
IntNode* it = list_->next_;
it->prev_->next_ = it->next_;
it->next_->prev_ = it->prev_;
it->prev_ = 0;
it->next_ = 0;
it->content_ = 0;
delete it;
it = 0;
}
list_->prev_ = 0;
list_->next_ = 0;
delete list_;
list_ = 0;
size_ = 0;
}
virtual IntNode* begin()
{
return list_->next_;
}
virtual IntNode* end()
{
return list_;
}
private:
size_t size_;
IntNode* list_;
};
#endif // IMPL_H_
“因?yàn)椴幌攵鄤?dòng)腦筋，所以代碼中充滿了轉(zhuǎn)型，這些都是不良的設(shè)計(jì)。你大概明白一下iterator模式的思想就可以了，以后我們還會(huì)優(yōu)化這些代碼的。”老C說(shuō)道，“不用太關(guān)注代碼的細(xì)節(jié)，只要知道我們通過(guò)運(yùn)算符重載保證了用戶代碼的簡(jiǎn)單明了就達(dá)到目的了。”
“唔，我看看先……”小P回答。他問(wèn)了幾個(gè)代碼中的問(wèn)題，想了想，說(shuō)，“看來(lái)iterator模式就是將對(duì)container中元素的操作與container本身分開(kāi)，這樣就可以達(dá)到復(fù)用某些算法的目的？”
“呵呵，差不多就是這樣啦。”老C回答，“要看懂這些古怪的代碼，還有一些細(xì)節(jié)需要了解，但是我們不要過(guò)于糾纏到細(xì)節(jié)當(dāng)中，先從整體上把握一下就可以了。
這些細(xì)節(jié)問(wèn)題，當(dāng)然需要重視，但是不是現(xiàn)在。等我們接觸的代碼再多一些，我們?cè)倩仡^看看這些細(xì)節(jié)問(wèn)題吧。”他揉揉手指，“看，這下find()函數(shù)即可以
在vector上使用，也可以在list上使用了吧；而且對(duì)于container數(shù)據(jù)的操作也方便了一些。代價(jià)是我們?cè)谀缓箅s七雜八的搞了一些小動(dòng)作。”
老C伸了一個(gè)懶腰，“等我們掌握了足夠的細(xì)節(jié)，再回來(lái)修改這些代碼吧，先用面向?qū)ο蟮姆椒ǎ儆媚０宓姆椒ā贿^(guò)現(xiàn)在談?wù)撨@些兒還太早，有害無(wú)益，我們
還是先不要太激進(jìn)的好。”
“哦？好吧，”小P覺(jué)得自己越來(lái)越好奇了，“還有面向?qū)ο蠛湍０宓姆椒ò。?#8221;
“是啊是啊，這些我們以后慢慢說(shuō)……”老C心想一次都搞光了，以后晚飯就沒(méi)有人請(qǐng)客了。
“呵呵，好啊好啊。不過(guò)這些代碼我還是要再看看，你給我傳一下吧……”小P道。
“唉，現(xiàn)在不要糾纏在這些代碼上啦，我們還是要平衡一下……”老C回答，“不過(guò)我還是把這些代碼放到服務(wù)器上，你用ftp下載吧。”
“好啊，”小P道，“你說(shuō)不用糾纏在這些代碼的細(xì)節(jié)上，那么接下來(lái)我們要討論一些什么內(nèi)容呢？”
“……”老C深沉了一會(huì)，“接下來(lái)我們要討論——數(shù)學(xué)。”
“數(shù)學(xué)？”小P奇道。
“唔，”老C點(diǎn)頭，“我們編碼就像練功，語(yǔ)言啊，代碼結(jié)構(gòu)啊，風(fēng)格啊什么的就是外功；而解決問(wèn)題的方法就是內(nèi)功——內(nèi)功需要一定的專業(yè)知識(shí)和數(shù)學(xué)功底。無(wú)
論內(nèi)外功都是要修煉的……否則哪怕你程序的結(jié)構(gòu)再好，風(fēng)格再優(yōu)美，但是你無(wú)法解決稍微復(fù)雜一些的實(shí)際問(wèn)題——那么一切也是白搭。”
“是啊，也對(duì)。”小P贊同。“那么需要討論些什么內(nèi)容呢？”
“呵呵，也不會(huì)很復(fù)雜，只是一些基本的分析問(wèn)題，解決問(wèn)題的基本思路而已。”老C說(shuō)道，“你的數(shù)學(xué)還是不錯(cuò)的，等到融會(huì)貫通了，對(duì)你來(lái)說(shuō)小菜而已。”老C
想想，“其實(shí)不僅僅是數(shù)學(xué)，我們還可以順便討論一些信號(hào)、電路和自控方面的問(wèn)題。因?yàn)榫幊桃欢ㄒ陧?xiàng)目中進(jìn)行，在項(xiàng)目中學(xué)習(xí)得是最快的。等到掌握的知識(shí)細(xì)
節(jié)足夠豐富的時(shí)候，我想我們可以開(kāi)始做一些小工程了。”
“好啊，沒(méi)有問(wèn)題！”小P點(diǎn)頭。
“但是我們?cè)陂_(kāi)始小的工程之前先要簡(jiǎn)單的討論一下遞歸和有限狀態(tài)機(jī)。”老C說(shuō)，“這些東東用C++的基于對(duì)象的部分完全可以應(yīng)付。不過(guò)……”他打了一個(gè)哈欠。
“嗯，時(shí)候也不早了，我們還是先閃人吧！”小P拾趣的說(shuō)道。
兩個(gè)人跑到隔壁，叫上大部隊(duì)，一邊談?wù)撟罱陌素允录贿呄虼箝T晃去……
(遞歸？和遞推公式有關(guān)嗎？)