泛型編程與設計新思維之一

泛型編程與設計新思維之一

徐景周

前言

       永遠記住，編寫代碼的宗旨在于簡單明了，不要使用語言中的冷僻特性，耍小聰明，重要的是編寫你理解的代碼，理解你編寫的代碼，這樣你可能會做的更好。

--- 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.anti-gravitydesign.com