STL泛型编程与设计新思维

函数对象(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