Impossible is nothing  
  爱过知情重醉过知酒浓   花开花谢终是空   缘份不停留像春风来又走   女人如花花似梦
公告
日历
<2008年6月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345
统计
  • 随笔 - 8
  • 文章 - 91
  • 评论 - 16
  • 引用 - 0

导航

常用链接

留言簿(4)

随笔分类(4)

随笔档案(8)

文章分类(77)

文章档案(91)

相册

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 
1.什么是STL?

标准模板库(Standard Template Library)。虚函数和模板(包括函数模板和类模板)是C++语言的两个重要特性,MFC利用大量地运用了虚函数,而STL则是利用模板实现的。

2.为什么要使用类属算法?

软件模块的可重用性考虑,使得不必为每一种数据类型编写算法,在抽象数据类型上定义算法,当算法作用于具体数据类型时,只要用特定的数据类型具体化便可。

例如:

template <typename T>

T max(T x,T y)

{

          if(x<y) ruturn y;

        else return x;

}

调用如下

int u=3,v=4;

double d=4.7;

cout<<max(u,v)<<endl;

cout<<max(d,9.3)<<endl;

函数模板在使用时不必告诉编译器所使用的实际类型,编译器可以从参数中直接判断出来,如上例。

注意:编译器不会进行自动类型转换。所以如下调用时不正确的:

cout<<max(u,d)<<endl; //incorrect

这里使用的是内置数据类型,也可以传递用户定义数据类型,但必须定义<比较运算符 。

另一方面,STL使用的类属算法,与容器(STL的重要基本概念之一,通俗地理解,就是封装过的数组,队列,集合等 放置数据的一种结构,从字面意思即可理解,也可以理解为一种模板类)是相对独立的,即一种类属算法可以应用于多种容器之上,甚至有些类属算法可以应用于所 有的容器。OOP编程一般把作用于类的操作,即使算法实现为特定类的成员函数,使得数据和算法紧密的联系在一起,但是STL把各种容器的公共操作提取出 来,作为一个独立的组件(算法集合),而把某些特殊的算法实现为容器的成员函数(出于容器的特殊性考虑,有些类属算法虽然可以实现同样的功能,但适当考虑 某些容器的特殊性之后,可以有不同的实现方式,使得这种操作作用于特殊的类时效率更高,于是一部分某些容器也提供实现相同功能的成员函数),例如对于类属 算法find,其时间复杂度是线性的,而有序关联容器(set,multiset,map,multiset)就提供了成员函数,其实见复杂度为log (N)。

总的来说,使用类属算法,提高了通用性,降低了程序员工作的复杂度,可以通过标准的统一接口来编程,也易于维护。

3.类属算法如何工作?

容器(container)<——>迭代器(iterator)<——>类属算法(algorithm)

迭代器是类似于指针的一种STL组件,在STL中,迭代器的用法跟指针类似,目前就暂且把它理解为指针。

可以这样理解,类属算法不是对容器直接操作,而是通过对指向容器某个位置的迭代器(类似指针)来实现对该地址的数据的操作。

4.基本概念

类模板

template<typename T1,typename T2>

class pair{

public:

          T1 first;

          T2 second;

          pair():first(T1()),sencond(T2()){}   //默认构造函数

          pair(const T1&  x,const T2&  y):first(x),second(y){}  //自定义构造函数

} ;        

实际调用时:

pair<int,char> pair1(13,'a');

pair<bool,double> pair2(true,0.1);

函数模板:上面的max()函数就是一个简单的函数模板。

成员函数模板

不管类属否使用模板定义,其成员函数都可以有模板参数,例如:

template <typename T>

class vector{

          //.....

public:

          template <typename InputIterator>

          void insert(iterator position,InputIterator first,InputIterator last);

          //.....

};

容器

在STL中,容器指存储其他对象的集合的对象,主要有两种类型的STL容器:序列容器和顺序关联容器。

序列容器

序列容器将一组具有相同类型的对象以严格线性的形式组织在一起。包括如下几种:

vector<T> 提供对变长序列的随机访问,对序列末尾的插入和删除操作时间是分摊常量的,对序列开头的插入和删除是线性的。可以理解为封装后的数组。

depue<T>提供对变长序列的随机访问,对序列开头和末尾的插入和删除操作是分摊常量的。存储空间是连续的(这一点尚未在书上说明,只是个人推测)。

list<T>提供对变长序列的线性时间访问,但是对序列中任意位置的插入和删除操作均为常量时间的。可以理解为封装后的链表。

对向量使用STL类属算法reverse:

#include<iostream>
#include<vector>
#include<cassert>
#include<string>
#include<algorithm> //for reverse
using namespace std;

template<typename Container>
Container make(const char s[])
{
 return Container(&s[0],&s[strlen(s)]);
}

int main()
{
 cout<<"Using reverse algorithm with a vector"<<endl;
 string string1="mark twain";
 vector<char> vector1(string1.begin(),string1.end()); //begin()和end()是访问器,返回迭代器
 reverse(vector1.begin(),vector1.end());
 assert(vector1==make< vector<char> >("niawt kram"));
 cout<<" --OK."<<endl;
 return 0;
}

有序关联容器

有序关联容器具有从基于键的集合种快速提取对象的能力。集合的大小可以在运行时改变。STL中有4种类型的有序关联容器:

set<Key>支持唯一的键(每个键值只能有一个)并提供对见本身的快速检索。

multiset<Key>支持客重复的键(同一个键值可以有多个副本)并提供对键本身的快速检索。

map<Key,T>支持唯一的(Key类型的)键并提供对另一个基于键的类型T的快速检索 。

multimap<Key,T>支持可重复的(Key类型的)键并提供对另一个基于键的类型T的快速检索。

演示STL映射(map):

#include<iostream>
#include<map>
#include<string>
using namespace std;

int main()
{
 map<string,long> directory;
 directory["Bogart"]=123;
 directory["Bacall"]=456;
 directory["Cagney"]=789;
 string name;
 while(cin>>name)
 {
  if(directory.find(name)!=directory.end())
   cout<<"The phone number for "<<name
   <<" is "<<directory[name]<<"\n";
  else
   cout<<"Sorry,no listing for "<<name<<endl;
 }
 return 0;
}

上例中,find()为所有有序关联容器的成员函数,查找时间复杂度为logN,该函数首先检查name是否为保存在directory中的一个键,假如directory确实存在以name作为键值的数据项,则其返回该数据项的迭代器,否则find函数返回“序列末尾最后一个元素之后的一个位置”迭代器,该迭代器与end成员函数返回的迭代器相同

STL容器和其他C++容器类库中的容器的一个重要区别:STL容易并没有为其所包含的容器提供过多的操作(成员函数),相反,STL提供的是类属算法。

类属算法

最简单的类属算法:find和merge

类属查找算法find

用表演示find类属算法

#include<iostream>
#include<cassert>
#include<list>
#include<algorithm>
using namespace std;

template<typename Container>
Container make(const char s[])
{
 return Container(&s[0],&s[strlen(s)]);
}

int main()
{
 list<char> list1=make< list<char> >("C++ is a better C.");
 list<char>::iterator
  where=find(list1.begin(),list1.end(),'e');
 list<char>::iterator next=where;
 ++next;
 assert(*where=='e' && *next=='t');
 cout<<" ---OK."<<endl;
 return 0;
}

注意:与表对应的迭代器不支持表达式*(where+1)中的+运算符,而向量(vector)和双端队列支持这样的表达式。但所有的STL迭代器都要求支持++。

类属合并算法merge

merge算法的功能是将两个序列的元素合并到一个序列中,调用形式为

merge(first1,last1,first2,last2,result);

则包含如下假定:

*迭代器first1和last1表示一个输入序列的起始和终止位置,其元素类型为T;

*迭代器first2和last2表示另一个输入序列的起始和终止位置,其元素类型也为T;

*按照类型T上的<运算符的定义,两个输入序列均为升序排列。

*result表示合并后序列存放的起始位置。

merge函数返回的结果是合并两个序列后的一个升序序列。

示例:merge类属算法合并数组和向量,把结果保存在表中

#include<iostream>
#include<string>
#include<cassert>
#include<vector>
#include<list>
#include<algorithm>
using namespace std;

template<typename Container>
Container make(const char s[])
{
 return Container(&s[0],&s[strlen(s)]);
}

int main()
{
 char s[]="acegikm";
 vector<char> vector1(
  make< vector<char> >("bdfhjlnopqrstuvwxyz"));
 list<char> list1(26,'x'); //将list1初始化为26个'x'

 //merge first 5 letters in array s with first 10 in
 //vector1,putting result in list1
 merge(&s[0],&s[5],vector1.begin(),vector1.begin()+10,list1.begin());

 assert(list1==
  make< list<char> >("abcdefghijlnopqxxxxxxxxxxx"));
 cout<<" --OK."<<endl;
 return 0;
}

疑问:vc6.0下如果把上述程序中的vector换作deque,则无法通过编译,不知道是否是编译器不支持

deque<char> deque1(
  make< deque<char> >("bdfhjlnopqrstuvwxyz"));

这种初始化方式?

迭代器

普通的C++指针就是一种迭代器,但除了指针以外,还有其他种类的迭代器。STL要求这些迭代器具有和指针类似的特性,既可以对迭代器做++和*等操作,而且这些操作与定义在指针上的相同操作具有相同的功能。

各个迭代器(不包括分配器)之间的层次关系及其要求定义的运算:

1. ==   !=  *

2.   ++

3.     --

4.+=  -=  +  -  <  >  <=  >=

前向(输入,输出):1,2

双向:1,2,3

随机:所有

前向也是双向迭代器,双向也是随机迭代器。

对于输入迭代器,只能读取数据,不能写入;对于输出迭代器,只能写入数据,不能读取。

演示类属算法accumulate,该算法在初始值基础上累加指定容器区间的值。

#include<iostream>
#include<vector>
#include<cassert>
#include<numeric>  //for accumulate
using namespace std;

int main()
{
 int x[5]={2,3,5,7,11};
 vector<int> vector1(&x[0],&x[5]);
 int sum=accumulate(vector1.begin(),vector1.end(),0); //最后一个参数是累加的初始值
 assert(sum==28);
 cout<<"--OK."<<endl;
 return 0;
}

向量和双端队列迭代器是随机迭代器,而表迭代器仅仅是双向的,并非随机,固有些要求随机迭代器的类属算法不能用于表容器,例如sort算法,一次表容器有排序成员函数。

函数对象

先看一例。STL提供了accumulate函数的一个更为通用的版本。其定义如下:

template <typename InputIterator,typename T,typename BinaryOperation>
T accumulate(InputIterator first,InputIterator last,
    T init,BinaryOperation binary_op)
{
 while (first!=last)
 {
  init=binary_op(init,*first);
  ++first;
 }
 return init;
}

上面的定义没有定义+运算符,而是引入了另一个参数binary_op,作为定义在序列质类型上的二元操作符。

示例:使用增强版的accumulate计算连乘积

#include<iostream>
#include<vector>
#include<cassert>
#include<numeric> //for accumulate
using namespace std;

int mult(int x,int y){return x*y;}

int main()
{
 int x[5]={2,3,5,7,11};
 vector<int> vector1(&x[0],&x[5]);
 int product=
  accumulate(vector1.begin(),vector1.end(),1,mult);
 assert(product==2310);
 cout<<"--OK."<<endl;
 return 0;
}

这里传递给accumulate函数的是一个普通函数的mult,实际上传递的是该函数的地址。

函数对象是一种实体,可以不带参数,也可以带有一个以上的参数,不能够从中获得一个值或者改变程序的状态。除了上面所示的普通函数,另一类函数对象是类或者结构的对象,且在其定义中重载了()运算符,而且这种方式在STL中更为常用。

请看下例:

#include<iostream>
#include<vector>
#include<cassert>
#include<numeric>  //for accumulate
using namespace std;

class multiply
{
public:
 int operator()(int x,int y) const{return x*y;}
};

int main()
{
 int x[5]={2,3,5,7,11};
 vector<int> vector1(&x[0],&x[5]);
 int product=
  accumulate(vector1.begin(),vector1.end(),1,multiply());
 assert(product==2310);
 cout<<"--OK."<<endl;
 return 0;
}

通过在类multiply中定义运算符operator(),就定义了一种可以作为函数参数的对象,可以像使用函数一样使用这种对象。这里传递给accumulate的对象是通过调用multiply类的默认构造函数multiply()获得的。

使用以类的形式定义的函数对象比普通函数优越,它可以携带更多额外的信息(可以静态数据成员的形式),以后再举例子。

适配器

用来改变其他组件接口的组件称为适配器。包括迭代器适配器、容器适配器和函数适配器。

迭代器适配器

reverse_iterator将某种类型的迭代器变成一种新的迭代器,但保持其功能不变,而仅将其便利的顺序倒转过来。

容器适配器

栈适配器可以将序列容器变换到后进先出的栈接口中。

队列适配器可以将序列容器变换到先进先出的队列中。

优先级队列可以将序列容器变换到优先级队列中,由一个比较参数来控制对其元素的访问顺序。

函数适配器

取反器(negator)用于对判定函数对象(判定函数对象指那些返回值为bool类型的函数对象)的结果进行取反。

邦定器(binder)通过将二元函数的一个参数与某个特定的值邦定,可以将二元函数变成一元函数。

函数指针适配器从函数指针得到函数对象,与使用标准函数相比,这将使编译后的代码具有更大的灵活性。

下面一例使用反向迭代器。

#include<iostream>
#include<vector>
#include<cassert>
#include<numeric> //for accumulate
using namespace std;

int main()
{
 float small=(float)1.0/(1<<26);
 float x[5]={1.0,3*small,2*small,small,small};
 vector<float> vector1(&x[0],&x[5]);
 cout<<"Values to be added: "<<endl;
 vector<float>::iterator i;
 for(i=vector1.begin(); i != vector1.end(); ++i)
  cout<<*i<<endl;
 cout<<endl;

 float sum=accumulate(vector1.begin(),vector1.end(),(float)0.0);
 cout<<"Sum accumulated from left = "<<sum<<endl;

 float sum1=accumulate(vector1.rbegin(),vector1.rend(),(float)0.0);
 cout<<"sum accumulated from right = "<<(double)sum1<<endl;

 return 0;
}

vector<float>::reverse_iterator类型是用迭代器适配器定义的。也可以在程序中直接使用适配器:

reverse_iterator<vector<float>::iterator> start(vector1.end()),finish(vector1.begin());

float sum1=accumulate(start,finish,(float)0.0);

reverse_iterator类型也提供了++和--运算符,但互换了这两个运算符的含义。上例中的vector1.rbegin()和vector1.rend()成员函数返回的即是reverse_iterator类型。

分配器

每种STL容器都是用了一种分配器类,用来封装程序所用的内存分配模式的信息。不同的内存分配模式采用不同的方法从 操作系统中检索内存。分配器类可以封装许多方面的信息,包括指针、常量指针、引用、常量引用、对象大小、不同类型指针之间的差别、分配函数与释放函数、以 及一些函数的信息。分配器上的所有操作都具有分摊常量的运行时间。

由于内存分配模式方面的信息可以封装在分配器中,所以提供不同的分配器,就可以使STL容易能够用于不同的内存分配模式。

对多数程序员来说,STL提供的默认分配器类已经可以满足编程的需要了。

posted on 2006-02-22 22:04 笑笑生 阅读(847) 评论(1)  编辑 收藏 引用 所属分类: C++语言
评论:

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


 
Copyright © 笑笑生 Powered by: 博客园 模板提供:沪江博客