STL泛型编程与设计新思维

【 tulaoshi.com - 编程语言 】

　　前言
　　
　　永远记住，编写代码的宗旨在于简单明了，不要使用语言中的冷僻特性，耍小聪明，重要的是编写你理解的代码，理解你编写的代码，这样你可能会做的更好。 
　　 　　　　--- Herb Sutter
　　
　　 !-- frame contents -- !-- /frame contents -- 　　1998年，国际C++标准正式通过，标准化对C++最重要的贡献是：对“强大的抽象概念”给于更有力的支持，以降低软件的复杂度，C++提供了二种功能强大的抽象方法：面向对象编程与泛型编程。面向对象编程大家一定很熟悉了，这里就不再哆嗦了。提到泛型编程(Generic Programming)，有的人可能还不太熟悉，但是提到STL，你就一定会有所耳闻了。STL(Standard Template Library，标准模板库) 其实就是泛型编程的实现品，STL是由Alexander Stepanov(STL之父)、David R Musser和Meng Lee三位大师共同发展，于1994年被纳入C++标准程序库。STL虽然加入C++标准库的时间相对较晚，但它却是C++标准程序库中最具革命性的部分，同时也是C++标准程序库中最重要的组成部分。由于新的C++标准库中几乎每一样东西都是由模板(Template)构成的，当然，STL也不会例外。所以，在这里有必要先概要说明一下模板的有关概念。
　　
　　模板概念
　　
　　通过使用模板可以使程序具有更好的代码重用性。记住，模板是对源代码进行重用，而不是通过继续和组合重用对象代码，当用户使用模板时，参数由编译器来替换。模板由类模板和函数模板二部分组成，以所处理的数据类型的说明作为参数的类就叫类模板，而以所处理的数据类型的说明作为参数的函数叫做函数模板。模板参数可以由类型参数或非类型参数组成，类型参数可用class和typename要害字来指明，二者的意义相同，都表示后面的参数名代表一个潜在的内置或用户定义的类型，非类型参数由一个普通参数声明构成。下面是类模板和函数模板的简单用法：
　　
　　template＜class T1, int Size＞
　　class Queue // 类模板，其中T1为类型参数，Size为非类型参数
　　{
　　public:
　　eXPlicit Queue():size_(Size){}; // 显式构造，避免隐式转换
　　……
　　template＜class T2＞ void assign(T2 first,T2 last); // 内嵌函数模板
　　private:
　　T* temp_;
　　int size_;
　　}
　　// 类模板中内嵌函数模板Compare的外围实现(如在Queue类外实现)
　　template＜class T1,int Size＞ template＜class T2＞
　　void Queue＜T1,Size＞::assign (T2 first,T2 last) {}; // 模板的使用方法
　　int ia[4] = {0,1,2,3};
　　Queue＜int, sizeof(ia)/sizeof(int)＞ qi;
　　qi.assign(ai,ai+4); 泛型编程
　　
　　泛型编程和面向对象编程不同，它并不要求你通过额外的间接层来调用函数，它让你编写完全一般化并可重复使用的算法，其效率与针对某特定数据类型而设计的算法相同。泛型编程的代表作品STL是一种高效、泛型、可交互操作的软件组件。 !-- frame contents -- !-- /frame contents -- 所谓泛型(Genericity)，是指具有在多种数据类型上皆可操作的含意，与模板有些相似。
　　
　　STL巨大，而且可以扩充，它包含很多计算机基本算法和数据结构，而且将算法与数据结构完全分离，其中算法是泛型的，不与任何特定数据结构或对象类型系在一起。STL以迭代器(Iterators)和容器(Containers)为基础，是一种泛型算法(Generic Algorithms)库，容器的存在使这些算法有东西可以操作。STL包含各种泛型算法(algorithms)、泛型指针(iterators)、泛型容器(containers)以及函数对象(function objects)。STL并非只是一些有用组件的集合，它是描述软件组件抽象需求条件的一个正规而有条理的架构。
　　
　　迭代器(Iterators)是STL的核心，它们是泛型指针，是一种指向其他对象(objects)的对象，迭代器能够遍历由对象所形成的区间(range)。迭代器让我们得以将容器(containers)与作用其上的算法(algorithms)分离，大多数的算法自身并不直接操作于容器上，而是操作于迭代器所形成的区间中。
　　
　　迭代器一般分为五种：Input Iterator、Output Iterator、Forward Iterator、Bidirections Iterator和Random Access Iterator。Input Iterator就象只从输入区间中读取数据一样，具有只读性，属于单向移动，如STL中的istream_iterator。
　　
　　Output Iterator刚好相反，只写出数据到输出区间中，具有只写性，属于单向移动，如STL中的ostream_iterator。Forward Iterator也属于单向移动，但不同之处是它同时具有数据读、写性。Bidirections Iterator如名称暗示，支持双向移动，不但可以累加(++)取得下一个元素，而且可以递减(--)取前一个元素，支持读、写性。Random Access Iterator功能最强，除了以上各迭代器的功能外，还支持随机元素访问(p+=n)，下标(p[n])、相减(p1-p2)及前后次序关系(p1＜p2)等。
　　
　　Input Iterator和Output Iterator属于同等最弱的二种迭代器，Forward Iterator是前二者功能的强化(refinement)，Bidirections Iterator又是Forward Iterator迭代器的强化，最后Random Access Iterator又是Bidirections Iterator迭代器的强化。如下简单示例展示Input Iterator、Forward Iterator、Bidirections Iterator和Radom Access Iterator迭代器的功能（其中input_iterator_tag等带tag字符串为各不同迭代器的专属标识）：
　　
　　1、InputIterator
　　
　　
　　 template＜class InputIterator, class Distance＞
　　void advance(InputIterator& i, Distance n, input_iterator_tag)
　　{
　　for(; n＞0; --n,++i){} // InputIterator具有++性
　　}
　　2、ForwardIterator
　　
　　template＜class ForwardIterator, class Distance＞
　　void advance(ForwardIterator& i, Distance n,forward_iterator_tag)
　　{
　　advance(i, n, input_iterator_tag());
　　}
　　3、BidirectionalIterator
　　
　　template＜class BidirectionalIterator, class Distance＞
　　void advance(BidirectionalIterator& i, Distance n, bidirectional_iterator_tag)
　　{
　　if(n＞=0) // 具有++、--性
　　for(; n＞0; --n,++i){}
　　else
　　for(; n＞0; ++n,--i){}
　　}
　　4、RandomAccessIterator
　　
　　template＜class RandomAccessIterator, class Distance＞
　　void advance(RandomAccessIterator& i, Distance n, random_access_iterator_tag)
　　{
　　i += n; // 具有++、--、+=等性
　　} 函数对象(Function object)也称仿函数(Functor)，是一种能以一般函数调用语法来调用的对象，函数指针(Function pointer)是一种函数对象，所有具有operator()操作符重载的成员函数也是函数对象。函数对象一般分为无参函数(Generator)，单参函数(Unary Function)和双参函数(Binary Function)三种形式，它们分别能以f()、f(x)和f(x,y)的形式被调用，STL定义的其他所有函数对象都是这三种概念的强化。如下简单示例展示几种形式的实现：
　　
　　1、无参(Generator)形式
　　
　　strUCt counter
　　{
　　typedef int result_type;
　　counter(result_type init=0):n(init){}
　　result_type operator() { return n++;}
　　result_type n;
　　}
　　2、单参(Unary Function)形式
　　
　　template＜class Number＞ struct even // 函数对象even，找出第一个偶数
　　{
　　bool operator()(Number x) const {return (x&1) == 0;}
　　}
　　// 使用算法find_if在区间A到A+N中找到满足函数对象even的元素
　　int A[] = {1,0,3,4};
　　const int N=sizeof(A)/sizeof(int);
　　find_if(A,A+N, even＜int＞());
　　3、双参(Binary Function)形式
　　
　　struct ltstr
　　{
　　bool operator()(const char* s1, const char* s2) const
　　{ return strcmp(s1＜s2) ＜ 0;}
　　};
　　// 使用函数对象ltstr，输出set容器中A和B的并集
　　const int N=3
　　const char* a[N] = {“xjz”,”xzh”,”gh”};
　　const char* b[N]= {“jzx”,”zhx”,”abc”};
　　set＜const char*,ltstr＞ A(a,a+N);
　　set＜const char*,ltstr＞ B(b,b+N);
　　set_union(A.begin(),A.end(),B.begin(),B.end(), ostream_iterator＜const char*＞(cout,” “), ltstr());
　　容器(container)是一种对象(object)，可以包含并治理其它的对象，并提供迭代器(iterators)用以定址其所包含之元素。根据迭代器种类的不同，容器也分为几中，以Input Iterator为迭代器的一般container，以Forward Iterator为迭代器的Forward Container，以Bidirectional Iterator 为迭代器的Reversible Container，以Random Access Iterator为迭代器的Random Access Container。STL定义二种大小可变的容器：序列式容器(Sequence Container)和关联式容器(Associative Container)序列式容器包括vector、list和deque，关联式容器包括set、map、multiset和multimap。以下示例简单说明部分容器的使用：
　　
　　1、vector使用
　　
　　// 将A中以元素5为分割点，分别排序，使排序后5后面的元素都大于5之前的元素(后区间不排序)，然后输出
　　int main()
　　{
　　int A[] = {7,2,6,4,5,8,9,3,1};
　　const int N=sizeof(A)/sizeof(int);
　　vector＜int＞ V(A,A+N);
　　partial_sort(V,V+5,V+N);
　　copy(V,V+N,ostream_iterator＜int＞(cout,” “));
　　cout ＜＜ endl;
　　}
　　输出可能是：1 2 3 4 5 8 9 7 6
　　
　　2、list使用
　　
　　
　　 // 产生一空list，插入元素后排序，然后输出
　　int main()
　　{
　　list＜int＞ L1;
　　L1.push_back(0);
　　L1.push_front(1);
　　L1.insert(++L1.begin,3);
　　L1.sort();
　　copy(L1.begin(),L1.end(),ostream_iterator＜int＞(cout,” “));
　　}
　　输出：0 1 3
　　
　　3、deque使用
　　
　　int main()
　　{
　　deque＜int＞ Q;
　　Q.push_back(3);
　　Q.push_front(1);
　　Q.insert(Q.begin()+1,2);
　　Copy(Q.begin(),Q.end(),ostream_iterator＜int＞(cout,” “));
　　}
　　输出：1 2 3
　　
　　4、map使用
　　
　　int main()
　　{
　　map＜string,int＞ M;
　　M.insert(make_pair(“A”,11);
　　pair＜map＜string,int＞::iterator, bool＞ p = M.insert(make_pair(“C”,5));
　　if(p.second)
　　cout ＜＜ p.first-＞second＜＜endl;
　　}
　　输出：5
　　
　　5、multiset使用
　　
　　int main()
　　{
　　　const int N = 5;
　　　int a[N] = {4,1,1,3,5};
　　　multiset＜int＞ A(a,a+N);
　　　copy(A.begin(),A.end(),ostream_iterator＜int＞(cout,” “));
　　}
　　输出：1 1 3 4 5 设计新思维
　　
　　将设计模式(design patterns)、泛型编程(generic programming)和面向对象编程(object-oriented programming)有机的结合起来，便形成了设计新思维。 !-- frame contents -- !-- /frame contents -- 其中，设计模式是经过提炼的出色设计方法，对于很多情况下碰到的问题，它都是合理而可复用的解决方案；泛型编程是一种典范(paradigm)，专注于将类型抽象化，形成功能需求方面的一个精细集合，并利用这些需求来实现算法，相同的算法可以运用于广泛的类型集中，所谓泛型，就是具有在多种数据类型上皆可操作的含意；最后同面象对象编程中的多态(polymorphism)和模板(templates)等技术相结合，便获得极高层次上的具有可复用性的泛型组件。泛型组件预先实现了设计模块，可以让用户指定类型和行为，从而形成合理的设计，主要特点是灵活、通用和易用。
　　policies和policy类，是一种重要的类设计技术，所谓policy，是用来定义一个类或类模板的接口，该接口由下列之一或全部组成：内部类型定义、成员函数和成员变量。
　　
　　基于policy的类由许多小型类(称为policies)组成，每一个这样的小型类只负责单纯如行为或结构的某一方面。Policies机制由模板和多重继续组成，它们可以互相混合搭配，从而形成设计戎的多样性，通过plicy类，不但可以定制行为，也可以定制结构。
　　
　　下面简单举例说明泛化思维和面向对象思维在部分设计模式中的运用。
　　
　　Singletons设计模式泛化实现
　　
　　Singleton模式是一种保证一个对象(class)只有一个实体，并为它提供一个全局访问点。Singleton是一种经过改进的全局变量，既在程序中只能有唯一实体的类型，它的重点主要集中在产生和治理一个独立对象上，而且不答应产生另一个这样的对象。
　　
　　先让我们看看一般的C++实现的基本手法，下面是实现源码：
　　
　　// Singleton.h文件中
　　class Singleton
　　{
　　　public:
　　　static Singleton& Instance()
　　　{
　　if(!pInstance_){
　　　if(destroyed_){ // 引用是否已经失效
　　OnDeadReference();
　　　}
　　　else {
　　Create(); // 第一次时创建实例
　　　}
　　}
　　return *pInstance_;
　　　}
　　　private:
　　Singleton(); // 禁止默认构造
　　Singleton(const Singleton&); // 禁止拷贝构造
　　Singleton& operator= (const Singleton&);　// 禁止赋值操作
　　static void Create() // 传加创建的实例引用
　　{
　　　static Singleton theInstance;
　　　pInstance_ = &theInstance;
　　}
　　static void OnDeadReference()
　　{
　　　throw std::runtime_error(“ 实例被不正当消毁”);
　　}
　　virtual ~Singleton()
　　{
　　　pInstance- = 0;
　　　destroyed_ = true;
　　} static Singleton *pInstance_;
　　static bool destroyed_;
　　}
　　// Singleton.cpp中静态成员变量初始化
　　Singleton* Singleton::pInstance_ = 0;
　　Bool Singleton::destroyed_ = false;
　　如上所示，Singleton模式实现中只有一个public成员Instance()用来第一次使用时创建单一实例，当第二次使用时静态变量将已经被设定好，不会再次创建实例。还将默认构造函数、拷贝构造函数和赋值操作符放在private中，目地是不让用户使用它们。另外，为避免实例意外消毁后再实例化情况，加入静态布尔变量destroy_来进行判定是否出错，从而达到稳定性。
　　
　　从上面一般实现可以看出Singleton模式实现主要在于创建(Creation)方面和生存期(Lifetime)方面，既可以通过各种方法来创建Singleton。Creation必然能创建和摧毁对象，必然要开放这两个相应函数，将创建作为独立策略分离开来是必需的，这样你就可以创建多态对象了，所以泛化Singleton并不拥有Creator对象，它被放在CreationPolicy＜T＞类模板之中。生命期是指要遵循C++规则，后创建都先摧毁，负责程序生命期某一时刻摧毁Singleton对象。
　　 下面是一个简单的泛化Singleton模式的实现(不考虑线程因素)
　　
　　template
　　＜ class T,
　　　template＜class＞ calss CreationPolicy = CreateUsingNew,
　　　template＜class＞ class LifetimePolicy=DefaultLifetime,
　　＞
　　classs SingletonHolder
　　{
　　　public:
　　static T& Instance()
　　{
　　　if(!pInstance_)
　　　{
　　if(destroyed_)
　　{
　　　LifetimePolicy＜T＞::OnDeadReference();
　　　destroyed_ = false;
　　}
　　pInstance_ = CreationPolicy＜T＞::Create();
　　LifetimePolicy＜T＞::SchedultCall(&DestorySingleton);
　　　}
　　　return *pInstance_;
　　}
　　　private:
　　static void DestroySinleton()
　　{
　　　assert(!destroyed_);
　　　CreationPlicy＜T＞::Destroy(pInstance_);
　　　pInstance_ = 0;
　　　destroyed_ = true;
　　} SingletonHolder();
　　SingletonHolder (const SingletonHolder &);
　　SingletonHolder & operator= (const SingletonHolder &);　
　　
　　Static T* pInstance_;
　　Static bool destroyed_;
　　};
　　Instance()是SingletonHolder开放的唯一一个public函数，它在CreationPolicy、LifetimePolicy中打造了一层外壳。其中模板参数类型T，接收类名，既需要进行Singleton的类。模板参数内的类模板缺省参数CreateUsingNew是指通过new操作符和默认构造函数来产生对象，DefaultLifetime是通过C++规则来治理生命期。 LifetimePolicy＜T＞中有二个成员函数，ScheduleDestrution()函数接受一个函数指针，指向析构操作的实际执行函数，如上面DestorySingleton析构函数；OnDeadReference()函数同上面一般C++中同名函数相同，是负责发现失效实例来抛出异常的。CreationPlicy＜T＞中的Create()和Destroy()两函数是用来创建并摧毁具体对象的。
　　
　　下面是上述泛化Singleton模式实现的使用：
　　
　　1、应用一
　　
　　class A{};
　　typedef SingletonHolder＜A, CreateUsingNew＞ SingleA;
　　2、应用二
　　
　　class A{};
　　class Derived : public A {};
　　template＜class T＞ struct MyCreator : public CreateUsingNew＜T＞
　　{
　　　static T* Create()
　　　{
　　return new Derived;
　　　}
　　　static void Destroy(T* pInstance)
　　　{
　　delete pInstance;
　　　}
　　}
　　typedef SingletonHolder＜A,MyCreator＞ SingleA;
　　通过上面示例可以看出， SingletonHolder采用基于plicy设计实现，它将Singleton对象分解为数个policies，模板参数类中CreationPolicy和LifetimePolicy相当于二个policies封装体。利用它们可以协助制作出使用者自定义的Singleton对象，同时还预留了调整和扩展的空间。由此而得，泛型组件(generic components)，是一种可复用的设计模板，结合了模板和模式，是C++中创造可扩充设计的新方法，提供了从设计到代码的简易过渡，帮助我们编写清楚、灵活、高度可复用的代码。