“感觉这一家有做大的趋势……”老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拾趣的说道。
两个人跑到隔壁，叫上大部队，一边谈论最近的八卦事件一边向大门晃去……
(递归？和递推公式有关吗？)