泛型编程与设计新思维之一

发表于:2007-07-01来源:作者:点击数: 标签:
泛型编程与设计新思维之一 徐景周 前言 永远记住,编写代码的宗旨在于简单明了,不要使用语言中的冷僻特性,耍小聪明,重要的是编写你理解的代码,理解你编写的代码,这样你可能会做的更好。 --- Herb Sutter 1998年,国际C++标准正式通过,标准化对C++最重

泛型编程与设计新思维之一

徐景周

前言

       永远记住,编写代码的宗旨在于简单明了,不要使用语言中的冷僻特性,耍小聪明,重要的是编写你理解的代码,理解你编写的代码,这样你可能会做的更好。

--- Herb Sutter

 

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是一种高效、泛型、可交互操作的软件组件。所谓泛型(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 Aclearcase/" target="_blank" >ccess 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

 


原文转自:http://www.ltesting.net