“感覺這一家有做大的趨勢……”老C一邊喝茶消食一邊對小P發表自己的看法。
“的確，他家已經把旁邊的店生意快搶光了，估計過一些時間就會把隔壁的店買下來了。”小P亦有同感，“怪不得最近食堂的刀削面師傅辭工，可能創業去了……”
“？是么？呵呵，也許吧。”老C笑道，“不過看在你請客的面子上，我決定和你多聊幾句……”
“哦，是的是的。你要告訴我如何更好的實現線性表。”小P接道。
“嘻嘻，是的是的。不過這次我要先寫一段代碼……”老C說道。
“……是啊……”小P于是很自覺的將白板擦干凈，并拉到兩人面前。
“我們現在的題目是，寫一個函數，作用是在一個線性表中查找某一個特定元素。”老C說道，“我們先從數組開始，這樣比較簡單。”
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)表示需要查找的區間，如果找到就返回元素的指針，否則返回last。”老C解釋，“為了更清楚的表明此函數所在的應用環
境，我們再來一段使用它的代碼。”
#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()函數就是這樣被使用的。”老C說道，“同時我要提醒一下你，數組類型與指針類型是不同的類型，因為數組類型還帶有數組長度的信息。比如
int a[2] 與 int* a，這是兩種類型，其中int a[]可以被內部轉型為int*
，但是反之則不行。可惜的是數組類型無法作為函數參數，在使用函數對數組進行操作的時候不得不將其轉型為指針……這個就是C中的數組降維問題……總之你要
明白，數組與指針是不同的類型，但數組可以被轉型為指針——代價是丟失長度信息——反之則不行。”
“好，我了解了。”小P回答，心想好像在哪本書上說過貌似數組和指針沒有什么區別的。為了確認這個事情，他決定再google一下。
“喏，如果我們使用了[first,
last)的表達形式，很多對線性表的操作就可以統一起來，這樣我們將指向線性表元素的指針提取出來，就使得用戶使用這些線性表就好像在使用一個數組似
的。這樣會大大減輕用戶記憶的難度，同時也使得編程人員避免了很多下意識的錯誤——比如過一錯誤。”老C說道，“而這個被提煉出來的指針，我們就叫它
iterator。”
“是么？”小P道，“原來iterator就是這樣來的啊。”
“剛才的例子是trivial的，我們再深入一點點。”老C說道，“如果我們希望find()函數可以被運用到所有類型的線性表，那么可以怎么做呢？”看
到小P有些槑，老C自問自答，“其實方法有很多，我們可以將find()看成對象——一切皆為對象——如果使用面向對象的方法，然后提煉出一個find
類，讓findVector和findList成為它的子類，find類中的操作寫為虛函數，然后讓findVector子類和findList子類去修
改這些虛函數以滿足自己的實際需要，這可以被稱為strategy模式的一個簡單應用。但是這個方法我們先避開不談，在這里我們采用另外一個方法。”他找
到茶杯喝了一口，“我們將這個iterator提煉為一個類，同時保持find()函數的實現不變，然后在這個iterator上動腦筋。”
“那么應當怎么做呢？”小P問道。
“嗯，如果find()函數的代碼不變，那么我們可以這么做。”老C說著打開了電腦，新建立了一個工程開始敲鍵盤，一邊敲一邊給小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()函數可以是這樣的一種接口和實現。”老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;
}
“在這里我們假設find()函數即可以用在vector上，也可以用在linked list上，橋梁就是Iterator類。”老C解釋道，“這下我們就可以根據find()函數的實現看看我們需要什么樣子的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() {}
};
“根據find()函數的實現，我們知道Iteratro類必須擁有上面列出的接口。在這里我把Iterator類設計為抽象類，因為它只是提供一個接口規范而已。”老C解釋。
“那么為什么它的析構函數是protected的呢？”小P問。
“哦，這是一個習慣用法。一般的抽象類的析構函數要么是public virtual的，要么是protected
非virtual的。我在這里將它設計為protected
非virtual是因為我不想讓Iterator動態生成，就是說不希望Iterator的繼承類的對象是在堆上創建的。”看到小P還是有些莫名其妙，老
C接著說，“關于這個小技巧，我會在后面一段時間……一個月后吧……跟一些其他的小技巧一起總結一下，在這里你就先將就著看吧。”
“也好……”小P槑。
“接下來的代碼……很傻很天真……”老C解釋道，“因為在這里只是說明問題而已，你可不要學習這種設計啊。”
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;
}
“因為我們沒有辦法在系統定義類型——比如int——與用戶定義類型——比如Student——間保持一致，而我們又希望對于int數組和Student
數組都可以使用find()函數……不得以，我設計了一個叫做ValueType的傻傻基類，并將int用IntValueType類包裹了一下，使得類
似int這種系統定義類型也可以加入到我們的組織當中。”老C解釋，“為了便于屏幕輸出，我還重載了ostream的輸出函數。”他撓撓頭，“最后我又畫
蛇添足的寫了一個Container的基類，用于存放我們的數據結構。其實它什么也沒有做，只是為了統一下類型而已。”
class Container
{
public:
virtual ~Container() {}
};
“最后我們把這些接口放入一個文件當中。”老C新建了一個頭文件，將類的定義放入其中。
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_
“下來又是一些天真的實現代碼，”老C不好意思的撓頭，“就先作為說明示例代碼吧，等我們掌握了更多的知識后再來修改這些代碼吧。”
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_
“因為不想多動腦筋，所以代碼中充滿了轉型，這些都是不良的設計。你大概明白一下iterator模式的思想就可以了，以后我們還會優化這些代碼的。”老C說道，“不用太關注代碼的細節，只要知道我們通過運算符重載保證了用戶代碼的簡單明了就達到目的了。”
“唔，我看看先……”小P回答。他問了幾個代碼中的問題，想了想，說，“看來iterator模式就是將對container中元素的操作與container本身分開，這樣就可以達到復用某些算法的目的？”
“呵呵，差不多就是這樣啦。”老C回答，“要看懂這些古怪的代碼，還有一些細節需要了解，但是我們不要過于糾纏到細節當中，先從整體上把握一下就可以了。
這些細節問題，當然需要重視，但是不是現在。等我們接觸的代碼再多一些，我們再回頭看看這些細節問題吧。”他揉揉手指，“看，這下find()函數即可以
在vector上使用，也可以在list上使用了吧；而且對于container數據的操作也方便了一些。代價是我們在幕后雜七雜八的搞了一些小動作。”
老C伸了一個懶腰，“等我們掌握了足夠的細節，再回來修改這些代碼吧，先用面向對象的方法，再用模板的方法——不過現在談論這些兒還太早，有害無益，我們
還是先不要太激進的好。”
“哦？好吧，”小P覺得自己越來越好奇了，“還有面向對象和模板的方法啊？”
“是啊是啊，這些我們以后慢慢說……”老C心想一次都搞光了，以后晚飯就沒有人請客了。
“呵呵，好啊好啊。不過這些代碼我還是要再看看，你給我傳一下吧……”小P道。
“唉，現在不要糾纏在這些代碼上啦，我們還是要平衡一下……”老C回答，“不過我還是把這些代碼放到服務器上，你用ftp下載吧。”
“好啊，”小P道，“你說不用糾纏在這些代碼的細節上，那么接下來我們要討論一些什么內容呢？”
“……”老C深沉了一會，“接下來我們要討論——數學。”
“數學？”小P奇道。
“唔，”老C點頭，“我們編碼就像練功，語言啊，代碼結構啊，風格啊什么的就是外功；而解決問題的方法就是內功——內功需要一定的專業知識和數學功底。無
論內外功都是要修煉的……否則哪怕你程序的結構再好，風格再優美，但是你無法解決稍微復雜一些的實際問題——那么一切也是白搭。”
“是啊，也對。”小P贊同。“那么需要討論些什么內容呢？”
“呵呵，也不會很復雜，只是一些基本的分析問題，解決問題的基本思路而已。”老C說道，“你的數學還是不錯的，等到融會貫通了，對你來說小菜而已。”老C
想想，“其實不僅僅是數學，我們還可以順便討論一些信號、電路和自控方面的問題。因為編程一定要在項目中進行，在項目中學習得是最快的。等到掌握的知識細
節足夠豐富的時候，我想我們可以開始做一些小工程了。”
“好啊，沒有問題！”小P點頭。
“但是我們在開始小的工程之前先要簡單的討論一下遞歸和有限狀態機。”老C說，“這些東東用C++的基于對象的部分完全可以應付。不過……”他打了一個哈欠。
“嗯，時候也不早了，我們還是先閃人吧！”小P拾趣的說道。
兩個人跑到隔壁，叫上大部隊，一邊談論最近的八卦事件一邊向大門晃去……
(遞歸？和遞推公式有關嗎？)