STL泛型編程與設計新思維

2019-11-17 05:07:42

字體：大中小

來源：轉載

供稿：網友

　　前言

　　永遠記住，編寫代碼的宗旨在于簡單明了，不要使用語言中的冷僻特性，耍小聰明，重要的是編寫你理解的代碼，理解你編寫的代碼，這樣你可能會做的更好。
　　　　　　　　　　　　　　　　　　　　--- 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 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)有機的結合起來，便形成了設計新思維。

其中，設計模式是經過提煉的出色設計方法，對于很多情況下碰到的問題，它都是合理而可復用的解決方案；泛型編程是一種典范(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++中創造可擴充設計的新方法，提供了從設計到代碼的簡易過渡，幫助我們編寫清楚、靈活、高度可復用的代碼。

上一篇：C++實現三維視圖繪制與消隱技術

下一篇：C++箴言：聲明為非成員函數時機