/*
从一个简单的实例开始:对考试结果进行统计分析(及格率)
int main(int argc, char *argv[])
{
float scores[STUDENT_COUNT];
int passed = 0;
//initialize scores here...
for (int i = 0; i != STUDENT_COUNT; i++)
{
if (scores[i] >= 60)
{
passed++;
}
}
cout << "passed rate=" << (float)passed/STUDENT_COUNT << endl;
return EXIT_SUCCESS;
}
责任分解:把分析单独作为一个功能
void analyze(float *scores, int student_count)
{
int passed = 0;
for (int i = 0; i != student_count; i++)
{
if (scores[i] >= 60)
passed++;
}
cout << "passing rate = " << (float)passed / student_count << endl;
}
备注:以上传进去的参数是指针,是否可以使用链表代替数组?
如果成绩用单项非循环链表呢?
struct Student
{
float score;
Student* next;
};
//..
Student *head;
//如果成绩用单项非循环链表存储?
void analyze(Student *scores)
{
int passed = 0, count = 0;
for (Student *p = scores; p != NULL; p = p->next)
{
if (p->score >= 60)
passed++;
count++;
}
cout << "passing rate=" << (float)passed/count << endl;
}
//遍历:变与不变
//需要遍历所有学生的成绩(不变),不希望绑定在某种存储方式下(变)
//分离变与不变(存储)与不变(访问)
//把“访问”设计为一个接口,针对不同的存储完成这个接口的不同的实现
for (int i = 0; i != STUDENT_COUNT; i++)
{
//access item by p
}
for (Student *p = scores; p != NULL; p = p->next)
{
//access item by p
}
迭代器:把访问设计成为一个接口
class Iterator
{
public:
virtual ~Iterator() {}
virtual bool operator!=(const Iterator &other) const = 0;
virtual const Iterator& operator++() = 0;
virtual const Iterator& operator++(int) = 0;
virtual float& operator*() const = 0;
virtual float* operator->() const = 0;
bool operator==(const Iterator &other) const
{
return !(*this != other);
}
};
使用迭代器作为参数传递
void analyze(Iterator *begin, Iterator* end)
{
int passed = 0, count = 0;
for (Iterator* p = begin; *p != *end; (*p)++)
{
if (**p >=60)
passed++;
count++;
}
cout << "passing rate" << (float)passed/count << endl;
}
//需要给存储对象一个约束:能够返回代表头部和尾部的迭代器
//使用“左边闭右开区间,即[begin,end)
class Collection
{
public:
virtual ~Collection() {}
virtual Iterator* begin() const = 0;
virtual Iterator* end() const = 0;
virtual int size() = 0;
};
int main(int argc, char *argv[])
{
Collection *collection;
//initialize collection here...
analyze(collection->begin(), collection->end());
}
//实现基于数组的集合Collection
class ArrayCollection:public Collection
{
friend class ArrayIterator;
float *_data;
int _size;
public:
ArrayCollection():_size(10){_data = new float0[_size];}
ArrayCollection(int size,float* data):_size(size)
{
_data = new float[_size];
for (int i = 0; i < size; i++)
*(_data+i) = *(data+i);
}
~ArrayCollection() {delete[] _data;}
int size() {return _size;}
Iterator* begin() const;
Iterator* end() const;
};
Iterator* ArrayCollection::begin() const
{
return new ArrayIterator(_data,0);
}
Iterator* ArrayCollection::end() const
{
return new ArrayIterator(_data,_size);
}
//实现基于数组的迭代器Iterator
class ArrayIterator:public Iterator
{
float *_data;
int _index;
public:
ArrayIterator(float *data,int index):_data(data),_index(index)
{}
ArrayIterator(const ArrayIterator& other):_data(other._data),_index(other._index)
{}
~ArrayIterator(){}
const Iterator& operator++();
const Iterator& operator++(int);
float& operator*() const;
float* operator->() const;
bool operator!=(const Iterator &other) const;
};
const Iterator& ArrayIterator::operator++()
{
_index++;
return *this;
}
const Iterator& ArrayIterator::operator(int)
{
_index++;
return ArrayIterator(_data,_index - 1);
}
float& ArrayIterator::operator*() const
{
return *(_data + _index);
}
float* ArrayIterator::operator->() const
{
return (_data + _index);
}
bool ArrayIterator::operator!=(const Iterator &other) const
{
return (_data != ((ArrayIterator*)(&other))->data ||
_index != ((ArrayIterator*)(&other))->_index);
}
analyze() &main()
void analyze(Iterator* begin, Iterator* end)
{
int passed = 0, count = 0;
for (Iterator* p = begin; *p != *end; (*p)++)
{
if (**p >= 60)
passed++;
count++;
}
cout << "passing rate=" << (float)passed/count << endl;
}
int main(int argc, char **argv[])
{
float scores[] = {90,20,40,40,20,60,70,30,90,100};
Collection *collection = new ArrayCollection(10,scores);
analyze(collection->begin(), collection->end());
system("PAUSE");
return EXIT_SUCCESS;
}
//总结:迭代器模式
//提供一种方法顺序访问一个聚合对象中各个元素,而又不需要暴露该对象的内部表示,与对象的内部表示无关(数组还是链表)
//
for (Iterator p = begin; p != end; p++)
{
//do something with object *p;
}
//另一种常见的迭代器模式
Iterator it = collection.iterator();
while(it.hasNext())
{
Object object = it.next();
//do something with object;
}
变与不变
不变
产生迭代器的方法不变
迭代器遍历集合的接口不变
变:
集合的存储方式可变
迭代器遍历集合的具体实现可变
实现了遍历与存储方法的隔离;
更进一步:把analyze看做一个算法,我们实现了算法和数据存储的隔离
算法--迭代器--数据表示
算法的通用化
设计一系列通用算法
max,min,sort,count,count_if,find...
模板:在编写代码时候留出一些可变的部分(类型),这些部分在使用前必须作出指明,这样,我们就可以使用通用的
算法和数据结构,然后再在使用时予以实例化;
使用模板技术实现泛型;
通用算法:
template <class _iterator>
void analyze(_iterator begin,_iterator end)
{
int passed = 0, count = 0;
for (_iterator p = begin; p != end; p++)
{
if (*p >= 60)
passed++;
//...
}
}
数组容器与迭代器
template <class T>
class ArrayCollection
{
T* _data;
int _size;
public:
ArrayCollection():_size(10){_data = new T[_size];}
ArrayCollection(int size):_size(size){_data = new T[_size];}
ArrayCollection(int size,T* data):_size(size)
{
_data = new T[_size];
for (int i = 0; i < size; i++)
{
*(_data + i) = *(data + i);
}
}
~ArrayCollection() {delete[] _data;}
T* begin() {return _data;}
T* end() {return (_data + _size);}
};
链表与其迭代器
template <class T>
struct LinkedListNode
{
T _data;
LinkedListNode *next;
LinkedListNode():next(NULL){}
LinkedListNode(T data):_data(data),next(NULL){}
};
template <class T>
struct LinkedListIterator{
LinkedListNode<T> *pointer;
LinkedListIterator(LinkedListNode<T> *p):pointer(p){}
LinkedListIterator(const LinkedListIterator<T>& it):pointer(it.pointer){}
LinkedListIterator<T>& operator++()
{
pointer = pointer->next;
return *this;
}
const LinkedListIterator<T> operator++(int)
{
LinkedListIterator<T> temp = *this;
pointer = pointer->next;
return temp;
}
T& operator*() const { return pointer->_data;}
T& operator->() const { return &(pointer->_data);}
bool operator!=(const LinkedListIterator<T> &other)
{
return pointer != other.pointer;
}
bool operator==(const LinkedListIterator<T> &other)
{
return pointer == other.pointer;
}
};
链表容器
template <class T>
class LinkedListCollection
{
LinkedListNode<T>* _head;
public:
LinkedListIterator<T> begin() {return LinkedListIterator<T>(_head);}
LinkedListIterator<T> end() {return LinkedListIterator<T>(NULL);}
LinkedListCollection():_head(NULL){}
LinkedListCollection(in size, T* data)
{
//...
}
~LinkedListCollection()
{
//...
}
};
使用算法与迭代器
int main(int argc, char *argv[])
{
float scores[] = {90,....};
ArrayCollection<float> collection2(10,scores);
LinkCollection<float> collection1(10,scores);
analyze(scores,scores + 10);
analyze(collection1.begin(),collection1.end());
analyze(collection2.begin(),collection2.end());
system("PAUSE");
return EXIT_SUCCESS;
}
新的类型
考试三科都要高于60分,怎么办?
struct Score
{
float value[3];
Score(){}
Score(float f1,float f2,float f3)
{
value[0] = f1;
value[1] = f2;
value[2] = f3;
}
Score& operator=(const Score& s)
{
value[0] = s.value[0];
value[1] = s.value[1];
value[2] = s.value[2];
return *this;
}
bool operator>=(float pass)
{
return (value[0] >= pass && value[1] >= pass && value[2] >= pass);
}
};
ostream& operator<<(ostream& out, const Score& s)
{
out << "{" << s.value[0] << "," << s.value[1] << "," << s.value[2] << "}";
return out;
}
适应新的类型
int main(int argc, char *argv[])
{
Score sarray[3];
sarray[0] = Score(60,60,60);
sarray[1] = Score(70,70,70);
sarray[2] = Score(90,80,80);
ArrayCollection<Score> collection3(3,sarray);
LinkCollection<Score> collection4(3,sarray);
analyze(collection3.begin(),collection3.end());
analyze(collection4.begin(),collection4.end());
system("PAUSE");
return EXIT_SUCCESS;
}
算法实际上与“可用的操作相关”,与具体的数据类型无关;
抽象结构和类模板
除了抽象算法外,还有抽象结构:Stack,Linked list,Vector...
这些抽象结构与存储什么数据没有关系,只与数据的存储方式和访问方式相关;
可以借助类模板实现:
template <class T>
struct LinkNode
{
T _data;
LinkNode *_next;
LinkNode():_next(NULL){}
LinkNode(T data):_data(data),_next(NULL){}
LinkNode(T data,T* next):_data(data),_next(next){}
};
template <class T>
class LinkedListCollection
{
LinkedListNode<T>* _head;
public:
LinkedListCollection():_head(NULL){}
~LinkedListCollection(){clear();}
bool empty(){return (_head == NULL);}
void addFirst(const T& data) {_head = new LinkedListNode<T>(data,_head);}
bool removeFirst() {
if (_head != NULL)
{
LinkedListNode<T>* p = _head;
_head = _head->_next;
delete p;
return true;
}
else
return false;
}
}
T* getFirst() { return (_head != NULL) ? &(_head->_data) : NULL;}
LinkedListNode<T>* lastNode()
{
LinkedListNode<T>* p;
for (p = _head; p->_next != NULL; p = p->_next);
return p;
}
void addLast(const T& data)
{
if (_head != NULL)
lastNode()->_next = new LinkedListNode<T>(data);
else
_head = new LinkedListNode<T>(data);
}
T* getLast() { return (_head != NULL) ? &(_lastNode()->_data : NULL);}
bool removeLast()
{
if (_head != NULL)
{
if (_head->_next != NULL)
{
LinkedListNode<T>* p;
for (p = _head; p->_next->_next != NULL; p = p->_next);
delete p->_next;
p->_next = NULL;
return true;
}
else
{
delete _head;
_head = NULL;
return true;
}
}
else
{
return false;
}
}
void clear()
{
while(removeFirst());
}
LinkedListIterator<T> begin() {return LinkedListIterator<T>(_head);}
LinkedListIterator<T> end() {return LinkedListIterator<T>(NULL);}
内联函数:
inline int min(int a, int b) { return (a>b) ? a:b;}
作用:函数内联展开,避免函数调用开销用空间换时间;
在类定义体内定义(实现)的函数缺省为内联函数;
通过模板实例化使用Linked List(抽象结构)
int main(int argc, char *argv[])
{
LinkedListCollection<Score> collection4;
for (int i = 0; i < 3; i++)
collection4.addFirst(sarray[i]);
analyze(collection4.begin(),collection4.end());
//....
return EXIT_SUCCESS;
}
备注:
不变:算法和抽象结构的接口与实现不变,数据的访问接口不变(迭代器),数据的可用操作不变(操作符重载);
数据的组织形式可变,数据的类型可变;
实现“算法/抽象结构”与数据表示之间的分离;
泛型编程:先实现算法,再充实数据表示(类型);
假设算法继续变化
某些科目的及格线不是60分
template<class _iterator> void analyze(_iterator begin,_iterator end)
{
int passed = 0, count = 0;
for (_iterator p = begin; p != end; p++)
{
if(*p >= 60)
passed++;
count++;
}
cout << "passing rate= " << (float)passed / count << endl;
}
使用函数指针把判断及格的这个函数传递进去
template <class _iterator>
void analyze(_iterator begin, _iterator end, bool (*isPass)(const _iterator&))
{
int passed = 0, count = 0;
for (_iterator p = begin; p != end; p++)
{
if(isPass(p))
{
passed++;
}
count++;
}
}
使用函数指针判断及格函数
template <class _Iterator> bool isPass(const _Iterator& p)
{
return (p->value[0] >= 70 && p->value[1] >= 60 && p->value[2] >= 60);
}//注意这个函数的实现是有缺陷的,只适用于Score类型
int main(int argc, char *argv[])
{
//...
analyze(sarray,sarray + 3,isPass<Score *>);//???
analyze(collection3.begin,collection3.end(),isPass<Score *>);//???
analyze(collection4.begin,collection4.end(),isPass<LinkedListIterator<Score> >);//????
//...
}
继续解耦
这两个函数有什么不同吗?
template <class _Iterator> bool isPass(const _Iterator& p)
{
return (p->value[0] >= 60
&& p->value[1] >= 60 && p->value[2] >= 60);
}
template <class _Iterator> bool isPass(const _Iterator& p)
{
return (p->value[0] >= 70
&& p->value[1] >= 60 && p->value[2] >= 60);
}
如果及格线能够被记住呢?
Score pass(70,60,60);
template <class _Iterator> bool isPass(const _Iterator& p)
{
return (p->value[0] >= pass.value[0] &&
p->value[1] >= pass.value[1] &&
p->value[2] >= pass.value[2]);
}
文件也可以作为函数“记住”数据的另外一种手段
Score pass(70,60,60);
template <class _Iterator>
bool isPass(const _Iterator& p)
{
float pass1, pass2, pass3;
ifstream is("passScore.txt");
is >> pass1 >> pass2 >> pass3;
return (p->value[0] >= pass1 && p->value[1] >= pass2 && p->value[2] >= pass3);
}
这样的话通过修改passScore.text文件可以轻松地修改及格的分数线;
单一实例的问题依然存在;
问题在于函数是死的:数据 + 函数 = 对象 函数 + 数据 = 对象
函数调用==()操作符,还原()操作符的本意,操作符重载;
函数对象:
通过对函数运算符的重载,我们可以赋予一个对象“函数”的特性,能被调用
template <class _iterator,class T>
class IsPass{
T _pass;
public:
IsPass(const T& pass):_pass(pass){}
bool operator() (const _iterator& p)
{
return (*p >= _pass);
}
};
IsPass就是一个函数对象类模板
算法的定义:
template <class _iterator , class T>
void analyze(_iterator begin, _iterator end, IsPass<_iterator,T> isPass)
{
int passed = 0, count = 0;
for (_iterator p = begin; p != end; p++)
if (isPass(p))
passed++;
count++;
}
使用函数对象
int main(int argc, char *argv[])
{
//...
sarray[0] = Score(60,60,70);
sarray[1] = Score(60,60,70);
sarray[2] = Score(60,60,70);
ArrayCollection<Score> collection3(3,sarray);
LinkedListCollection<Score> collection4;
//....
analyze(sarray,sarray + 3 ,IsPass<Score*, Score> (Score(70,60,60)));
analyze(collection3.begin(),collection3.end(),IsPass<Score*,Score>(Score(50,60,60)));
analyze(collection4.begin(),collection4.end(),IsPass<LinkedListIterator<Score>, Score>(Score(60,60,60)));
}
*/